問題一覧 > 通常問題

No.1978 Permutation Repetition

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 27
作問者 : magsta / テスター : shino16
1 ProblemId : 8045 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-10 12:25:45

問題文

正の整数 N,MN,M と順列 A=(A1,A2,...,AN)A=(A_1,A_2,...,A_N) が与えられます。

以下の条件を満たす順列 P=(P1,P2,...,PN)P=(P_1,P_2,...,P_N) は何通りあるでしょうか。総数を 109+710^9+7 で割った余りを求めてください。

  • 整数 i (1≤i≤N)i \ (1 \leq i \leq N) それぞれにおいて、初期値が ii である変数 xx に対し xx を PxP_x で置き換えるという操作を MM 回行うと x=Aix=A_i となる。

    • 制約

    • 1≤N≤103\displaystyle 1 \leq N \leq 10^3
    • 1≤M≤109\displaystyle 1 \leq M \leq 10^9
    • 1≤Ai≤N\displaystyle 1 \leq A_i \leq N
    • Ai≠Aj (i≠j)\displaystyle A_i \neq A_j \ (i \neq j)
    • 入力はすべて整数である

    入力

    入力は以下の形式で標準入力から与えられる。 

    N  MN\ \ M
A1  A2 … ANA_1\ \ A_2\ \dots \ A_N

    出力

    求めた値を出力し、最後に改行せよ。

    サンプル

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

    P=(1,4,3,2),(4,3,2,1)P=(1,4,3,2),(4,3,2,1) などが条件を満たします。

    例えば P=(1,4,3,2)P=(1,4,3,2) であるときを考えると、xx は

    • i=1i=1 のとき、1→1→11 \to 1 \to 1
    • i=2i=2 のとき、2→4→22 \to 4 \to 2
    • i=3i=3 のとき、3→3→33 \to 3 \to 3
    • i=4i=4 のとき、4→2→44 \to 2 \to 4

    と変化し、それぞれの最終的な xx は AiA_i と等しくなっています。

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

    条件を満たす順列 PP は存在しません。

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