A5716. 「TJOI / HEOI2016」求和
编程题
省选/NOI-
知识点
题目描述
在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。
现在他想计算这样一个函数的值:
$$f(n)=\sum_{i=0}^n \sum_{j=0}^i S(i, j) \cdot 2^j \cdot j!$$
$S(i, j)$表示第二类斯特林数，递推公式为: $S(i, j) = j \cdot S(i − 1, j) + S(i − 1, j − 1), \ 1 \leq j \leq i − 1$。
边界条件为：$S(i, i) = 1(0 \leq i), \ S(i, 0) = 0(1 \leq i)$
你能帮帮她吗?
现在他想计算这样一个函数的值:
$$f(n)=\sum_{i=0}^n \sum_{j=0}^i S(i, j) \cdot 2^j \cdot j!$$
$S(i, j)$表示第二类斯特林数，递推公式为: $S(i, j) = j \cdot S(i − 1, j) + S(i − 1, j − 1), \ 1 \leq j \leq i − 1$。
边界条件为：$S(i, i) = 1(0 \leq i), \ S(i, 0) = 0(1 \leq i)$
你能帮帮她吗?
输入格式
输入只有一个正整数。
输出格式
输出 $f(n)$。由于结果会很大，输出 $ f(n) $ 对 $998244353 \ (7 × 17 × 2^{23} + 1)$ 取模的结果即可。
输入输出样例
输入 #1
3
输出 #1
87
说明/提示
$1 \leq n \leq 100000$