No.1671 Permutation Tour
タグ : / 解いたユーザー数 74
作問者 :
NatsubiSogan
/ テスター :
nok0
Problem Statement
You are given an integer $N$ greater than or equal to $2$.
For a sequence $P=(P_1,P_2,...,P_N)$ obtained by rearranging $(1,2,...,N)$, define its tour cost as follows.
- Define the sequence $Q=(Q_1,Q_2,...,Q_N)$ as follows. (By this definition, $Q$ is always uniquely determined.)
- For every $i$ $(1 \leq i \leq N)$, $Q_{P_i} = i$ holds.
- The tour cost is $|Q_1 - Q_2| + |Q_2 - Q_3| + \dots + |Q_{N-1} - Q_N| + |Q_N - Q_1|$.
You choose $P$ uniformly at random from the $N!$ possibilities. Find the expected value of the tour cost of $P$ in $\bmod 10^9+7$.
What does it mean to output the expected value in $\bmod 10^9+7$? (Click to expand)
The value to be found is always a rational number. Let it be the irreducible fraction $\displaystyle\frac{p}{q}$. It can be proved that $q \not\equiv 0 \pmod{10^9+7}$ holds. Under this condition, there is a unique integer $r$ that is at least $0$ and less than $10^9+7$ and satisfies $rq \equiv p \pmod{10^9+7}$, so output this $r$.
Input
$N$
- $N$ is an integer satisfying $2 \leq N \leq 10^9$.
Output
Output the expected value of the tour cost in $\bmod 10^9+7$.
Print a newline at the end.
Sample
Sample 1
Input
2
Output
2
- When $P=(1,2)$: $Q=(1,2)$, so the tour cost is $|Q_1-Q_2|+|Q_2-Q_1| = |1-2|+|2-1| = 2$.
- When $P=(2,1)$: $Q=(2,1)$, so the tour cost is $|Q_1-Q_2|+|Q_2-Q_1| = |2-1|+|1-2| = 2$.
Therefore, the expected value of the tour cost is $\displaystyle\frac{2 + 2}{2!} = 2$.
Sample 2
Input
314159265
Output
136209063
Note that the expected value must be output in $\bmod 10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。