首页 > 代码库 > hdu 5673 Robot 卡特兰数+逆元

hdu 5673 Robot 卡特兰数+逆元

2024-08-18 05:46:20   222人阅读

Robot

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)


Problem Description
There is a robot on the origin point of an axis.Every second, the robot can move right one unit length or do nothing.If the robot is 
on the right of origin point,it can also move left one unit length.A route is a series of movement. How many different routes there are
that after n seconds the robot is still located on the origin point?
The answer may be large. Please output the answer modulo 1,000,000,007
 

 

Input
There are multiple test cases. The first line of input contains an integer T(1≤T≤100) indicating the number of test cases. For each test case:

The only line contains one integer n(1≤n≤1,000,000).
 

 

Output
For each test case, output one integer.
 

 

Sample Input
3124
 

 

Sample Output
129
 

 

Source
BestCoder Round #81 (div.2)
思路：把n步当成最多往右走[n/2]步，最多往左走[n/2]步，当成火车出栈和入栈，卡特兰数，枚举到[n/2];
#include<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14const int N=2e5+10,M=4e6+10,inf=1e9+10,mod=1e9+7;const ll INF=1e18+10;ll a[M];ll inv[M];void init(){    inv[1] = 1;    for(int i=2;i<=1000010;i++)    {        if(i >= mod)break;        inv[i] = (mod - mod / i) * inv[mod % i]% mod;    }}ll c[M];int main(){    a[0]=1;    init();    for(ll i=1;i<=1000000;i++)    {        a[i]=(((a[i-1]*(4*i-2))%mod)*inv[i+1])%mod;    }    int T,cas=1;    scanf("%d",&T);    while(T--)    {        int n;        scanf("%d",&n);        c[0]=1;        for(int i=1,t=n;i<=n;t--,i++)        {            c[i]=(((c[i-1]*t)%mod)*inv[i])%mod;        }        ll ans=0;        for(int i=0;i*2<=n;i++)        {            ans=(ans+(a[i]*c[2*i])%mod)%mod;        }        printf("%lld\n",ans);    }    return 0;}

 

hdu 5673 Robot 卡特兰数+逆元


联系
我们