[分治FFT] UOJ50. [UR #3] 链式反应

明显是多项式题啦。

可以写出转移方程: \[ f(i)=\frac{1}{2}\sum_j\sum_k[i-1-j-k\in A]{i-1\choose j}{i-1-j\choose k}f(j)f(k)+1 \] 打开后整理一下: \[ f(i)=\frac{(i-1)!}{2} \sum_j \sum_k \frac{f(j)}{j!} \frac{f(k)}{k!}\frac{1}{i-1-j-k}= (i-1)! (f*f*h)_{i-1} \] 然后可以分治 \(FFT\) 求。

但这里有个 \(f*f\) ,考虑贡献的时候有点不一样,分 两个都在 \([L,mid]\) 与 只有一个在 这两种情况。

这也是可以在分治过程中求得的。

这样是两个 \(log\) 。题解中有一个 \(log\) 的做法,需要知道解微分方程的技巧... 以后来看吧...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=262500,P=998244353,N=1<<18;
int fac[maxn],inv[maxn],fac_inv[maxn];

int Pow(LL a,int b){
LL res=1;
for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;
return res;
}
int rev[maxn];
void getrev(int n){
int t=0; while((1<<t)<n) t++;
for(int i=1;i<=n-1;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<t-1);
}
void NTT(int a[],int n,int k){
for(int i=0;i<=n-1;i++) if(rev[i]<i) swap(a[rev[i]],a[i]);
for(int m=2;m<=n;m<<=1){
int wm=Pow(3,(P-1)/m); if(k==-1) wm=Pow(wm,P-2);
for(int i=0;i<=n-1;i+=m){
LL t0,t1,w=1;
for(int j=0;j<=(m>>1)-1;j++,w=w*wm%P)
t0=a[i+j], t1=w*a[i+j+(m>>1)]%P, a[i+j]=(t0+t1)%P, a[i+j+(m>>1)]=(t0+P-t1)%P;
}
}
if(k==-1){
LL t=Pow(n,P-2);
for(int i=0;i<=n-1;i++) a[i]=t*a[i]%P;
}
}
int A[maxn],B[maxn],C[maxn],f[maxn],g[maxn],h[maxn];
void Solve(int L,int R){
if(L==R){
f[L]=(LL)f[L]*fac[L-1]%P;
return;
}
int mid=(L+R)>>1;
Solve(L,mid);
int len=1; while(len<R-L+1) len<<=1; getrev(len);
for(int i=L;i<=mid;i++) A[i-L]=g[i];
for(int i=0;i<=R-L-1;i++) B[i]=h[i];
NTT(A,len,1); NTT(B,len,1);
for(int i=0;i<=len-1;i++) C[i]=(LL)A[i]*B[i]%P, A[i]=B[i]=0;
NTT(C,len,-1);
for(int i=mid+1;i<=R;i++) f[i]=(f[i]+C[i-L-1])%P;
for(int i=L;i<=mid;i++) A[i-L]=(LL)f[i]*fac_inv[i]%P;
for(int i=0;i<=R-L;i++){
if(i<L) B[i]=(LL)2*f[i]*fac_inv[i]%P;
if(L<=i&&i<=mid) B[i]=(LL)f[i]*fac_inv[i]%P;
}
NTT(A,len,1); NTT(B,len,1);
for(int i=0;i<=len-1;i++) C[i]=(LL)A[i]*B[i]%P, A[i]=B[i]=0;
NTT(C,len,-1);
for(int i=mid+1;i<=R;i++) g[i]=(g[i]+C[i-L])%P;
Solve(mid+1,R);
}
int n;
char st[maxn];
int main(){
fac[0]=1; for(int i=1;i<=N;i++) fac[i]=(LL)fac[i-1]*i%P;
inv[1]=1; for(int i=2;i<=N;i++) inv[i]=(LL)(P-P/i)*inv[P%i]%P;
fac_inv[0]=1; for(int i=1;i<=N;i++) fac_inv[i]=(LL)fac_inv[i-1]*inv[i]%P;
scanf("%d%s",&n,st);
for(int i=0;i<=n-1;i++)
if(st[i]=='1') h[i]=(LL)fac_inv[i]*inv[2]%P;
//for(int i=0;i<=n-1;i++) printf("%d ",h[i]); printf("\n");
f[1]=1; Solve(1,n);
for(int i=1;i<=n;i++) printf("%d\n",f[i]);
return 0;
}