题解 P1976 【鸡蛋饼】
teafrogsf
2017-09-08 13:18:16
关于卡特兰数的定义和概念,本题解不再赘述,楼下的几位大佬们已经讲得很清楚了。
这里给出**快速幂**求逆元的代码。~~【终于不用写扩欧了~~
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
#define mod 100000007
ll cal[1000010]={1,1},n;
ll slowpow(ll m,ll n)
{
long long b=1;
while (n > 0)
{
if(n&1)b=(b*m)%mod;
n>>=1;
m=(m*m)%mod;
}
return b;
}
int main()
{
ll x,y;
scanf("%lld",&n);
f(i,2,n<<1)cal[i]=(cal[i-1]*i)%mod;
printf("%lld\n",(((cal[n<<1]%mod)*slowpow(cal[n+1],mod-2))%mod*slowpow(cal[n],mod-2))%mod);
return 0;
}
```