【BZOJ4555】求和（第二类斯特林数，组合数学，NTT）

时间：2023-03-09 13:27:34
【BZOJ4555】求和（第二类斯特林数，组合数学，NTT）

【BZOJ4555】求和（第二类斯特林数，组合数学，NTT）

题面

BZOJ

题解

推推柿子

\[\sum_{i=0}^n\sum_{j=0}^iS(i,j)·j!·2^j
\]

\[=\sum_{i=0}^n\sum_{j=0}^nS(i,j)·j!·2^j
\]

\[=\sum_{i=0}^n\sum_{j=0}^nj!·2^j(\frac{1}{j!}\sum_{k=0}^j(-1)^k·C_j^k·(j-k)^i)
\]

\[=\sum_{j=0}^n2^j\sum_{k=0}^j(-1)^k·C_j^k·\sum_{i=0}^n(j-k)^i
\]

\[=\sum_{j=0}^n2^j\sum_{k=0}^j(-1)^k·\frac{j!}{k!(j-k)!}·\sum_{i=0}^n(j-k)^i
\]

\[=\sum_{j=0}^n2^j·j!\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{\sum_{i=0}^n(j-k)^i}{(j-k)!}
\]

上面是一个等比数列求和

\[=\sum_{j=0}^n2^j·j!\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{(j-k)^{n+1}-1}{(j-k)!(j-k-1)}
\]

发现后面的东西是一个卷积

可以\(O(nlogn)\)预处理

然后就可以\(O(n)\)算答案了

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MOD 998244353

#define MAX 500000

const int pr=3;

const int phi=MOD-1;

int fpow(int a,int b)

{

	int s=1;

	while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}

	return s;

}

int r[MAX],N,M,l;

int jc[MAX],inv[MAX];

int a[MAX],b[MAX],S[MAX];

void NTT(int *P,int opt)

{

	for(int i=0;i<N;++i)if(i<r[i])swap(P[i],P[r[i]]);

	for(int i=1;i<N;i<<=1)

	{

		int W=fpow(pr,phi/(i<<1));

		for(int p=i<<1,j=0;j<N;j+=p)

		{

			int w=1;

			for(int k=0;k<i;++k,w=1ll*w*W%MOD)

			{

				int X=P[j+k],Y=1ll*w*P[i+j+k]%MOD;

				P[j+k]=(X+Y)%MOD;P[i+j+k]=((X-Y)%MOD+MOD)%MOD;

			}

		}

	}

	if(opt==-1)reverse(&P[1],&P[N]);

}

void Work()

{

	M+=N;

	for(N=1;N<=M;N<<=1)++l;

	for(int i=0;i<N;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

	NTT(a,1);NTT(b,1);

	for(int i=0;i<N;++i)a[i]=1ll*a[i]*b[i]%MOD;

	NTT(a,-1);

	for(int i=0,inv=fpow(N,MOD-2);i<N;++i)a[i]=1ll*a[i]*inv%MOD;

}

int n,ans;

int main()

{

	scanf("%d",&n);

	N=M=n;

	jc[0]=inv[0]=1;

	for(int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%MOD;

	for(int i=1;i<=n;++i)inv[i]=fpow(jc[i],MOD-2);

	for(int i=0;i<=n;++i)a[i]=(i&1)?-1:1;

	for(int i=0;i<=n;++i)a[i]=(1ll*a[i]*inv[i]%MOD+MOD)%MOD;

	for(int i=2;i<=n;++i)b[i]=(fpow(i,n+1)-1+MOD)%MOD;

	for(int i=2;i<=n;++i)b[i]=1ll*b[i]*inv[i]%MOD;

	for(int i=2;i<=n;++i)b[i]=1ll*b[i]*fpow(i-1,MOD-2)%MOD;

	b[0]=1;b[1]=n+1;

	Work();

	for(int i=0,p=1;i<=n;++i,p=(p+p)%MOD)ans=(ans+1ll*jc[i]*p%MOD*a[i]%MOD)%MOD;

	printf("%d\n",ans);

	return 0;

}

相关文章