博客

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

Input

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

Output

输出走法的数量 Mod 10007。

Sample Input

4

Sample Output

10

卡特兰数+卢卡斯+费马小定理：

分析：列举几个n就会发现，结果就是卡特兰数乘2

卡特兰数：

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

这里用到求卡特兰数的一个公式：h(n)=C(2n,n)-C(2n,n-1)(n=0,1,2,…)

然后其实这就是一个比较裸的卡特兰+卢卡斯模板。

#include <iostream>
#include <cstdio>
#include <string>
#include<cstring>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define N 205
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
int p=1e4+7;
//快速幂
ll quick_pow(ll n,ll m){
    ll ans=1;
    while (m){
        if(m&1)
            ans = ans * n % p;
        n=n*n%p;
        m>>=1;
    }
    return ans;
}
//求组合数C（n,m）
ll C(ll n,ll m){
       if(m>n)return 0;
       ll ans=1;
       for(int i=1;i<=m;i++){
           ll a =(n + i - m) % p;
           ll b = i % p;
           ans = ans * (a * quick_pow(b, p-2) % p) % p;
           //费马小定理求逆元
       }
       return ans;
}
//卢卡斯模板
ll lucas(ll n,ll m){
    if(!m)
        return 1;
    return C(n%p,m%p)*lucas(n/p,m/p)%p;
}
int main()
{
    ll n;cin>>n;
    n-=1;
    ll r=lucas(2*n,n);
    //求卡特兰数：f(n)=C(2n,n)-C(2n,n-1)
    ll es=lucas(2*n,n-1);
    ll res=(r-es+p)%p*2%p;
    cout<<res<<endl;
    return 0;
}