2019牛客暑期多校训练营（第二场）A.Eddy Walker

admin管理员组

文章数量:1581974

2019牛客暑期多校训练营（第二场）A.Eddy Walker

题目链接

题目描述

Eddy likes to walk around. Especially, he likes to walk in a loop called “Infinite loop”. But, actually, it’s just a loop with finite length(Anyway, the name doesn’t matter). Eddy can walk in a fixed length. He finds that it takes him N steps to walk through the loop a cycle. Then, he puts N marks on the “Infinite loop” labeled with 0 , 1 , … , N − 1 0, 1, \ldots, N-1 0,1,…,N−1, where i and i+1 are a step away each other, so as 0 and N-1. After that, Eddy stands on the mark labeled 0 and start walking around. For each step, Eddy will independently uniformly randomly choose to move forward or backward. If currently Eddy is on the mark labeled i, he will on the mark labeled i+1 if move forward or i-1 if move backward. If Eddy is on the mark labeled N-1 and moves forward, he will stand on the mark labeled 0. If Eddy is on the mark labeled 0 and moves backward, he will stand on the mark labeled N-1.

Although, Eddy likes to walk around. He will get bored after he reaches each mark at least once. After that, Eddy will pick up all the marks, go back to work and stop walking around.

You, somehow, notice the weird convention Eddy is doing. And, you record T scenarios that Eddy walks around. For i-th scenario, you record two numbers N i , M i N_i , M_i Ni​,Mi​ , where N i N_i Ni​ tells that in the i-th scenario, Eddy can walk through the loop a cycle in exactly N i N_i Ni​ steps(Yes! Eddy can walk in different fixed length for different day.). While M i M_i Mi​ tells that you found that in the i-th scenario, after Eddy stands on the mark labeled M i M_i Mi​ , he reached all the marks.

However, when you review your records, you are not sure whether the data is correct or even possible. Thus, you want to know the probability that those scenarios will happen. Precisely,   you   are   going   to   compute   the   probability   that   first   i   scenarios   will   happen   sequentially   for   each   i. \textbf{Precisely, you are going to compute the probability that first i scenarios will happen sequentially for each i.} Precisely, you are going to compute the probability that first i scenarios will happen sequentially for each i.

输入描述:

The first line of input contains an integers T.
Following T lines each contains two space-separated integers N i N_i Ni​ and M i M_i Mi​.
1 ≤ T ≤ 1021 1 \leq T \leq 1021 1≤T≤1021
0 ≤ M i < N i ≤ 1 0 9 0 \leq M_i < N_i \leq 10^9 0≤Mi​<Ni​≤109

输出描述:

Output T lines each contains an integer representing the probability that first i scenarios will happen sequentially.
you should output the number module 1 0 9 + 7 10^9+7 109+7
Suppose the probability is P Q \frac{P}{Q} QP​ , the desired output will be P × Q − 1 m o d    1 0 9 + 7 P \times Q^{-1} \mod 10^9+7 P×Q−1mod109+7

示例1

输入

3
1 0
2 1
3 0

输出

1
1
0

题意就是有一个 0->n-1 的圈，从 0 点出发，可以前进可以后退，求每个点都至少经过一次后的终点~
这题看着比较懵其实就是找规律，我们很容易发现起点 0 在 n > 1 n>1 n>1 时是不可能走到的，而其他点的概率恰为 1 n − 1 \frac{1}{n-1} n−11​，所以就可以通过求逆元直接得答案，但注意上面我题干标红的部分，题目要求的是连续的概率，也即每次求的概率都要累乘起来，否则答案错误，AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
main(){
    ll t,a,b,ans=1;
    cin>>t;
    while(t--){
        cin>>a>>b;
        if(b==0) ans=(a>1?0:ans);
        else{
            ans=ans*power(a-1,mod-2)%mod;
        }
        cout<<ans<<endl;
    }
}

本文标签： 校训暑期第二场EddyWalker