問題一覧 > 通常問題

No.1978 Permutation Repetition

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

問題文

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

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

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

    • 制約

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

    入力

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

    $N\ \ M$
$A_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)$ であるときを考えると、$x$ は

    • $i=1$ のとき、$1 \to 1 \to 1$
    • $i=2$ のとき、$2 \to 4 \to 2$
    • $i=3$ のとき、$3 \to 3 \to 3$
    • $i=4$ のとき、$4 \to 2 \to 4$

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

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

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

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