問題一覧 > 通常問題

No.1392 Don't be together

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 64
作問者 : chineristACchineristAC / テスター : tatyamtatyam
7 ProblemId : 5125 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-12 19:02:39

問題文

はじめに整数 $N,M$ と $1$ から $N$ までの整数の順列 $P_i\ (1\le i \le N)$ が与えられます。この順列は $i\neq P_i\ (1\le i \le N)$ を満たします。

以下の条件を満たすように $1$ から $N$ までの整数を $M$ 個のグループに分ける方法の場合の数を求めてください。答えは非常に大きくなることがあるので $998244353$ で割ったあまりを出力してください。

条件

  • 各グループは少なくとも $1$ つの整数を含む
  • 各 $i\ (1\le i \le N)$ について、 $i$ と $P_i$ は異なるグループに属する

入力

$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)$
  • 与えられる入力はすべて整数

出力

答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
4 2
2 1 4 3
出力
2

条件を満たす分け方は $\{1,3\},\ \{2,4\}$ と $\{1,4\},\ \{2,3\}$ の $2$ 通りです。

ほかの分け方としては例えば $\{1,2,3\},\ \{4\}$ が考えられますが、これは $1, 2$ が同じグループに属してしまっているので条件を満たしません。

サンプル2
入力
3 2
2 3 1
出力
0

条件を満たす分け方は存在しません。

サンプル3
入力
20 11
14 10 11 20 19 8 4 15 12 17 3 16 5 18 2 6 7 9 1 13
出力
136233051

$998244353$ で割ったあまりを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。