机器人走方格 V3 51Nod - 1120

本文主要是介绍机器人走方格 V3 51Nod - 1120，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.51nod.com/Challenge/Problem.html#!#problemId=1120

学到了卡特兰数 这道题可以转换成出栈次序问题

https://blog.csdn.net/wu_tongtong/article/details/78161211

https://baike.baidu.com/item/卡特兰数/6125746?fr=aladdin

 

还有就是模数太小 求组合数得用卢卡斯定理 即c(n,k)%mod=(c(n/mod,k/mod)*c(n%mod,k%mod))%mod

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e4+7;
const int maxn=1e4+10;ll pre[maxn];void init()
{ll i;pre[0]=1;for(i=1;i<=10006;i++) pre[i]=(pre[i-1]*i)%mod;
}ll quickpow(ll a,ll b)
{ll res;res=1;while(b>0){if(b%2) res=(res*a)%mod;a=(a*a)%mod,b/=2;}return res;
}ll getcnk(ll n,ll k)
{return (pre[n]*quickpow(pre[k],mod-2)*quickpow(pre[n-k],mod-2))%mod;
}ll lucas(ll n,ll k)
{ll res;res=getcnk(n%mod,k%mod);while(n/mod>=mod||k/mod>=mod){n/=mod,k/=mod;res=(res*getcnk(n%mod,k%mod))%mod;}res=(res*getcnk(n/mod,k/mod))%mod;return res;
}int main()
{ll n;init();scanf("%lld",&n);n--;printf("%lld\n",(2ll*lucas(2*n,n)*quickpow(n+1,mod-2))%mod);return 0;
}

 

这篇关于机器人走方格 V3 51Nod - 1120的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---