CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:多项式应用 [2020/10/11 14:49]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:多项式应用 [2021/08/29 18:56] (当前版本)
jxm2001 [题解]
@@ 行 1: / 行 1: @@
-====== 多项式练习 1 ======
+====== 多项式应用 ======
 ===== 习题一 =====
@@ 行 71: / 行 71: @@
 </code>
 </hidden>
+===== 习题二（字符串匹配） =====
+[[https://www.luogu.com.cn/problem/P4173|洛谷p4173]]
+==== 题意 ====
+给定只包含小写字母和通配符的字符串 $A,B$。其中 $A$ 为模板串，$|A|=m,|B|=n$。询问所有匹配位置。
+==== 题解 ====
+构成字符集到数值的映射
+$$
+f(x)=
+\begin{cases}
+x-a &x= a\sim z\\
+&x=*
+\end{cases}
+$$
+令 $c_i=\sum_{j=0}^{m-1}\left(f(a_j)-f(b_{i-m+1+j})\right)^2f(a_j)f(b_{i-m+1+j})$。
+于是 $B$ 中第 $i$ 个字符结尾的长度为 $m$ 的字符串与 $A$ 匹配当且仅当 $c_i=0$。令 $t_i=a_{m-1-i}$，有
+$$\sum_{x+y=i}\left(f(t_x)-f(b_y)\right)^2f(t_x)f(b_y)=\sum_{x+y=i}f(t_x)^3f(b_y)+\sum_{x+y=i}f(t_x)f(b_y)^3-2\sum_{x+y=i}f(t_x)^2f(b_y)^2$$
+于是直接 $\text{FFT}$ 即可，时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5;
+const double pi=acos(-1.0);
+struct complex{
+	double x,y;
+	complex(double x=0.0,double y=0.0):x(x),y(y){}
+	complex operator + (const complex &b){
+		return complex(x+b.x,y+b.y);
+	}
+	complex operator - (const complex &b){
+		return complex(x-b.x,y-b.y);
+	}
+	complex operator * (const complex &b){
+		return complex(x*b.x-y*b.y,x*b.y+y*b.x);
+	}
+	complex operator * (const int &b){
+		return complex(x*b,y*b);
+	}
+}w[32][2];
+int rev[MAXN<<2];
+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));
+	for(int i=1,t=0;i<n;i<<=1,t++)
+	w[t][1]=complex(cos(pi/i),sin(pi/i)),w[t][0]=complex(cos(pi/i),-sin(pi/i));
+	return n;
+}
+void FFT(complex *f,int n,int type){
+	_for(i,0,n)if(i<rev[i])
+	swap(f[i],f[rev[i]]);
+	complex t1,t2;
+	for(int i=1,t=0;i<n;i<<=1,t++){
+		for(int j=0;j<n;j+=(i<<1)){
+			complex cur(1.0,0.0);
+			_for(k,j,j+i){
+				t1=f[k],t2=cur*f[k+i];
+				f[k]=t1+t2,f[k+i]=t1-t2;
+				cur=cur*w[t][type];
+			}
+		}
+	}
+	if(!type)_for(i,0,n)
+	f[i].x/=n;
+}
+complex sum[MAXN<<2];
+void Mul(int *a,int _n,int *b,int _m,int k,int n){
+	static complex f[MAXN<<2],g[MAXN<<2];
+	_for(i,0,_n)f[i]=complex(a[i],0.0);
+	_for(i,_n,n)f[i]=complex(0.0,0.0);
+	_for(i,0,_m)g[i]=complex(b[i],0.0);
+	_for(i,_m,n)g[i]=complex(0.0,0.0);
+	FFT(f,n,1);FFT(g,n,1);
+	_for(i,0,n)f[i]=f[i]*g[i];
+	_for(i,0,n)sum[i]=sum[i]+f[i]*k;
+}
+char s1[MAXN],s2[MAXN];
+int v1[MAXN],v2[MAXN],t1[MAXN],t2[MAXN];
+int main()
+{
+	int m=read_int(),n=read_int();
+	scanf("%s%s",s1,s2);
+	_for(i,0,m){
+		if(s1[i]=='*')v1[i]=0;
+		else
+		v1[i]=s1[i]-'a'+1;
+	}
+	reverse(v1,v1+m);
+	_for(i,0,n){
+		if(s2[i]=='*')v2[i]=0;
+		else
+		v2[i]=s2[i]-'a'+1;
+	}
+	int __n=build(n+m-2);
+	_for(i,0,m)t1[i]=v1[i]*v1[i]*v1[i];
+	_for(i,0,n)t2[i]=v2[i];
+	Mul(t1,m,t2,n,1,__n);
+	_for(i,0,m)t1[i]=v1[i]*v1[i];
+	_for(i,0,n)t2[i]=v2[i]*v2[i];
+	Mul(t1,m,t2,n,-2,__n);
+	_for(i,0,m)t1[i]=v1[i];
+	_for(i,0,n)t2[i]=v2[i]*v2[i]*v2[i];
+	Mul(t1,m,t2,n,1,__n);
+	FFT(sum,__n,0);
+	int cnt=0;
+	_for(i,m-1,n){
+		if(fabs(sum[i].x)<0.5)
+		cnt++;
+	}
+	enter(cnt);
+	_for(i,m-1,n){
+		if(fabs(sum[i].x)<0.5)
+		space(i-m+2);
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 习题三（差分与前缀和） =====
+[[https://www.luogu.com.cn/problem/P5488|洛谷p5488]]
+==== 题意 ====
+给定一个长度为 $n$ 的序列 $a$，求 $a$ 的 $k$ 阶差分或前缀和。
+==== 题解 ====
+设序列的生成函数为 $F(x)=\sum_{i=0}^{n-1} a_ix^i$，则 $k$ 阶差分等价于
+$$
+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)(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

用户工具

站点工具

页面工具