No.1671 Permutation Tour
タグ : / 解いたユーザー数 66
作問者 :
NatsubiSogan
/ テスター :
nok0
問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。