問題一覧 > 通常問題

No.1392 Don't be together

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

問題文

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

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

条件

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

入力

N M
P1 P2 … PN

  • 2≤N≤5000
  • 1≤M≤N
  • 1≤Pi≤N (1≤i≤N)
  • i≠Pi (1≤i≤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もしくは右上の雲マークをクリックしてアカウントを作成してください。