102265: [AtCoder]ABC226 F - Score of Permutations
Description
Score : $500$ points
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
Input
Output
问题描述
对于排列$P = (p_1, p_2, \dots, p_N)$,定义$P$的分数$S(P)$如下。
- 有$N$个人,编号为$1,2,\dots,N$。此外,Snuke也在场。最初,第$i$个人($1 \leq i \leq N$)拥有Ball $i$。
每次Snuke尖叫时,所有编号不为$p_i$的第$i$个人同时将他们的球交给第$p_i$个人。
如果,在至少尖叫一次之后,每个人都拥有Ball $i$,则Snuke停止尖叫。
分数为Snuke停止尖叫之前尖叫的次数。这里,保证分数将是一个有限值。
有$N!$个排列$P$为$(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$个人拥有Ball $1$,第$2$个人拥有Ball $2$。
在Snuke的第一次尖叫后,第$1$个人拥有Ball $1$,第$2$个人拥有Ball $2$。
这里,每个人都拥有Ball $i$,所以他停止尖叫。
因此,分数为$1$。
排列$(2,1)$的分数如下找到。
- 最初,第$1$个人拥有Ball $1$,第$2$个人拥有Ball $2$。
在Snuke的第一次尖叫后,第$1$个人拥有Ball $2$,第$2$个人拥有Ball $1$。
在Snuke的第二次尖叫后,第$1$个人拥有Ball $1$,第$2$个人拥有Ball $2$。
这里,每个人都拥有Ball $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