C-Travel along the Line ZOJ - 4006题解

题目

c - travel along the line zoj - 4006 
baobao is traveling along a line with infinite length.

at the beginning of his trip, he is standing at position 0. at the beginning of each second, if he is standing at position , with  probability he will move to position , with  probability he will move to position , and with probability he will stay at position . positions can be positive, 0, or negative.

dreamgrid, baobao's best friend, is waiting for him at position . baobao would like to meet dreamgrid at position  after exactly  seconds. please help baobao calculate the probability he can get to position  after exactly  seconds.

it's easy to show that the answer can be represented as , where  and  are coprime integers, and  is not pisible by . please print the value of  modulo , where  is the multiplicative inverse of  modulo .

input
there are multiple test cases. the first line of the input contains an integer (about 10), indicating the number of test cases. for each test case:

the first and only line contains two integers  and  (). their meanings are described above.

output
for each test case output one integer, indicating the answer.

sample input
3
2 -2
0 0
0 1
sample output
562500004
1
0

题解：

我们枚举向左移动的次数，那么很容易可以得到向右和保持不动的此处

然后根据公式

(nl)(n−lr)(14)l+r(12)s=(nl)(n−lr)(12)2(l+r)+s

    #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <map>
#include <queue>
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define mset(var,val) memset(var,val,sizeof(var))

#define test(a) cout<<a<<endl
#define test2(a,b) cout<<a<<" "<<b<<endl

#define test3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
const int n= 2e5;
const int mod =1e9+7;
using namespace std;
typedef long long ll;
ll a[n+10];
ll b[n+10];
ll fac[n+10];
ll inv(ll a){
    if(a==1)return 1;
    return inv(mod%a)*(mod-mod/a)%mod;
}
ll c(ll n,ll m){
        ll ans = fac[n]*(inv(1ll*fac[m]*fac[n-m]%mod));
        return ans % mod ;
}
void init(){
        fac[0]=1;
        b[0]=1;
        for(int i =1;i<=n;i++){
                fac[i]=(fac[i-1]*i)%mod;
                b[i]=(b[i-1]*2ll)%mod;
        }
}

void work(){
        int n,y;
        scdd(n,y);
        long long ans=0;
        for(int i=0;i<=n;i++){
                int l = i;
                int r = y+i;
                int s = n-l-r;
                if(r<0||s<0||r>n||s>n)continue;
                ll son = c(n,l)*c(n-l,r)%mod;
                ll mon = inv(b[2*(l+r)+s]);
                ans =( ans + (1ll*son*mon))%mod;
        }
        printf("%lld\n",ans);
}
int main(){
    #ifdef local
        freopen("in.txt","r",stdin);
    #endif
    int t;
    init();
    scd(t);
    while(t--){
        work();
    }
}