当前位置： 移动技术网 > IT编程>开发语言>C/C++ > C-Travel along the Line ZOJ - 4006题解

C-Travel along the Line ZOJ - 4006题解

2018年10月03日  | 移动技术网IT编程  | 我要评论

枫叶的作文,欲望之瞳传说,A CHORD

题目

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();
    }
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网