No.1706 Many Bus Stops (hard)
タグ : / 解いたユーザー数 83
作問者 :
harurun
/ テスター :
Problem Statement
There are $C$ bus stops, which we call bus stop $1$, bus stop $2$, ...., bus stop $C$.
At time $0$, $M$ buses are stopped at bus stop $1$, and there are no buses anywhere other than bus stop $1$.
At each time $i=0,1,2,...,N-1$, every bus at each bus stop moves independently as follows.
If a bus is at bus stop $x$
For each bus stop other than bus stop $x$, it moves to that bus stop with probability $\frac{1}{C}$, taking time $1.5$
With probability $\frac{1}{C}$, it stays at bus stop $x$
Output the probability that at least one bus is at bus stop $1$ at time $N$, modulo $\mod 10^9+7$.
What it means to output a probability modulo $\mod 10^9+7$ (click to expand)
When the probability is expressed as an irreducible fraction $\frac{P}{Q}$, output the non-negative integer $R$ that satisfies $R\times Q=P (mod 10^9+7)$ and $0≤R<10^9+7$.
Input
$C\ N\ M$
The number of bus stops $C$, an integer $N$, and the number of buses $M$ are given, separated by spaces.
Constraints
$2≤C≤1\times10^5$
$1≤N≤1\times10^9$
$1≤M≤1\times10^9$
All inputs are integers
Sample
Sample 1
Input
3 3 1
Output
370370373
The probability in question is $\frac{1}{27}$. Output it modulo $\mod 10^9+7$.
Sample 2
Input
10 1 2
Output
830000006
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。