No.1671 Permutation Tour

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1671 Permutation Tour

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 68
作問者 :

NatsubiSogan / テスター :

nok0

4 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$ の周遊コストの期待値を $mod 10^{9} + 7$ で求めてください。

期待値を

mod 10^{9} + 7

で出力するとは？（クリックで開けます）

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

入力

$N$

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

出力

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

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

サンプル

サンプル1

入力

出力

$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$

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

サンプル2

入力

314159265

出力

136209063

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

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

yukicoder

No.1671 Permutation Tour

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力