No.1392 Don't be together
タグ : / 解いたユーザー数 69
作問者 :
tatyam
Problem Statement
First, you are given integers $N,M$ and a permutation $P_i\ (1\le i \le N)$ of the integers from $1$ to $N$. This permutation satisfies $i\neq P_i\ (1\le i \le N)$.
Find the number of ways to divide the integers from $1$ to $N$ into $M$ groups so that the following conditions are satisfied. Since the answer can be very large, output the remainder when divided by $998244353$.
Conditions
- Each group contains at least $1$ integer
- For each $i\ (1\le i \le N)$, $i$ and $P_i$ belong to different groups
Input
$N\ M$ $P_1\ P_2\ \dots\ P_N$
- $2\le N \le 5000$
- $1\le M \le N$
- $1 \le P_i \le N\ (1\le i \le N)$
- $i\neq P_i\ (1\le i \le N)$
- All input values are integers
Output
Output the answer.
Print a newline at the end.
Sample
Sample 1
Input
4 2 2 1 4 3
Output
2
There are $2$ valid ways to divide: $\{1,3\},\ \{2,4\}$ and $\{1,4\},\ \{2,3\}$.
Another possible division is, for example, $\{1,2,3\},\ \{4\}$, but this does not satisfy the conditions because $1, 2$ belong to the same group.
Sample 2
Input
3 2 2 3 1
Output
0
There is no valid way to divide.
Sample 3
Input
20 11 14 10 11 20 19 8 4 15 12 17 3 16 5 18 2 6 7 9 1 13
Output
136233051
Output the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。