题解 P1375 小猫

tytyty · 2021-12-04 21:26:45 · 题解

题意

一个圆上有 2n 个点，用 n 条线段把这些点连起来（每个点只连一条线段），使所有的线段都不相交，问有多少种连线方案。

思路

本题是一道 Catalan 数的模板。

我们知道 Catalan 数的应用有：进出栈序列，括号序列，凸多边形三角划分，n 个节点的二叉搜索树等。

这里将点顺（逆）时针从 1-2n 标号，画图可以发现奇偶性相同的点是不能连线的（因为这样会交叉），所以必须奇数点与偶数点，问题转化为括号序列问题。

Catalan 数通项式：C_n=\dfrac {C_{2n}^n}{n+1}。另外此题还要用到逆元和快速幂。

Code

#include<bits/stdc++.h>
#define ll long long//记得开long long
using namespace std;
const int p=1000000007;
int n;
ll inv;//逆元
ll power(ll x,ll y)
{
    ll ret=1;
    while(y)
    {
        if(y&1)
            ret=ret*x%p;
        x=x*x%p;
        y>>=1;
    }
    return ret;
}
ll c()
{
    ll fz=1,fm=1;
    for(int i=n+1;i<=2*n;i++)//化简后
    {
        fz=fz*i%p;
    }
    for(int i=1;i<=n;i++)
    {
        fm=fm*i%p;
    }
    fm=power(fm,p-2);//求逆元
    return fz*fm%p;
}
int main()
{
    scanf("%d",&n);
    inv=power(n+1,p-2);
    printf("%d",c()*inv%p);
    return 0;
}

PS:

双倍经验

一道神奇的题目：有趣的序列