分数: 500 点
问题陈述
对于排列 P = (p_1, p_2, \dots, p_N) of (1,2, \dots, N),让我们定义分数 S(P) of P 如下。
- 有 N 人,已编号 1,2,\dots,N。此外,还有《Snuke》。最初,人 i (1 \leq i \leq N) 有球 i.
每次 Snuke 尖叫时,每个人 i 这样 i \neq p_i 将球交给 Person p_i 同时进行。
如果每个人至少尖叫一次后 i 有球 i,Snuke 停止尖叫。
分数是 Snuke 尖叫直至停止的次数。这里,保证分数是有限值。
有 N! 排列 P of (1,2, \dots, N)。求总和,取模 998244353,这些排列的分数,每个都提高到 K次方。
- 正式地,让 S_N 是以下排列的集合 (1,2, \dots, N)。计算如下: \displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}.
约束
- 2 \leq N \leq 50
- 1 \leq K \leq 10^4
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K
输出
打印 \displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}.
示例输入 1
2 2
示例输出 1
5
当 N = 2,有两种可能的排列 P: (1,2),(2,1).
排列的分数 (1,2) 被发现如下。
- 最初,人 1 有球 1和人 2 有球 2.
Snuke的第一声尖叫之后,Person 1 有球 1和人 2 有球 2.
在这里,每个人 i 有球 i,所以他停止尖叫。
因此,分数是 1.
排列的分数 (2,1) 被发现如下。
- 最初,人 1 有球 1和人 2 有球 2.
Snuke的第一声尖叫之后,Person 1 有球 2和人 2 有球 1.
Snuke第二次尖叫后,Person 1 有球 1和人 2 有球 2.
在这里,每个人 i 有球 i,所以他停止尖叫。
因此,分数是 2.
因此,本例的答案是 1^2 + 2^2 = 5.
示例输入 2
3 3
示例输出 2
79
下面列出了所有排列及其分数。
- (1,2,3):分数是 1.
- (1,3,2):分数是 2.
- (2,1,3):分数是 2.
- (2,3,1):分数是 3.
- (3,1,2):分数是 3.
- (3,2,1):分数是 2.
因此,我们应该打印 1^3 + 2^3 + 2^3 + 3^3 + 3^3 + 2^3 = 79.
示例输入 3
50 10000
示例输出 3
77436607