bzoj 4555 [Tjoi2016&Heoi2016]求和

bzoj 4555 [Tjoi2016&Heoi2016]求和

​​ 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 HINT

Source

第二类斯特林数公式: 将n个物品放入m个无序的盒子中不允许为空 求方案数 Smn=1m!∑k=0m(−1)kCkm∗(m−k)n S n m = 1 m ! ∑ k = 0 m ( − 1 ) k C m k ∗ ( m − k ) n 首先将盒子有序 最后/(m!) 然后考虑容斥 表示从m个中钦定K个空的位置 然后剩下的随便放 这样的答案就是至少K个空位置的答案 那显然0个空位置是答案 那么就至少0-至少1+至少2 …这样就写出了这样一个通项公式 首先将斯特林数带入公式 Ans=∑i=0n∑j=0iSi,j×2j×(j!) A n s = ∑ i = 0 n ∑ j = 0 i S i , j × 2 j × ( j ! ) Ans=∑i=0n∑j=0j1j!∑k=0j(−1)k×j!(j−k)!×k!×(i−k)i×2j×(j!) A n s = ∑ i = 0 n ∑ j = 0 j 1 j ! ∑ k = 0 j ( − 1 ) k × j ! ( j − k ) ! × k ! × ( i − k ) i × 2 j × ( j ! ) 变换求和符号将其提到前面

Ans=∑j=0n(j!)×2j∑k=0j(−1)k×1k!∑i=jn×(j−k)i(j−k)! A n s = ∑ j = 0 n ( j ! ) × 2 j ∑ k = 0 j ( − 1 ) k × 1 k ! ∑ i = j n × ( j − k ) i ( j − k ) ! 所以可以设 ai=(−1)ii! a i = ( − 1 ) i i ! bi=∑j=0niji! b i = ∑ j = 0 n i j i ! 然后分别带入 Ans=∑j=0n(j!)×2j∑k=0ja[k]×b[j−k] A n s = ∑ j = 0 n ( j ! ) × 2 j ∑ k = 0 j a [ k ] × b [ j − k ] 用ntt算一下后面的卷积其他预处理即可

#include#include#include#define ll long longusing namespace std;const int gg=3;const int N=1e5+10;const int mod=998244353;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}inline int ksm(ll b,int t){static ll tmp; tmp=1;for (;t;b=b*b%mod,t>>=1)if (t&1) tmp=tmp*b%mod;return tmp;}ll g[N],inv[N];int mul[N],n,R[N<<2],a[N<<2],b[N<<2],invn,ans;inline int inc(int x,int v){return x+v>=mod?x+v-mod:x+v;}inline int dec(int x,int v){return x-v<0?x-v+mod:x-v;}inline void ntt(int *x,int f){ for (int i=0;i>1]>>1)|(i&1)<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。