Score : $500$ points

问题描述

对于一个由 $(1,2,\dots,N)$ 构成的排列 $P = (p_1, p_2, \dots, p_N)$，我们定义其得分 $S(P)$ 如下：

• 有 $N$ 名编号为 $1,2,\dots,N$ 的人，此外还有 Snuke。最初，编号为 $i$ $(1 \leq i \leq N)$ 的人持有第 $i$ 号球。 每当 Snuke 大喊时，所有满足 $i \neq p_i$ 的编号为 $i$ 的人会同时将他们的球交给编号为 $p_i$ 的人。 如果在至少大喊一次之后，每个编号为 $i$ 的人都持有第 $i$ 号球，则 Snuke 停止大喊。 得分是指 Snuke 在停止大喊前所大喊的次数。这里保证得分将是一个有限值。

存在 $N!$ 种由 $(1,2,\dots,N)$ 构成的排列 $P$。求这些排列中，每种排列的得分的 $K$ 次方之和，结果对 $998244353$ 取模。

• 形式上，令 $S_N$ 表示由 $(1,2,\dots,N)$ 构成的排列集合。计算以下表达式：$\displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}$.

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

For a permutation $P = (p_1, p_2, \dots, p_N)$ of $(1,2, \dots, N)$, let us define the score $S(P)$ of $P$ as follows.

• There are $N$ people, numbered $1,2,\dots,N$. Additionally, Snuke is there. Initially, Person $i$ $(1 \leq i \leq N)$ has Ball $i$.
  Each time Snuke screams, every Person $i$ such that $i \neq p_i$ gives their ball to Person $p_i$ simultaneously.
  If, after screaming at least once, every Person $i$ has Ball $i$, Snuke stops screaming.
  The score is the number of times Snuke screams until he stops. Here, it is guaranteed that the score will be a finite value.

There are $N!$ permutations $P$ of $(1,2, \dots, N)$. Find the sum, modulo $998244353$, of the scores of those permutations, each raised to the $K$-th power.

• Formally, let $S_N$ be the set of the permutations of $(1,2, \dots, N)$. Compute the following: $\displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}$.

Constraints

• $2 \leq N \leq 50$
• $1 \leq K \leq 10^4$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$

Output

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

Sample Input 1

2 2

Sample Output 1

5

When $N = 2$, there are two possible permutations $P$: $(1,2),(2,1)$.

The score of the permutation $(1,2)$ is found as follows.

• Initially, Person $1$ has Ball $1$, and Person $2$ has Ball $2$.
  After Snuke's first scream, Person $1$ has Ball $1$, and Person $2$ has Ball $2$.
  Here, every Person $i$ has Ball $i$, so he stops screaming.
  Thus, the score is $1$.

The score of the permutation $(2,1)$ is found as follows.

• Initially, Person $1$ has Ball $1$, and Person $2$ has Ball $2$.
  After Snuke's first scream, Person $1$ has Ball $2$, and Person $2$ has Ball $1$.
  After Snuke's second scream, Person $1$ has Ball $1$, and Person $2$ has Ball $2$.
  Here, every Person $i$ has Ball $i$, so he stops screaming.
  Thus, the score is $2$.

Therefore, the answer in this case is $1^2 + 2^2 = 5$.

Sample Input 2

3 3

Sample Output 2

79

All permutations and their scores are listed below.

• $(1,2,3)$: The score is $1$.
• $(1,3,2)$: The score is $2$.
• $(2,1,3)$: The score is $2$.
• $(2,3,1)$: The score is $3$.
• $(3,1,2)$: The score is $3$.
• $(3,2,1)$: The score is $2$.

Thus, we should print $1^3 + 2^3 + 2^3 + 3^3 + 3^3 + 2^3 = 79$.

Sample Input 3

50 10000

Sample Output 3

77436607

update @ 2024/3/10 09:56:07