51nod 1120 机器人走方格 V3 【卡特兰数+卢卡斯定理+组合数】

…我并不知道为什么事卡特兰数，反正用dp打的表就是卡特兰数，因为是两个三角所以再乘个2

卡特兰数使用\( h(n)=\frac{C_{2n}^{n}}{n+1} \)因为范围比较大所以组合数部分用卢卡斯定理来求。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

using namespace std;

const int mod=10007,N=10020;

int n,fac[N],inv[N];

int ksm(int a,int b)

{

	a=a%mod;

	int r=1;

	while(b)

	{

		if(b&1)

			r=r*a%mod;

		a=a*a%mod;

		b>>=1;

	}

	return r;

}

int C(int n, int m)

{

    if(n<m)

        return 0;

    return fac[n]*inv[m]%mod*inv[n-m]%mod;

}

int lucas(int n,int m)

{

    return m==0?1:C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;

}

int main()

{

    fac[0]=1;

    for(int i=1;i<mod;i++)

        fac[i]=fac[i-1]*i%mod;

    inv[mod-1]=ksm(fac[mod-1],mod-2);

    for(int i=mod-2;i>=0;i--)

        inv[i]=inv[i+1]*(i+1)%mod;

    scanf("%d",&n);

    n--;

    printf("%d\n",(lucas(n<<1,n)+mod-lucas(n<<1,n-1))%mod*2%mod);

    return 0;

}

巴特西

51nod 1120 机器人走方格 V3 【卡特兰数+卢卡斯定理+组合数】

最新文章

热门文章