Description
在2016年,佳媛姐姐剛剛學習了第二類斯特林數,非常開心。
現在他想計算這樣一個函數的值:f(n)=ΣiΣj s(i,j)*2^j* j!
S(i, j)表示第二類斯特林數,遞推公式為:
S(i, j) = j ∗ S(i − 1, j) + S(i − 1, j − 1), 1 <= j <= i − 1。
邊界條件為:S(i, i) = 1(0 <= i), S(i, 0) = 0(1 <= i)
你能幫幫他嗎?
Input
輸入隻有一個正整數
Output
輸出f(n)。由于結果會很大,輸出f(n)對998244353(7 × 17 × 223 + 1)取模的結果即可。1 ≤ n ≤ 100000
Sample Input
3
Sample Output
87
s o l u t i o n solution solution:
要求 ∑ i = 0 n ∑ j = 0 i { i j } ∗ 2 j ∗ j ! \sum_{i=0}^n\sum_{j=0}^i \left\{ i \atop j \right\} * 2^j *j! ∑i=0n∑j=0i{ji}∗2j∗j!
可以等價于求 ∑ i = 0 n ∑ j = 0 n { j j } ∗ 2 j ∗ j ! \sum_{i=0}^n\sum_{j=0}^n \left\{ j \atop j \right\} * 2^j *j! ∑i=0n∑j=0n{jj}∗2j∗j!
後面推式子就行了
∑ i = 0 n ∑ j = 0 n 2 j ∗ j ! ∗ S ( i , j ) = ∑ i = 0 n ∑ j = 0 n 2 j ∗ ∑ k = 0 j ( − 1 ) k C j k ∗ ( j − k ) i = ∑ i = 0 n ∑ j = 0 n 2 j ∗ j ! ∑ k = 0 j ( − 1 ) k k ! ∗ ( 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 ) ! \sum_{i=0}^n\sum_{j=0}^n2^j*j!*S(i,j)\\ =\sum_{i=0}^n\sum_{j=0}^n 2^j*\sum_{k=0}^j(-1)^kC_j^k*(j-k)^i\\ =\sum_{i=0}^n\sum_{j=0}^n 2^j*j!\sum_{k=0}^j\frac{(-1)^k}{k!}*\frac{(j-k)^i}{(j-k)!}\\ =\sum_{j=0}^n2^j*j!\sum_{k=0}^j\frac{(-1)^k}{k!}*\frac{\sum_{i=0}^n(j-k)^i}{(j-k)!} i=0∑nj=0∑n2j∗j!∗S(i,j)=i=0∑nj=0∑n2j∗k=0∑j(−1)kCjk∗(j−k)i=i=0∑nj=0∑n2j∗j!k=0∑jk!(−1)k∗(j−k)!(j−k)i=j=0∑n2j∗j!k=0∑jk!(−1)k∗(j−k)!∑i=0n(j−k)i
後面那個式子是個卷積的形式
直接 N T T NTT NTT就行了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define rept(i,x) for(int i = linkk[x];i;i = e[i].n)
#define P pair<int,int>
#define Pil pair<int,ll>
#define Pli pair<ll,int>
#define Pll pair<ll,ll>
#define pb push_back
#define pc putchar
#define mp make_pair
#define file(k) memset(k,0,sizeof(k))
#define ll long long
int rd()
{
int num = 0;char c = getchar();bool flag = true;
while(c < '0'||c > '9') {if(c == '-') flag = false;c = getchar();}
while(c >= '0' && c <= '9') num = num*10+c-48,c = getchar();
if(flag) return num;else return -num;
}
const int p = 998244353,g = 3;
inline int ksm(int a,int x){int now = 1;for(;x;x>>=1,a=1ll*a*a%p)if(x&1)now=1ll*now*a%p;return now;}
inline int calc(int a,int b){return (a+=b)>=p?a-=p:a;}
inline int del(int a,int b){return (a-=b)<0?a+=p:a;}
inline int mul(int a,int b){return 1ll*a*b%p;}
int n;
int r[401000],w[401000];
int fac[101000],inv[101000];
int a[401000],b[401000];
void ntt(int *a,int f,int flen)
{
w[0] = 1;
rep(i,0,flen-1) r[i] = (r[i>>1]>>1) | ((i&1)?flen/2:0);
rep(i,0,flen-1) if(i < r[i]) swap(a[i],a[r[i]]);
for(int len = 2;len <= flen;len<<=1)
{
int wn = ksm(g,(p-1)/len);
if(f == -1) wn = ksm(wn,p-2);
rep(i,1,len-1) w[i] = mul(w[i-1],wn);
for(int st = 0;st < flen;st += len)
rep(i,0,len/2-1)
{
int x = a[st+i],y = mul(w[i],a[st+len/2+i]);
a[st+i] = calc(x,y);
a[st+len/2+i] = del(x,y);
}
}
if(f == -1){int inv = ksm(flen,p-2);rep(i,0,flen-1) a[i] = mul(a[i],inv);}
}
int main()
{
n = rd();fac[0] = inv[0] = 1;rep(i,1,100000) fac[i] = mul(fac[i-1],i),inv[i] = ksm(fac[i],p-2);
rep(i,0,n)
{
a[i] = mul( (i&1)?p-1:1 , inv[i] );
int k;
if(i == 0) k = 1;
else if(i == 1) k = n+1;
else k = mul(del(ksm(i,n+1),1),ksm(i-1,p-2));
b[i] = mul(k,inv[i]);
}
int flen = 1;
while(flen <= 2*n+1) flen <<= 1;
ntt(a,1,flen);ntt(b,1,flen);
rep(i,0,flen-1) a[i] = mul(a[i],b[i]);
ntt(a,-1,flen);
int ans = 0;
rep(i,0,n)
{
int v = mul(ksm(2,i),fac[i]);
ans = calc(ans,mul(v,a[i]));
}
printf("%d\n",ans);
return 0;
}