問題一覧 > 通常問題

No.1671 Permutation Tour

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : NatsubiSoganNatsubiSogan / テスター : nok0nok0
1 ProblemId : 6949 / 自分の提出
問題文最終更新日: 2021-09-04 15:55:29

問題文

$2$ 以上の整数 $N$ が与えられます。

$(1,2,...,N)$ を並べ替えた数列 $P=(P_1,P_2,...,P_N)$ に対し、周遊コスト を以下のように定義します。

  • 数列 $Q=(Q_1,Q_2,...,Q_N)$ を以下のように定義する。(この定義から、$Q$ は常に一意に定まる)
    • すべての $i$ $(1 \leq i \leq N)$ について、 $Q_{P_i} = i$ が成り立つ
  • 周遊コスト は $|Q_1 - Q_2| + |Q_2 - Q_3| + \dots + |Q_{N-1} - Q_N| + |Q_N - Q_1|$ である。

あなたは、$P$ を考えられる $N!$ 通りから一様ランダムに選択します。$P$ の 周遊コスト の期待値を $\bmod 10^9+7$ で求めてください。

期待値を $\bmod 10^9+7$ で出力するとは?(クリックで開けます)

求める値は必ず有理数となります。これを既約分数 $\displaystyle\frac{p}{q}$ としましょう。ここで、$q \not\equiv 0 \pmod{10^9+7}$ となることが証明できます。このもとで、$rq \equiv p \pmod{10^9+7}$ を満たす $0$ 以上 $10^9+7$ 未満の整数 $r$ が一意に定まるので、$r$ を出力してください。

入力

$N$
  • $N$ は $2 \leq N \leq 10^9$ を満たす整数

出力

周遊コスト の期待値を $\bmod 10^9+7$ で出力してください。

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

サンプル

サンプル1
入力
2
出力
2
  • $P=(1,2)$ のとき:$Q=(1,2)$ となるので、周遊コスト は $|Q_1-Q_2|+|Q_2-Q_1| = |1-2|+|2-1| = 2$
  • $P=(2,1)$ のとき:$Q=(2,1)$ となるので、周遊コスト は $|Q_1-Q_2|+|Q_2-Q_1| = |2-1|+|1-2| = 2$

よって、周遊コスト の期待値は $\displaystyle\frac{2 + 2}{2!} = 2$ です。

サンプル2
入力
314159265
出力
136209063

期待値を $\bmod 10^9+7$ で出力することに注意してください。

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