問題一覧 > 通常問題

No.1978 Permutation Repetition

レベル : / AI推定難易度 : 2025 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 28
作問者 : magsta / テスター : shino16
お気に入りにしたユーザー ProblemId : 8045 / 自分の提出
問題文最終更新日: 2022-06-10 12:25:45
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 347 (順位表) の他の問題:

Problem Statement

You are given positive integers $N,M$ and a permutation $A=(A_1,A_2,...,A_N)$.

How many permutations $P=(P_1,P_2,...,P_N)$ satisfy the following condition? Find the count modulo $10^9+7$.

  • For each integer $i \ (1 \leq i \leq N)$, starting with a variable $x$ whose initial value is $i$, performing the operation of replacing $x$ with $P_x$ exactly $M$ times results in $x=A_i$.
  • Constraints

    • $\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)$
    • All inputs are integers.

    Input

    The input is given from standard input in the following format.

    $N\ \ M$
    $A_1\ \ A_2\ \dots \ A_N$

    Output

    Output the computed value, followed by a newline.

    Sample

    Sample 1
    Input
    4 2
    1 2 3 4
    Output
    10

    $P=(1,4,3,2),(4,3,2,1)$ and others satisfy the condition.

    For example, when $P=(1,4,3,2)$, $x$ changes as follows:

    • when $i=1$, $1 \to 1 \to 1$
    • when $i=2$, $2 \to 4 \to 2$
    • when $i=3$, $3 \to 3 \to 3$
    • when $i=4$, $4 \to 2 \to 4$

    In each case, the final value of $x$ equals $A_i$.

    Sample 2
    Input
    4 2
    4 3 1 2
    Output
    0

    No permutation $P$ satisfies the condition.

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