bzoj 4555[HEOI 2016/TJOI 2016]求和
タイトルの説明
2016年、佳媛姉は第2類のスターリング数を勉強したばかりで、とても楽しかったです.彼はこのような関数の値を計算したいと思っています.
f(n)=∑i=0n∑j=0iS(i,j)×j!×2j f ( n ) = ∑ i = 0 n ∑ j = 0 i S ( i , j ) × j ! × 2 j
S(i,j)は第2類のスターリング数を示しています.彼を助けることができますか.
f(n)を出力する.結果が大きいため、出力f(n)対998244353(7× 17 × 223+1)型取りの結果でOK
Solution
まずjの列挙上界は直接nになることができる.なぜなら、i∑i=0n∑j=0n2j×j!∑k=0j(−1)k×C(j,k)×(j−k)i ∑ i = 0 n ∑ j = 0 n 2 j × j ! ∑ k = 0 j ( − 1 ) k × C ( j , k ) × ( j − k ) i
コンビネーション数も取り外すことができます.
∑i=0n∑j=0n2j×j!∑k=0j(−1)kk!×(j−k)i(j−k)! ∑ i = 0 n ∑ j = 0 n 2 j × j ! ∑ k = 0 j ( − 1 ) k k ! × ( j − k ) i ( j − k ) !
一番外側のΣを一番奥に引くと
∑j=0n2j×j!∑k=0j(−1)kk!×∑ni=0(j−k)i(j−k)! ∑ j = 0 n 2 j × j ! ∑ k = 0 j ( − 1 ) k k ! × ∑ i = 0 n ( j − k ) i ( j − k ) !
後半は実際にボリュームで、iのΣは実際には等比数列の和で、NTTはすぐに解くといいです
Code
2016年、佳媛姉は第2類のスターリング数を勉強したばかりで、とても楽しかったです.彼はこのような関数の値を計算したいと思っています.
f(n)=∑i=0n∑j=0iS(i,j)×j!×2j f ( n ) = ∑ i = 0 n ∑ j = 0 i S ( i , j ) × j ! × 2 j
S(i,j)は第2類のスターリング数を示しています.彼を助けることができますか.
f(n)を出力する.結果が大きいため、出力f(n)対998244353(7× 17 × 223+1)型取りの結果でOK
Solution
まずjの列挙上界は直接nになることができる.なぜなら、i
コンビネーション数も取り外すことができます.
∑i=0n∑j=0n2j×j!∑k=0j(−1)kk!×(j−k)i(j−k)! ∑ i = 0 n ∑ j = 0 n 2 j × j ! ∑ k = 0 j ( − 1 ) k k ! × ( j − k ) i ( j − k ) !
一番外側のΣを一番奥に引くと
∑j=0n2j×j!∑k=0j(−1)kk!×∑ni=0(j−k)i(j−k)! ∑ j = 0 n 2 j × j ! ∑ k = 0 j ( − 1 ) k k ! × ∑ i = 0 n ( j − k ) i ( j − k ) !
後半は実際にボリュームで、iのΣは実際には等比数列の和で、NTTはすぐに解くといいです
Code
#include std:: swap(a[rev[i]],a[i]);
for (int i=1;i2) {
int wn;
if (f==1) wn=ksm(G,(MOD-1)/i/2);
else wn=ksm(G,MOD-1-(MOD-1)/i/2);
for (int j=0;j2) {
int w=1;
for (int k=0;kint u=a[j+k],v=(LL)a[j+k+i]*w%MOD;
a[j+k]=(u+v)%MOD;
a[j+k+i]=(u-v)%MOD;
w=(LL)w*wn%MOD;
}
}
}
if (f==-1) rep(i,0,len-1) a[i]=(LL)a[i]*ny%MOD;
}
void pre_work(int n) {
fac[0]=1; rep(i,1,n) fac[i]=(LL)fac[i-1]*i%MOD;
inv[0]=1; rep(i,1,n) inv[i]=ksm(fac[i],MOD-2);
for (len=1;len<=n*2;len<<=1,lg++);
rep(i,0,len-1) rev[i]=(rev[i/2]/2)|((i&1)<1));
ny=ksm(len,MOD-2);
}
int main(void) {
int n; scanf("%d",&n); pre_work(n);
rep(i,0,n) a[i]=((i&1)?(-1):(1))*inv[i];
a[0]=1; b[0]=1; b[1]=n+1;
rep(i,2,n) b[i]=(LL)((LL)(ksm(i,n+1)-1)*inv[i]%MOD*ksm(i-1,MOD-2)%MOD+MOD)%MOD;
rep(i,0,n) printf("%d %d
", a[i],b[i]);
DFT(a,1); DFT(b,1);
rep(i,0,len-1) a[i]=(LL)a[i]*b[i]%MOD;
DFT(a,-1);
LL ans=0; rep(i,0,n) ans=(ans+(LL)a[i]*fac[i]%MOD*ksm(2,i)%MOD)%MOD;
printf("%lld
", (ans+MOD)%MOD);
return 0;
}