【ZCMU2157】ly的旅行計劃（組合）

題目連結

2157: K.ly的旅行計劃

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 38  Solved: 12

[Submit][Status][Web Board]

Description

馬上就要放暑假了,ly開始準備她的假期旅行計劃，她買了一輛很神奇的火車的車票，假設把這輛火車的路線看成一條X軸，ly會在0的位置上車，然後開始她的旅行。這輛神奇的火車有一個神奇的行進規則，當它位于坐标X時，每天它有1/4的機率移動到（X+1），有1/4的機率移動到（X-1）,還有1/2的機率會在原地多停一天。

而wjw作為ly的好朋友，當然是希望和ly一起出去玩，但是wjw需要先回家一趟，是以wjw會在坐标點為M的地方等ly,ly現在想知道，她有多大的機率在第N天的時候到達M點見到wjw

顯然答案可以被表示成A/B,(A,B互質),并且Q不能被1000000007整除，請輸出A(B^-1) mod 1000000007的結果，(B^-1)是B的乘法倒數模1000000007

Input

多組資料，第一行包含一個正整數T(T<=10)

然後每行有兩個正整數N,M(0<=n,|M|<=100000)，如題意

Output

對每組N,M輸出結果

Sample Input

2 2 -2 0 0

Sample Output

562500004 1

HINT

Source

jnxxhzz

【解題思路】

從原點開始走到M點，假設在n天中有i天是往前走的，那麼就有i-m天是往回走的，n-2i+m天是停留在原地的。

是以在這n天中i天向前走的方案數為C(n,i)，向後走的方案數為C(n-i,i-m)，停留在原地的方案數為C(n-2i+m,n-2i+m)，是以總的機率為C(n,i)*(1/4)^i*C(n-i,i-m)*(1/4)^(i-m)*C(n-2i+m,n-2i+m)*(1/2)^(n-2i+m)。再枚舉i把所有的機率相加。

【代碼】

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int mod=1e9+7;
LL f[maxn];
LL quickpow(LL a,LL b)
{
    LL ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans%mod;
}
LL inv(LL a)
{
    return quickpow(a,mod-2);
}
LL C(int a,int b)
{
    if(a==b || b==0)return 1;
    else return ((f[a]*inv(f[b]))%mod*inv(f[a-b]))%mod;
}
int main()
{
    int T;
    f[0]=0;f[1]=1;
    for(int i=2;i<maxn;i++)
        f[i]=(f[i-1]*i)%mod;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        LL ans=0;
        scanf("%d%d",&n,&m);
        m=fabs(m);
        for(int i=m;2*i-m<=n;i++)
        {
            ans+=C(n,i)*C(n-i,i-m)%mod*inv(quickpow(2,n-2*i+m))%mod*inv(quickpow(4,2*i-m))%mod;
            ans=ans%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}