两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:legal_string:jxm2001:多项式应用 [2020/10/20 17:26] jxm2001 |
2020-2021:teams:legal_string:jxm2001:多项式应用 [2021/08/29 18:56] (当前版本) jxm2001 [题解] |
||
---|---|---|---|
行 1: | 行 1: | ||
- | ====== 多项式练习 1 ====== | + | ====== 多项式应用 ====== |
===== 习题一 ===== | ===== 习题一 ===== | ||
行 72: | 行 72: | ||
</hidden> | </hidden> | ||
- | ===== 习题二 ===== | + | ===== 习题二(字符串匹配) ===== |
[[https://www.luogu.com.cn/problem/P4173|洛谷p4173]] | [[https://www.luogu.com.cn/problem/P4173|洛谷p4173]] | ||
行 201: | 行 201: | ||
</hidden> | </hidden> | ||
- | ===== 习题三 ===== | + | ===== 习题三(差分与前缀和) ===== |
[[https://www.luogu.com.cn/problem/P5488|洛谷p5488]] | [[https://www.luogu.com.cn/problem/P5488|洛谷p5488]] | ||
行 210: | 行 210: | ||
==== 题解 ==== | ==== 题解 ==== | ||
+ | |||
+ | 设序列的生成函数为 $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)$。 | ||
+ | |||
+ |