【TJOI/HEOI2016】求和

這題好難啊！！

斯特林數(shù)+NTT。

首先我們將第二類斯特林數(shù)用容斥展開，具體原理不解釋了。

\(\displaystyle S(i,j)=\frac{1}{j!}\sum_{k=0}^{j}(-1)^{k}C_j^k(j-k)^i=\sum_{k=0}^{j}\frac{(-1)^k}{k!}\cdot\frac{(j-k)^i}{(j-k)!}\)。

我們交換一下\(\sum\)的順序：

\(\displaystyle f(n)=\sum_{j=0}^{n}2^jj!\sum_{i=0}^{n}S(i,j)\)。這里\(i\)從0開始枚舉是沒有問題的，因為\(j>i時，S(i,j)=0\)。

將斯特林數(shù)展開：
\[ \displaystyle f(n)=\sum_{j=0}^{n}2^jj!\sum_{i=0}^{n}\sum_{k=0}^j\frac{(-1)^k}{k!}\cdot\frac{(j-k)^i}{(j-k)!}\\ =\sum_{j=0}^{n}2^jj!\sum_{k=0}^j\frac{(-1)^k}{k!}\sum_{i=0}^n\frac{(j-k)^i}{(j-k)!} \]
很容易看出，最后一個\(\sum\)是一個等比數(shù)列求和。

于是我們設(shè)\(g(i)=\frac{i^{n+1}-1}{(i-1)*i!}，特別地，g(0)=1,g(1)=n+1\)。

于是\(\displaystyle f(n)=\sum_{j=0}^{n}2^jj!\sum_{k=0}^j\frac{(-1)^k}{k!}g(j-k)\)

我們又設(shè)\(h(i)=\frac{(-1)^i}{i!}\)，則\(\displaystyle f(n)=\sum_{j=0}^{n}2^jj!\sum_{k=0}^jh(k)g(j-k)\)

\(\displaystyle \sum_{k=0}^jh(k)g(j-k)\)是個卷積，可以用NTT來計算。

代碼：

#include<bits/stdc++.h> #define ll long long #define mod 998244353 #define N 200005using namespace std; inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n; ll fac[N],inv[N]; ll ksm(ll t,ll x) {ll ans=1;for(;x;x>>=1,t=t*t%mod)if(x&1) ans=ans*t%mod;return ans; } ll a[N<<2],b[N<<2],q[N]; const ll g=3; ll tem[N<<2]; int rev(int x,int len) {int ans=0;for(;len;len--,x>>=1) ans=ans<<1|x&1;return ans; }void NTT(ll *a,int x,int flag) {int n=1<<x;for(int i=0;i<n;i++) if(i<rev(i,x)) swap(a[i],a[rev(i,x)]); tem[0]=1;for(int s=1;s<=x;s++) {int len=1<<s,mid=len>>1;ll w=flag==1?ksm(g,(mod-1)/len):ksm(g,mod-1-(mod-1)/len);for(int i=1;i<mid;i++) tem[i]=tem[i-1]*w%mod;for(int i=0;i<n;i+=len) {for(int j=0;j<mid;j++) {ll u=a[i+j];ll v=tem[j]*a[i+j+mid]%mod;a[i+j]=(u+v)%mod;a[i+j+mid]=(u-v+mod)%mod;}}}if(flag==-1) {ll inv=ksm(n,mod-2);for(int i=0;i<n;i++) a[i]=a[i]*inv%mod;} }int bl[1000]; int main() {n=Get();fac[0]=1;for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;inv[n]=ksm(fac[n],mod-2);for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;int flag=1;for(int i=0;i<=n;i++,flag*=-1) {if(flag==1) a[i]=inv[i];else a[i]=(mod-inv[i])%mod;}q[0]=1;q[1]=n+1;for(int i=2;i<=n;i++) {q[i]=((ksm(i,n+1)-1)*ksm(i-1,mod-2)%mod+mod)%mod;}for(int i=0;i<=n;i++) b[i]=q[i]*inv[i]%mod;int x=0;for(int len=n<<2;len;len>>=1,x++);NTT(a,x,1),NTT(b,x,1);for(int i=0;i<(1<<x);i++) a[i]=a[i]*b[i]%mod;NTT(a,x,-1);ll ans=0;ll p=1;for(int i=0;i<=n;i++) {(ans+=p*fac[i]%mod*a[i]%mod)%=mod;p=(p<<1)%mod;}cout<<ans;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/hchhch233/p/10009226.html

總結(jié)

以上是生活随笔為你收集整理的【TJOJI\HEOI2016】求和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。