[NTT || 多项式求逆] BZOJ4555 [Tjoi2016&Heoi2016]求和

一种方法是直接带入 \[ S(i,j)=\frac{1}{j!}\sum_{k=0}^j(-1)^{j-k}{j\choose k}k^i \]

得到 \[ f(n)=\sum_{i=0}^n\sum_{j=0}^iS(i,j)j!2^j= \sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j(-1)^{j-k} \frac{j!}{k!(j-k)!} k^i 2^j \]

注意到若 \(i<j\) , \(S(i,j)=0\) , \(j\) 的取值范围可以不依赖于 \(i\) ,继续推式子: \[ f(n)= \sum_{i=0}^n \sum_{j=0}^n \sum_{k=0}^j(-1)^{j-k} \frac{j!}{k!(j-k)!} k^i 2^j \\ = \sum_{j=0}^n \sum_{k=0}^j(-1)^{j-k} \frac{j!}{k!(j-k)!} (\sum_{i=0}^n k^i) 2^j \\ =\sum_{j=0}^nj!2^j\sum_{k=0}^j \frac{(\sum_{i=0}^nk^i)}{k!} \frac{(-1)^{j-k}}{(j-k)!} \] 后面是卷积的形式,直接 \(NTT\) 求就好了。

还有一种较优美的方法:

若我们能求得多项式 \(g(i)=\sum_{j=0}^iS(i,j)j!2^j\) ,就能得到答案了。

考虑式子的组合意义,\(S(n,m)\) \(n\) 个不同元素放入 \(m\) 个集合的方案,乘上 \(m!\) 就是带标号集合,乘上 \(2^m\) 就集合2染色。然后写出 \(g(n)\) 的递推式: \[ g(0)=1 \\ g(n)=\sum_{i=1}^n {n\choose i} g(n-i)2 \quad (n\ge1) \] 注意到这刚好是个生成函数相乘的形式,

\(H(x)= \frac{0}{0!}x^0+\frac{2}{1!}x^1+\frac{2}{2!}x^2+\frac{2}{3!}x^3... \quad G(n)=\sum_{i=0}^n \frac{g(i)}{i!}x^i\)

然后就好了: \[ G=H*G+1 \Rightarrow G=\frac{1}{1-H} \] 求逆即可。

求逆的代码:

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=270005,P=998244353,P_g=3;
typedef long long LL;
LL Pow(LL a,int b,int P){
LL res=1;
for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;
return res;
}
int rev[maxn];
int get_rev(int n){
int t=0; while((1<<t)<n) t++;
rev[0]=0; 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(i<rev[i]) swap(a[i],a[rev[i]]);
for(int m=2;m<=n;m<<=1){
int wm=Pow(P_g,(P-1)/m,P); if(k==-1) wm=Pow(wm,P-2,P);
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,P);
for(int i=0;i<=n-1;i++) a[i]=(LL)a[i]*t%P;
}
}
void Inv(int a[],int b[],int n){
static int tmp[maxn];
if(n==1){
b[0]=Pow(a[0],P-2,P); b[1]=0;
return;
}
Inv(a,b,n>>1);
for(int i=0;i<=n-1;i++) tmp[i]=a[i], tmp[i+n]=0;
get_rev(n<<1);
NTT(tmp,n<<1,1); NTT(b,n<<1,1);
for(int i=0;i<=(n<<1)-1;i++) b[i]=((LL)b[i]*2%P+P-(LL)b[i]*b[i]%P*tmp[i]%P)%P;
NTT(b,n<<1,-1);
for(int i=n;i<=(n<<1)-1;i++) b[i]=0;
}
int n,H[maxn],G[maxn],ans;
LL fac[maxn],inv[maxn],fac_inv[maxn];
int main(){
freopen("bzoj4555.in","r",stdin);
freopen("bzoj4555.out","w",stdout);
scanf("%d",&n);
int N=1; while(N<=n) N<<=1;
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;
H[0]=1; for(int i=1;i<=N-1;i++) H[i]=(LL)(P-2)*fac_inv[i]%P;
Inv(H,G,N); //printf("G: ");
for(int i=0;i<=N-1;i++) G[i]=(LL)G[i]*fac[i]%P; // printf("%d ",G[i]);
for(int i=0;i<=n;i++) ans=(ans+G[i])%P;
printf("%d\n",ans);
return 0;
}