[倍增NTT] HHHOJ#290. 「湖南省队集训2018 Day1」Or

\(f(i)\) 表示或和有 \(i\)\(1\) 的方案数,则容易写出

\[ f(i)=\sum_{j=0}^{i-1} f(j){i\choose j}2^j \\ \frac{f(i)}{i!}= \sum_{j=0}^{i-1} 2^j\frac{f(j)}{j!}\frac{1}{(i-j)!} \] 我们需要这样转移 \(n\) 次。

\(F(i)=\frac{f(i)}{i!}\) , \(G(i)=\frac{1}{i!}\)\(H(i)=2^i\) ,显然我们需要求的就是 \[ F=((((H * G)\cdot H)*G) \cdot H)*G \cdots \] 看上去就是要倍增,可以发现 \(2^i=2^j2^{i-j}\) ,即 \(H(i)H(j)=H(i+j)\)

所以有 \((A*B) \cdot H =(A \cdot H)*(B \cdot H)\)

然后就能倍增了... \[ F=(H^{n-1}G)*(H^{n-2}G)*\dots *(H^2G)*(HG)*G \\ [2n]F=([n]F \cdot h^n)*[n]F \]

写多项式题要注意次数大小......

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=70005,P=998244353;
int rev[maxn];
void get_rev(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);
}
LL Pow(LL a,LL b){
LL res=1;
for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;
return res;
}
void NTT(int a[],int n,int k){
for(int i=0;i<=n-1;i++) if(i<rev[i]) swap(a[i],a[rev[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 w=1,t0,t1;
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 n,K,ans,N,f[maxn],g[maxn],A[maxn],B[maxn];
LL fac[maxn],fac_inv[maxn],inv[maxn];
void Merge(int a[],int b[],int w){
for(int i=0;i<=K;i++) A[i]=(LL)a[i]*Pow(2,(LL)i*w%(P-1))%P, B[i]=b[i];
for(int i=K+1;i<=N-1;i++) A[i]=B[i]=0;
NTT(A,N,1); NTT(B,N,1);
for(int i=0;i<=N-1;i++) A[i]=(LL)A[i]*B[i]%P;
NTT(A,N,-1);
for(int i=0;i<=K;i++) a[i]=A[i];
}
LL C(int n,int m){
return fac[n]*fac_inv[m]%P*fac_inv[n-m]%P;
}
int main(){
freopen("hhhoj290.in","r",stdin);
freopen("hhhoj290.out","w",stdout);
scanf("%d%d",&n,&K);
N=1; while(N<((K+1)<<1)) N<<=1; get_rev(N);
fac[0]=1; for(int i=1;i<=N;i++) fac[i]=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]=fac_inv[i-1]*inv[i]%P;
f[0]=1; g[0]=0; for(int i=1;i<=K;i++) g[i]=fac_inv[i];
for(int w=1;n;n>>=1,Merge(g,g,w),w<<=1)
if(n&1) Merge(f,g,w);
for(int i=0;i<=K;i++) (ans+=(LL)f[i]*fac[i]%P*C(K,i)%P)%=P;
printf("%d\n",ans);
return 0;
}