题解 P1976 【鸡蛋饼】

关于卡特兰数的定义和概念，本题解不再赘述，楼下的几位大佬们已经讲得很清楚了。 这里给出**快速幂**求逆元的代码。~~【终于不用写扩欧了~~ ```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; } ```