Eddy Walker

题目链接

题意

有一个大小为$n$的环，现在从位置$0$开始走，或前或后，直到走到所有点都经过一遍停下来，问停在$M_{i}$的概率。

思路

我们可以手玩几个小的$n,m$。
当$n$为2：

$$p=1.$$

当$n$为3：

$$p_{1} = \frac{1}{2}.$$

当$n$为4：

$$p_{1} = \frac{1}{2} p_{2} + \frac{1}{2} p_{2}.$$ $$p_{1} + p_{2} = 1.$$ $$p_{1} = p_{2} = \frac{1}{3}.$$

当$n$为5：

$$p_{2} = \frac{1}{2} p_{1} + \frac{1}{2} p_{2}.$$ $$p_{1} + p_{2} = \frac{1}{2}.$$

…
所以当$m$不为$0$，概率是$\frac{1}{n - 1}$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
inline ll powmod(ll a,ll b)
{
    ll ans=1;
    while(b){if(b&1ll) ans=ans*a%mod;b>>=1;a=a*a%mod;}
    return ans;
}
int main()
{
    #ifdef local
    freopen("a.txt","r",stdin);
    #endif // local
    int t,n,m;
    ll ans=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(!m){
            if(n>1) ans=0;
        }
        else ans=ans*powmod(n-1,mod-2)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}