题解 P1375 【小猫】

Karl_Aurora · 2020-03-20 12:46:08 · 题解

在看代码之前，我们先来了解一个组合数学里的经典数列——Catalan数

Catalan数一般的应用都有括号化、出栈次序、凸多边形三角划分、给定节点组成二叉搜索树、n对括号正确匹配数目等,定义如下：

设h(n)为Catalan数的第n+1项，令h(0)=1,h(1)=1，Catalan数满足递推式：

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)

例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2

h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

另有递推式：
h(n)=h(n-1)*(4*n-2)/(n+1);

递推式的解为：
h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

另有解为：
h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

看完定义，下面让我们回到这一题

这道题实质上等同于多边形三角剖分问题，是Catalan的一个经典例子，同时我们还要运用快速幂取模和乘法逆元进行优化计算，防止被卡

废话不多说，代码如下

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
inline long long read(){
    long long X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}//快读 
inline void write(long long x) {
    static long long stk[100], top = 0;
    if(x==0){putchar('0');return;}
    if(x<0){x=-x;putchar('-');}
    while(x){stk[++top]=x%10;x/=10;}
    while(top)putchar(stk[top--] ^ '0');
    return;
}//快输 
long long pow_mod(long long a,long long b){
    long long ret=1;
    while(b){
        if(b&1)ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}//快速幂 
long long mul_mod(long long a,long long b){
    a%=mod;b%=mod;
    long long c=a*b/mod;
    long long ans=a*b-c*mod;
    if(ans<0)ans+=mod;
    else if(ans>=mod)ans-=mod;
    return ans;
}//快速乘 
long long n,ans=1,x=1,y=1,z=1;
int main(){
    n=read();
    for(long long i=1;i<=2*n;i++){
        if(i<=n)y=mul_mod(y,i);
        if(i<=n+1)z=mul_mod(z,i);
        x=mul_mod(x,i);
        /*这里的卡特兰数初始化貌似有点玄学，
        我用三个for循环实现会玄学WA，
        于是参考了第一篇题解的写法*/ 
    }
    y=mul_mod(y,z);
    ans=mul_mod(x,pow_mod(y,mod-2));
    write(ans);
    return 0;
}
//实测吸氧后39ms956kb通过
//求资瓷