#2058. 「TJOI / HEOI2016」求和

ID: 667

传统题

1000ms

256MiB

难度: (无)

上传者:

题目描述

在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。

现在他想计算这样一个函数的值:

f(n)=∑i=0n∑j=0iS(i,j)⋅2j⋅j!f(n)=\sum_{i=0}^n \sum_{j=0}^i S(i, j) \cdot 2^j \cdot j!f(n)=i=0∑nj=0∑iS(i,j)⋅2j⋅j!

S(i,j)S(i, 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)S(i, i) = 1(0 \leq i), \ S(i, 0) = 0(1 \leq i)S(i,i)=1(0≤i), S(i,0)=0(1≤i)

你能帮帮她吗?

</div> </div>

输入只有一个正整数。

输出 f(n)f(n)f(n)。由于结果会很大，输出 f(n) f(n) f(n) 对 998244353 (7×17×223+1) 取模的结果即可。