2020-2021:teams:legal_string:jxm2001:多项式_3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:多项式_3 [2020/08/20 17:00] jxm2001 |
2020-2021:teams:legal_string:jxm2001:多项式_3 [2020/08/25 12:43] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 262: | 行 262: | ||
| $$g(e,j)\gets \sum p_{e,k}\text{dp}(v_e,j+k)=\sum a_{\text{rig}-\text{lef}-k}b_{k+j-\text{mid}-1}$$ | $$g(e,j)\gets \sum p_{e,k}\text{dp}(v_e,j+k)=\sum a_{\text{rig}-\text{lef}-k}b_{k+j-\text{mid}-1}$$ | ||
| - | 递归边界为 $\text{lef}=\text{rig}$，此时用 $g(e,j)$ 更新 $\text{dp}(u_e,j)$。 | + | 递归边界为 $\text{lef}=\text{rig}$，此时用 $g(e,j)$ 更新 $\text{dp}(u_e,j)$。由于没有必要通过分治计算出 $\text{dp}(u_e,t+1\sim 2t)$，故可以分治前处理。 |
| - | + | ||
| - | 由于没有必要通过分治计算出 $\text{dp}(e_u,t+1\sim 2t)$，故可以分治前处理。 | + | |
| 总时间复杂度 $O(mt\log^2 t)$。 | 总时间复杂度 $O(mt\log^2 t)$。 | ||
| 行 678: | 行 676: | ||
| namespace Poly{ | namespace Poly{ | ||
| const int G=3; | const int G=3; | ||
| - | int rev[MAXN<<2],Wn[30][2]; | + | int rev[MAXN<<2],Pool[MAXN<<3],*Wn[30]; |
| void init(){ | void init(){ | ||
| - | int m=Mod-1,lg2=0; | + | int lg2=0,*pos=Pool,n,w; |
| - | while(m%2==0)m>>=1,lg2++; | + | while((1<<lg2)<MAXN*2)lg2++; |
| - | Wn[lg2][1]=quick_pow(G,m); | + | n=1<<lg2,w=quick_pow(G,(Mod-1)/(1<<lg2)); |
| - | Wn[lg2][0]=quick_pow(Wn[lg2][1],Mod-2); | + | while(~lg2){ |
| - | while(lg2){ | + | Wn[lg2]=pos,pos+=n; |
| - | m<<=1,lg2--; | + | Wn[lg2][0]=1; |
| - | Wn[lg2][0]=1LL*Wn[lg2+1][0]*Wn[lg2+1][0]%Mod; | + | _for(i,1,n)Wn[lg2][i]=1LL*Wn[lg2][i-1]*w%Mod; |
| - | Wn[lg2][1]=1LL*Wn[lg2+1][1]*Wn[lg2+1][1]%Mod; | + | w=1LL*w*w%Mod; |
| + | lg2--;n>>=1; | ||
| } | } | ||
| } | } | ||
| 行 701: | 行 700: | ||
| swap(f[i],f[rev[i]]); | swap(f[i],f[rev[i]]); | ||
| int t1,t2; | int t1,t2; | ||
| - | for(int i=1,lg2=0;i<n;i<<=1,lg2++){ | + | for(int i=1,lg2=1;i<n;i<<=1,lg2++){ |
| - | int w=Wn[lg2+1][type]; | + | |
| for(int j=0;j<n;j+=(i<<1)){ | for(int j=0;j<n;j+=(i<<1)){ | ||
| - | int cur=1; | ||
| _for(k,j,j+i){ | _for(k,j,j+i){ | ||
| - | t1=f[k],t2=1LL*cur*f[k+i]%Mod; | + | t1=f[k],t2=1LL*Wn[lg2][k-j]*f[k+i]%Mod; |
| f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod; | f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod; | ||
| - | cur=1LL*cur*w%Mod; | ||
| } | } | ||
| } | } | ||
| } | } | ||
| if(!type){ | if(!type){ | ||
| + | reverse(f+1,f+n); | ||
| int div=quick_pow(n,Mod-2); | int div=quick_pow(n,Mod-2); | ||
| _for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod; | _for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod; | ||
| 行 739: | 行 736: | ||
| void Div(const int *f,int _n,const int *g,int _m,int *q,int *r){ | void Div(const int *f,int _n,const int *g,int _m,int *q,int *r){ | ||
| static int temp[MAXN<<2]; | static int temp[MAXN<<2]; | ||
| - | _for(i,0,_m)temp[i]=g[_m-1-i]; | + | if(_n<_m){ |
| + | _rep(i,0,n)r[i]=f[i]; | ||
| + | return; | ||
| + | } | ||
| + | _rep(i,0,_m)temp[i]=g[_m-i]; | ||
| Inv(temp,q,_n-_m+1); | Inv(temp,q,_n-_m+1); | ||
| - | _for(i,0,_n)temp[i]=f[_n-1-i]; | + | _rep(i,0,_n)temp[i]=f[_n-i]; |
| - | Mul(q,_n-_m+1,temp,_n,_n-_m+1); | + | Mul(q,_n-_m+1,temp,_n+1,_n-_m+1); |
| for(int i=0,j=_n-_m;i<j;i++,j--)swap(q[i],q[j]); | for(int i=0,j=_n-_m;i<j;i++,j--)swap(q[i],q[j]); | ||
| - | _for(i,0,_m)r[i]=g[i];_rep(i,0,_n-_m)temp[i]=q[i]; | + | int __m=min(_n-_m+1,_m); |
| - | Mul(r,_m,temp,_n-_m+1,_m); | + | _for(i,0,_m)r[i]=g[i];_for(i,0,__m)temp[i]=q[i]; |
| + | Mul(r,_m,temp,__m,_m); | ||
| _for(i,0,_m)r[i]=(f[i]+Mod-r[i])%Mod; | _for(i,0,_m)r[i]=(f[i]+Mod-r[i])%Mod; | ||
| } | } | ||
2020-2021/teams/legal_string/jxm2001/多项式_3.1597914058.txt.gz · 最后更改: 2020/08/20 17:00 由 jxm2001
