No.1704 Many Bus Stops (easy)
タグ : / 解いたユーザー数 101
作問者 :
harurun
/ テスター :
Problem Statement
There are $3$ bus stops: A, B, and C.
At time $0$, $1$ bus is stopped at bus stop A, and there are no buses anywhere other than bus stop A.
At each time $i=0,1,2,...,N-1$, each bus at each bus stop moves as follows.
If a bus is at bus stop A:
with probability $\frac{1}{3}$, it moves to bus stop B, taking time $1.5$
with probability $\frac{1}{3}$, it moves to bus stop C, taking time $1.5$
with probability $\frac{1}{3}$, it stays at bus stop A
If a bus is at bus stop B:
with probability $\frac{1}{3}$, it moves to bus stop C, taking time $1.5$
with probability $\frac{1}{3}$, it moves to bus stop A, taking time $1.5$
with probability $\frac{1}{3}$, it stays at bus stop B
If a bus is at bus stop C:
with probability $\frac{1}{3}$, it moves to bus stop A, taking time $1.5$
with probability $\frac{1}{3}$, it moves to bus stop B, taking time $1.5$
with probability $\frac{1}{3}$, it stays at bus stop C
Output the probability that at least 1 bus is at bus stop A at time $N$, modulo $\mod 10^9+7$.
Answer $T$ test cases.
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$ satisfying $R\times Q=P (mod 10^9+7)$ and $0≤R<10^9+7$.
Input
$T$
The first line contains the number of test cases $T$.
Each test case is as follows, and $T$ lines are given.
$N$
An integer $N$ is given.
Constraints
$1≤T≤3\times10^3$
$1≤N≤1\times10^9$
All input values are integers.
Sample
Sample 1
Input
5 3 5 10 100 1000000000
Output
370370373 930041159 79120731 511323553 802083332
For test case $1$, the probability of the answer is $\frac{1}{27}$. Output $370370373$, which is its value modulo $\mod 10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。