[HEOI2016/TJOI2016] 求和
程序员文章站
2022-10-08 15:33:15
推式子 $$ f(n)=\sum_{i=0}^n\sum_{j=0}^iS(i,j)\times 2^j\times (j!)\\ =\sum_{i=0}^n\sum_{j=0}^nS(i,j)\times 2^j\times (j!)=\sum_{i=0}^n2^i\times (i!)\sum_ ......
推式子
\[ f(n)=\sum_{i=0}^n\sum_{j=0}^is(i,j)\times 2^j\times (j!)\\ =\sum_{i=0}^n\sum_{j=0}^ns(i,j)\times 2^j\times (j!)=\sum_{i=0}^n2^i\times (i!)\sum_{j=0}^n s(j,i) \]
注意到
\[ s(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^ic(m,i)(m-i)^n\\ =\sum_{i=0}^m\frac{(-1)^i\times (m-i)^n}{i!\times (m-i)!} \]
带入得
\[ f(n)=\sum_{i=0}^n2^i\times i!\sum_{j=0}^n\sum_{k=0}^i\frac{(-1)^k\times(i-k)^j}{k!\times (i-k)!}\\ =\sum_{i=0}^n2^i\times i!\sum_{k=0}^i\frac{(-1)^k}{k!}\frac{\sum_{j=0}^n(i-k)^j}{(i-k)!}\\ \]
注意,其中的\(0^0=1\)而非“未定义的操作”:离散、计数问题大都如此,可以参考。然后就是很显然的卷积。
#include <bits/stdc++.h> #define ll long long using namespace std; const int n=4e5+10; const int mod=998244353; inline int qpow(ll x,ll y) { int c=1; for(; y; y>>=1,x=x*x%mod) if(y&1) c=x*c%mod; return c; } int p,pl,rev[n]; inline void ntt_init(int sum) { for(p=1,pl=0; p<sum;) p<<=1,pl++; for(int i=0; i<p; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(pl-1)); } inline void ntt(int*a,int tp) { for(int i=0; i<p; ++i) if(i<rev[i]) swap(a[i],a[rev[i]]); for(int m=1; m<p; m<<=1) { ll wm=qpow(3,(mod-1)/(m<<1)); if(tp<0) wm=qpow(wm,mod-2); for(int i=0; i<p; i+=(m<<1)) { ll w=1,tmp; for(int j=0; j<m; ++j,w=w*wm%mod) { tmp=w*a[i+j+m]%mod; a[i+j+m]=(a[i+j]-tmp+mod)%mod; a[i+j]=(a[i+j]+tmp)%mod; } } } if(tp<0) { ll tmp=qpow(p,mod-2); for(int i=0; i<p; ++i) a[i]=tmp*a[i]%mod; } } int n,f[n],g[n]; ll fc[n],fv[n]; int main() { scanf("%d",&n); fc[0]=fc[1]=fv[0]=fv[1]=1; for(int i=2; i<=n; ++i) fv[i]=fv[mod%i]*(mod-mod/i)%mod; for(int i=2; i<=n; ++i) fv[i]=fv[i-1]*fv[i]%mod,fc[i]=fc[i-1]*i%mod; f[0]=1,f[1]=mod-1,g[0]=1,g[1]=n+1; for(int i=2; i<=n; ++i) { f[i]=fv[i]*((i&1)?mod-1:1)%mod; g[i]=fv[i]*((qpow(i,n+1)-1+mod)%mod)%mod*qpow(i-1,mod-2)%mod; } //for(int i=0; i<=n; ++i) printf("%d ",f[i]); printf("\n"); //for(int i=0; i<=n; ++i) printf("%d ",g[i]); printf("\n"); ntt_init(n+n+2); ntt(f,1); ntt(g,1); //for(int i=0; i<p; ++i) printf("%d ",f[i]); printf("\n"); //for(int i=0; i<p; ++i) printf("%d ",g[i]); printf("\n"); for(int i=0; i<p; ++i) f[i]=1ll*f[i]*g[i]%mod; ntt(f,-1); ll p=1,sum=0; for(int i=0; i<=n; ++i) { sum=(sum+p*fc[i]%mod*f[i]%mod)%mod; p=p*2%mod; } printf("%lld\n",sum); return 0; }
写代码是别把p和mod弄混了……
上一篇: Java开发桌面程序学习(五)——文件选择器和目录选择器的使用
下一篇: 小程序实现列表点赞功能