AT_abc226_f [ABC226F] Score of Permutations

题目描述

给定一个长度为 $N$ 的排列 $P = (p_1, p_2, \dots, p_N)$，它是 $1,2,\dots,N$ 的一个排列。定义排列 $P$ 的分数 $S(P)$ 如下：

• 有 $N$ 个人和すぬけ君，这 $N$ 个人编号为 $1,2,\dots,N$。一开始，第 $i$ 个人（$1 \leq i \leq N$）手里拿着编号为 $i$ 的球。 每当すぬけ君喊叫一次，所有满足 $i \neq p_i$ 的人 $i$ 会同时把自己手里的球传给第 $p_i$ 个人。 当すぬけ君喊叫至少一次后，所有人 $i$ 都拿回了编号为 $i$ 的球时，すぬけ君就会停止喊叫。 すぬけ君喊叫的总次数就是该排列的分数。保证分数一定是有限的。

所有可能的 $P$ 有 $N!$ 种。请计算所有排列的分数的 $K$ 次幂之和对 $998244353$ 取模的结果。

• 更严格地说，设所有 $1,2,\dots,N$ 的排列的集合为 $S_N$，则需计算

  $$\left(\sum_{P \in S_N} S(P)^K \right) \bmod 998244353$$

输入格式

输入为一行，包含两个整数。

$N$ $K$

输出格式

输出 $\left(\sum_{P \in S_N} S(P)^K \right) \bmod 998244353$ 的值。

输入输出样例 #1

输入 #1

2 2

输出 #1

5

输入输出样例 #2

输入 #2

3 3

输出 #2

79

输入输出样例 #3

输入 #3

50 10000

输出 #3

77436607

说明/提示

数据范围

• $2 \leq N \leq 50$
• $1 \leq K \leq 10^4$
• 输入均为整数。

样例解释 1

当 $N=2$ 时，所有可能的排列为 $(1,2)$ 和 $(2,1)$ 共两种。排列 $(1,2)$ 的分数如下：

• 一开始，第 $1$ 个人拿着球 $1$，第 $2$ 个人拿着球 $2$。 すぬけ君第一次喊叫后，第 $1$ 个人仍然拿着球 $1$，第 $2$ 个人仍然拿着球 $2$。 此时所有人都拿回了自己编号的球，すぬけ君停止喊叫。分数为 $1$。 排列 $(2,1)$ 的分数如下：
• 一开始，第 $1$ 个人拿着球 $1$，第 $2$ 个人拿着球 $2$。 すぬけ君第一次喊叫后，第 $1$ 个人拿着球 $2$，第 $2$ 个人拿着球 $1$。 すぬけ君第二次喊叫后，第 $1$ 个人拿着球 $1$，第 $2$ 个人拿着球 $2$。 此时所有人都拿回了自己编号的球，すぬけ君停止喊叫。分数为 $2$。 因此 $1^2 + 2^2 = 5$，这就是本题的答案。

样例解释 2

枚举所有排列及其分数如下：

• 排列: $(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$，输出 $79$。

由 ChatGPT 4.1 翻译