51nod 1120 機器人走方格V3 卡特蘭數+盧卡斯定理

點這裡

忘了好久的公式。。。終于想起來查

卡特蘭數

卡特蘭數計算公式C(2n-2,n-1)/n或C(2n,n)-C(2n,n-1)

盧卡斯定理 用于大組合數取模運算

ans=(C(2n-2,n-1)/n)%mod

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long ll;
const int maxn= 10010;
const int mod=10007;
int  f[10020];
void init()
{
          f[0]=1;
    for(int i=1;i<=maxn;i++)
        f[i]=(i*f[i-1])%mod;

}

long long pow1(long long  n,long long m )
{
    long long ans = 1;
    while(m > 0)
    {
        if(m & 1)ans = (ans * n) % mod;
        m = m >> 1;
        n = (n * n) % mod;}
    return ans;
}
long long lucas(ll n,ll m)
{
     ll ans=1;
     while(n&&m)
     {
         ll x,y;
         x=n%mod;y=m%mod;
         if(x<y)
           return 0;
           //printf("%lld %lld %d %d %d\n",x,y,f[x],f[y],f[x-y]);
         ans=ans*f[x]*pow1(f[y]*f[x-y]%mod,mod-2)%mod;
         n/=mod;m/=mod;
     }
    return ans%mod;
}
int main()
{   init();
    ll n,m,t;
    //freopen("out.txt","w",stdout);
while(~scanf("%lld",&n))
{
    ll t=pow1(n,mod-2);
     printf("%lld\n",2*lucas(2*n-2,n-1)*t%mod);
}
    return 0;
}