51nod 1120 机器人走方格V3

1120 机器人走方格 V3 

基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题

 收藏

 关注

N * N的方格，从左上到右下画一条线。一个机器人从左上走到右下，只能向右或向下走。并要求只能在这条线的上面或下面走，不能穿越这条线，有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10007的结果。

Input

输入一个数N(2 <= N <= 10^9)。

Output

输出走法的数量 Mod 10007。

Input示例

4

Output示例

10

#include<bits/stdc++.h>

#define MOD 10007

using namespace std;

typedef long long ll;

ll inv(ll t, ll p)

{//求t关于p的逆元，注意:t要小于p，最好传参前先把t%p一下

    return t == 1 ? 1 : (p - p / t) * inv(p % t, p) % p;

}

ll f[MOD+3];

void init(int p)

{       //f[n] = n!

    f[0] = 1;

    for (int i=1; i<=p; ++i) f[i] = f[i-1] * i % p;

}

ll pow_mod(ll a, ll x, int p)

{

    ll ret = 1;

    while (x)

        {

        if (x & 1)  ret = ret * a % p;

        a = a * a % p;

        x >>= 1;

    }

    return ret;

}

ll Lucas(ll n, ll k, int p)        //C (n, k) % p

{

     ll ret = 1;

     while (n && k)

        {

        ll nn = n % p, kk = k % p;

        if (nn < kk) return 0;  //inv (f[kk]) = f[kk] ^ (p - 2) % p

        ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - 2, p) % p;

        n /= p, k /= p;

     }

     return ret;

}

int main(void)

{

    init (10007);

    ll n;

    cin>>n;

    n--;

    ll ans=Lucas(2*n,n,MOD);

    ll temp=(n+1)%MOD;//使用inv函数前%一下

    ans=(ans*inv(temp,MOD))%MOD;

    ans=(ans*2)%MOD;

    cout<<ans<<endl;

    return 0;

}

51nod 1120 机器人走方格V3的相关教程结束。