CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:多项式应用 [2020/10/20 17:38]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:多项式应用 [2021/08/29 18:56] (当前版本)
jxm2001 [题解]
@@ 行 1: / 行 1: @@
-====== 多项式练习 1 ======
+====== 多项式应用 ======
 ===== 习题一 =====
@@ 行 72: / 行 72: @@
 </hidden>
-===== 习题二 =====
+===== 习题二（字符串匹配） =====
 [[https://www.luogu.com.cn/problem/P4173|洛谷p4173]]
@@ 行 201: / 行 201: @@
 </hidden>
-===== 习题三 =====
+===== 习题三（差分与前缀和） =====
 [[https://www.luogu.com.cn/problem/P5488|洛谷p5488]]
@@ 行 214: / 行 214: @@
 $$
-F(x)(1-x)^k=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}(-1)^i{i\choose k}=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}(-1)^i\frac {k^{i}}{i!}
+F(x)(1-x)^k=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}(-1)^i{i\choose k}=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}(-1)^i\frac {k^{\underline i}}{i!}
 $$
-$k$ 阶前缀和等价于 $F(x)(1+x+x^2+x^3+\cdots)^k=F(x)(\cfrac 1{1-x})^k$。
+而 $k$ 阶前缀和等价于
+$$
+F(x)(1+x+x^2+x^3+\cdots)^k=F(x)(1-x)^{-k}=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}(-1)^i\frac {(-k)^{\underline i}}{i!}=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}\frac {k^{\overline i}}{i!}
+$$
+直接 $O(n)$ 递推出系数然后 $\text{NTT}$ 卷积即可。时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,Mod=1004535809;
+int quick_pow(int a,int b){
+	int t=1;
+	while(b){
+		if(b&1)
+		t=1LL*t*a%Mod;
+		a=1LL*a*a%Mod;
+		b>>=1;
+	}
+	return t%Mod;
+}
+namespace Poly{
+	const int G=3;
+	int rev[MAXN<<2],Pool[MAXN<<3],*Wn[30];
+	void init(){
+		int lg2=0,*pos=Pool,n,w;
+		while((1<<lg2)<MAXN*2)lg2++;
+		n=1<<lg2,w=quick_pow(G,(Mod-1)/(1<<lg2));
+		while(~lg2){
+			Wn[lg2]=pos,pos+=n;
+			Wn[lg2][0]=1;
+			_for(i,1,n)Wn[lg2][i]=1LL*Wn[lg2][i-1]*w%Mod;
+			w=1LL*w*w%Mod;
+			lg2--;n>>=1;
+		}
+	}
+	int build(int k){
+		int n,pos=0;
+		while((1<<pos)<=k)pos++;
+		n=1<<pos;
+		_for(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
+		return n;
+	}
+	void NTT(int *f,int n,bool type){
+		_for(i,0,n)if(i<rev[i])
+		swap(f[i],f[rev[i]]);
+		int t1,t2;
+		for(int i=1,lg2=1;i<n;i<<=1,lg2++){
+			for(int j=0;j<n;j+=(i<<1)){
+				_for(k,j,j+i){
+					t1=f[k],t2=1LL*Wn[lg2][k-j]*f[k+i]%Mod;
+					f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod;
+				}
+			}
+		}
+		if(!type){
+			reverse(f+1,f+n);
+			int div=quick_pow(n,Mod-2);
+			_for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod;
+		}
+	}
+	void Mul(int *f,int _n,int *g,int _m,int xmod=0){
+		int n=build(_n+_m-2);
+		_for(i,_n,n)f[i]=0;_for(i,_m,n)g[i]=0;
+		NTT(f,n,true);NTT(g,n,true);
+		_for(i,0,n)f[i]=1LL*f[i]*g[i]%Mod;
+		NTT(f,n,false);
+		if(xmod)_for(i,xmod,n)f[i]=0;
+	}
+}
+char s[MAXN];
+int inv[MAXN],a[MAXN<<2],b[MAXN<<2];
+void get_inv(int n){
+	inv[1]=1;
+	_rep(i,2,n)
+	inv[i]=1LL*(Mod-Mod/i)*inv[Mod%i]%Mod;
+}
+int main()
+{
+	Poly::init();
+	int n=read_int();
+	get_inv(n);
+	scanf("%s",s);
+	int len=strlen(s),k=0;
+	_for(i,0,len)
+	k=(10LL*k+s[i]-'0')%Mod;
+	int t=read_int();
+	_for(i,0,n)a[i]=read_int();
+	b[0]=1;
+	if(t) _for(i,1,n){
+		b[i]=-1LL*b[i-1]*(k-i+1)%Mod*inv[i]%Mod;
+		if(b[i]<0)b[i]+=Mod;
+	}
+	else _for(i,1,n)
+	b[i]=1LL*b[i-1]*(k+i-1)%Mod*inv[i]%Mod;
+	Poly::Mul(a,n,b,n,n);
+	_for(i,0,n)
+	space(a[i]);
+	return 0;
+}
+</code>
+</hidden>
+===== 习题四（矩阵卷积） =====
+==== 题意 ====
+考虑快速计算序列 $\{C\}$，其中 $A_i,B_i$ 均为 $w\times w$ 矩阵
+$$
+C_i=\sum_{j=0}^i A_jB_{i-j}(0\le i\le n)
+$$
+==== 题解 ====
+不难发现 $c_{ij}=\sum_{k=1}^w a_{ik}b_{kj}$，于是 $c_{ij}$ 可以拆分成 $w$ 个卷积。
+考虑 $O\left(w^2n\log n\right)$ 预处理出 $\{a_{ij}\}$ 和 $\{b_{ij}\}$ 的 $\text{DFT}$ 结果。然后通过  $c_{ij}=\sum_{k=1}^w a_{ik}b_{kj}$ 可以 $O\left(w^3n\right)$ 计算每个 $\{c_{ij}\}$ 的 $\text{DFT}$ 结果。
+最后对每个 $\{c_{ij}\}$ 做 $\text{IDFT}$，总时间复杂度 $O\left(w^2n\log n+w^3n\right)$。

CVBB ACM Team

用户工具

站点工具

页面工具