BZOJ 4555(第二类斯特林数+NTT)

传送门

解题思路

数学题，推式子。求\(f(n)=\sum\limits_{i=0}^n\sum\limits_{j=0}^iS(i,j)2^jj!\)

首先可以把\(j\)往前提：

\[f(n)=\sum\limits_{j=0}^n2^jj!\sum\limits_{i=0}^nS(i,j)
\]

然后把斯特林数按照通项展开：

\[f(n)=\sum\limits_{j=0}^n2^jj!\sum\limits_{i=0}^n\tfrac{1}{m!}\sum\limits_{k=0}^j(-1)^kC(j,k)(j-k)^i
\]

众所周知，里面那个玩意可以写成卷积的形式：

\[f(n)=\sum\limits_{j=0}^n2^jj!\sum\limits_{k=0}^j\tfrac{(-1)^k}{k!}\tfrac{\sum\limits_{i=0}^n(j-k)^i}{(j-k)!}
\]

继续发现里面的第二项的分子是等比数列求和，设\(A(x)=\tfrac{(-1)^x}{k!}\)，\(B(x)=\tfrac{\sum\limits_{i=0}^nx^i}{x!}\)，把\(B\)里面的等比数列求和：

\[B(x)=\tfrac{i^{n+1}-1}{i!(i-1)}
\]

突然发现似乎所有东西都能求了，直接上\(NTT\)求卷积，再扫一遍就行了。时间复杂度\(O(nlogn)\)。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=100005;

const int MOD=998244353;

typedef long long LL;

int n,A[N<<2],B[N<<2],rev[N<<2];

int fac[N],inv[N],limit=1,ans;

inline int fast_pow(int x,int y){

	int ret=1;

	for(;y;y>>=1){

		if(y&1) ret=(LL)ret*x%MOD;

		x=(LL)x*x%MOD;

	}

	return ret;

}

inline int add(int x){

	if(x<0) x+=MOD;if(x>=MOD) x-=MOD;return x;

}

inline void NTT(int *f,int type){

	for(int i=0;i<limit;i++)

		if(i<rev[i]) swap(f[i],f[rev[i]]);

	int Wn,w,tmp;

	for(int i=2;i<=limit;i<<=1){

		Wn=fast_pow(3,(MOD-1)/i);

		for(int j=0,len=i>>1;j<limit;j+=i){w=1;

			for(int k=j;k<j+len;k++){

				tmp=(LL)w*f[k+len]%MOD;f[k+len]=add(f[k]-tmp);

				f[k]=add(f[k]+tmp);w=(LL)w*Wn%MOD;

			}

		}

	}

	if(type==1) return ;

	int INV=fast_pow(limit,MOD-2);

	reverse(f+1,f+limit);

	for(int i=0;i<limit;i++) f[i]=(LL)f[i]*INV%MOD;

}	

int main(){

	scanf("%d",&n);fac[0]=B[0]=1;B[1]=n+1;

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

	inv[n]=fast_pow(fac[n],MOD-2);

	for(int i=n-1;~i;i--) inv[i]=(LL)inv[i+1]*(i+1)%MOD;

	while(limit<=2*n) limit<<=1;

	for(int i=0;i<limit;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(limit>>1):0);

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

	for(int i=2;i<=n;i++)

		 B[i]=(LL)(fast_pow(i,n+1)-1)*inv[i]%MOD*fast_pow(i-1,MOD-2)%MOD;

	NTT(A,1);NTT(B,1);

	for(int i=0;i<limit;i++) A[i]=(LL)A[i]*B[i]%MOD;

	NTT(A,-1);int now=1;

	for(int i=0;i<=n;i++){

		ans=(ans+(LL)fac[i]*now%MOD*A[i]%MOD)%MOD;

		now<<=1;if(now>=MOD) now-=MOD;

	}

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

	return 0;

}

巴特西

BZOJ 4555(第二类斯特林数+NTT)

解题思路

代码

最新文章

热门文章