bzoj4555（斯特林数，NTT）

De ion
在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

solution:
要求∑i=0n​∑j=0i​{ji​}∗2j∗j!
可以等价于求∑i=0n​∑j=0n​{jj​}∗2j∗j!
后面推式子就行了
i=0∑n​j=0∑n​2j∗j!∗S(i,j)=i=0∑n​j=0∑n​2j∗k=0∑j​(−1)kCjk​∗(j−k)i=i=0∑n​j=0∑n​2j∗j!k=0∑j​k!(−1)k​∗(j−k)!(j−k)i​=j=0∑n​2j∗j!k=0∑j​k!(−1)k​∗(j−k)!∑i=0n​(j−k)i​
后面那个式子是个卷积的形式
直接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 =  k[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-

					

						
继续阅读与本文标签相同的文章
						

														无标签