bzoj4555 [Tjoi2016Heoi2016]求和（NTT）

NTT）"/>

bzoj4555 [Tjoi2016Heoi2016]求和（NTT）

Description
在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。
现在他想计算这样一个函数的值:

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

分析:
这比那道序列计数友善多了

一看到这条限制，
998244353，yg=3
NTT啊
确实，那我们现在的任务就是找卷积

但是这个第二类斯特林数好烦人啊
ta到底是什么呢
第二类斯特林数S(n,m)定义为把n个元素划分成m个无序集合的方案数
根据这个定义我们不难写出递推式
设状态S(i,j)，讨论第i个元素是否单独一个集合
若单独一个集合，则方案数等价于S(i-1,j-1)
若不是单独一个集合，则他可以在之前任意j个集合里，方案为S(i-1,j)*j
这样我们得到式子S(i,j)=S(i-1,j-1)+S(i-1,j)*j
递推的时间复杂度是O(n^2)的

其实关键是知道斯特林数的通项公式

把通项公式带入化简一下
经过一系列的移项约分

我天，有除法，
需要线性求逆元
看来我们需要复习一下数论知识了

那我们就现在就需要在柿子（式子）上开刀了

tip

熟练运用不同的数学知识
一道题可能主体算法是NTT，
但是实际上在维护小东西的时候可能需要其他的姿势

板子打不对，

其他都jj， (╯‵□′)╯︵┻━┻

循环的时候注意，
只要循环的是数组下标，

一定要从0开始

——从0开始的~~异世界生活~~NTT循环

这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long longusing namespace std;const ll mod=998244353;
const int N=400005;
ll mi[N],jc[N],inv[N],f[N],g[N];
int n,fn;ll KSM(ll a,ll b,ll p)
{ll t=1;a=(a+mod)%mod;   //while (b){if (b&1) t=(t*a)%p;b>>=1;a=(a*a)%p;}return t%p;
}void NTT(ll *a,int n,int opt)
{int i,j=0,k;for (i=0;i<n;i++){if (i>j) swap(a[i],a[j]);for (int l=n>>1;(j^=l)<l;l>>=1);}for (i=1;i<n;i<<=1)   ///{ll wn=KSM(3,(mod-1)/(i<<1),mod);  //(mod-1)/(i<<1)int m=i<<1;for (j=0;j<n;j+=m){ll w=1;for (k=0;k<i;k++,w=(w*wn)%mod){ll z=(a[j+k+i]*w)%mod;a[j+i+k]=(a[j+k]-z+mod)%mod;a[j+k]=(a[j+k]+z)%mod;}}}if (opt==-1) reverse(a+1,a+n);  //
}int main()
{scanf("%d",&n);inv[0]=inv[1]=1;jc[0]=1; mi[0]=1;for (int i=1;i<=n;i++) mi[i]=(mi[i-1]*2)%mod;   //2的若干次幂 for (int i=1;i<=n;i++) jc[i]=(jc[i-1]*i)%mod;for (int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;for (int i=1;i<=n;i++) inv[i]=(inv[i-1]*inv[i])%mod;   //阶乘逆元 for (int i=0;i<=n;i++)if (i&1) f[i]=-inv[i];   //(-1)^k/k!else f[i]=inv[i];g[0]=1; g[1]=n+1;   for (int i=2;i<=n;i++)   //sigma/(j-k)!{ll t=(KSM(i,n+1,mod)-1+mod)%mod;   //等差数列公式 t=t*KSM(i-1,mod-2,mod)%mod;    //(a^(n+1)-1)/(n-1) g[i]=(t*inv[i])%mod;}fn=1;while (fn<=n*2+1) fn<<=1;NTT(f,fn,1); NTT(g,fn,1);for (int i=0;i<=fn;i++) f[i]=(f[i]*g[i])%mod;NTT(f,fn,-1);   //IDNTll t=KSM(fn,mod-2,mod);for (int i=0;i<=fn;i++) f[i]=(f[i]*t)%mod;   //IDNT不要忘了/nll ans=0;for (int i=0;i<=n;i++) ans=(ans+f[i]*jc[i]%mod*mi[i]%mod)%mod;printf("%lld",ans); return 0;
}