P1976 鸡蛋饼

曾经lofter上的文章。搬运 卡特兰数裸题。 因为范围不明所以用$\frac{C(2n,n)}{(n+1)}$，逆元解决。 【但最后神TM发现都过了 其实讲道理吧。 我写完之后自己也不是很清楚是怎么写的ORZ 一直很奇怪，就是在没爆long long的情况下，快速幂求逆元居然错了？ 【现在想了想可能与$\frac{}{(n+1)}$有关系，但还是希望大佬解答。 所以我只好写我一点都不会写的扩展欧几里得了。所以一脸懵逼。 ```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=1,cald=1,n; void exeuclid(ll a,ll b,ll &x,ll &y) { if(!b)x=1,y=0; else exeuclid(b,a%b,y,x),y-=x*(a/b); } int main() { ll x,y; scanf("%lld",&n); f(i,1,n)cal=(cal*(i+n))%mod,cald=(cald*i)%mod; cald=(cald*(n+1))%mod; exeuclid(cald,mod,x,y);x=(x%mod+mod)%mod; printf("%lld",(cal*x)%mod); return 0; } ``` 写出来了ORZ 快速幂版的卡特兰数。 令人激动。 ```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; } ```