問題一覧 > 通常問題

No.1392 Don't be together

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 69
作問者 : chineristAC / テスター : tatyam
お気に入りにしたユーザー ProblemId : 5125 / 自分の提出
問題文最終更新日: 2021-02-12 19:02:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 282 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。