星星灰暗着。

星星灰暗着。

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

P1976 鸡蛋饼

posted on 2017-12-25 20:32:38 | under 题解 |

曾经lofter上的文章。搬运

卡特兰数裸题。

因为范围不明所以用 $\frac{C(2n,n)}{(n+1)}$ ,逆元解决。

【但最后神TM发现都过了

其实讲道理吧。

我写完之后自己也不是很清楚是怎么写的ORZ

一直很奇怪,就是在没爆long long的情况下,快速幂求逆元居然错了?

【现在想了想可能与 $\frac{}{(n+1)}$ 有关系,但还是希望大佬解答。

所以我只好写我一点都不会写的扩展欧几里得了。所以一脸懵逼。

    #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

快速幂版的卡特兰数。

令人激动。

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