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个无序的盒子中不允许为空 求方案数 $S_{n}^{m}=\frac{1}{m!}\sum\limits_{k=0}^{m}(-1)^{k}C_{m}^{k}*(m-k)^{n}$ 首先将盒子有序 最后/(m!) 然后考虑容斥 表示从m个中钦定K个空的位置 然后剩下的随便放 这样的答案就是至少K个空位置的答案 那显然0个空位置是答案 那么就至少0-至少1+至少2 …这样就写出了这样一个通项公式 首先将斯特林数带入公式 $Ans=\sum\limits_{i=0}^n\sum\limits_{j=0}^iS_{i,j}\times2^j\times(j!)$ $Ans=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{j}\frac{1}{j!}\sum\limits_{k=0}^{j}(-1)^{k}\times \frac{j!}{(j-k)!\times k!}\times(i-k)^{i}\times 2^j\times (j!)$ 变换求和符号将其提到前面 $Ans=\sum\limits_{j=0}^{n}(j!)\times2^j\sum\limits_{k=0}^{j}(-1)^{k}\times \frac{1}{k!}\sum\limits_{i=j}^{n}\times\frac{(j-k)^{i}}{(j-k)!}$ 所以可以设 $a_i=\frac{(-1)^i}{i!}$ $b_i=\frac{\sum\limits_{j=0}^{n} i^j}{i!}$ 然后分别带入 $Ans=\sum\limits_{j=0}^{n}(j!)\times2^j\sum\limits_{k=0}^{j}a[k]\times b[j-k]$用ntt算一下后面的卷积其他预处理即可

 

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论