星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P1976 【鸡蛋饼】

posted on 2017-09-08 13:18:16 | under 题解 |

关于卡特兰数的定义和概念,本题解不再赘述,楼下的几位大佬们已经讲得很清楚了。

这里给出快速幂求逆元的代码。【终于不用写扩欧了

#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;
}