#667. #2058. 「TJOI / HEOI2016」求和
#2058. 「TJOI / HEOI2016」求和
题目描述
在2016年,佳媛姐姐刚刚学习了第二类斯特林数,非常开心。
现在他想计算这样一个函数的值:
表示第二类斯特林数,递推公式为: 。
边界条件为:
你能帮帮她吗?
输入格式
输入只有一个正整数。
输出格式
输出 。由于结果会很大,输出 对 取模的结果即可。
样例
3
87
数据范围与提示
在2016年,佳媛姐姐刚刚学习了第二类斯特林数,非常开心。
现在他想计算这样一个函数的值:
f(n)=i=0∑nj=0∑iS(i,j)⋅2j⋅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)
你能帮帮她吗?
输入只有一个正整数。
输出 f(n)。由于结果会很大,输出 f(n) 对 998244353 (7×17×223+1) 取模的结果即可。
3
87
1≤n≤100000