P1375 小猫【洛谷算法习题】
P1375 小猫
网页链接
P1375 小猫
题目描述
有2 n 2n2n只小猫站成一圈，主人小明想把它们两两之间用绳子绑住尾巴连在一起。同时小明是个完美主义者，不容许看到有两根绳子交叉。请问小明有几种连线方案，可以把让所有小猫两两配对？
方案数很大，仅需输出方案数模10 9 + 7 10^9+7109+7（一个质数）的值。
输入格式
输入共一行，一个整数n nn。
输出格式
输出方案数对10 9 + 7 10^9+7109+7取模后的值。
输入输出样例 #1
输入 #1
3输出 #1
5说明/提示
数据范围
- 对于60 % 60\%60%的数据，1 ≤ N ≤ 100 1\le N \le 1001≤N≤100。
- 对于100 % 100\%100%的数据，1 ≤ N ≤ 10 5 1\le N \le 10^51≤N≤105。
解题思路
本题是卡特兰数的经典应用——圆周非交叉完美匹配问题，通过卡特兰数通项公式结合模逆元即可高效求解。
模型转化与卡特兰数对应
2n只小猫围成一圈、两两连线不交叉，等价于「圆周上2n个点的非交叉完美匹配」，方案数恰好对应第n个卡特兰数。
推导：固定任意一个起点，若它与第2k个点配对，这条连线会将圆周分割为两个独立的子区域，分别包含2(k-1)和2(n-k)个点，子区域各自独立配对。方案数满足递推关系：
f ( n ) = ∑ i = 0 n − 1 f ( i ) ⋅ f ( n − 1 − i ) f(n) = \sum_{i=0}^{n-1} f(i) \cdot f(n-1-i)f(n)=i=0∑n−1f(i)⋅f(n−1−i)
初始条件f ( 0 ) = 1 f(0)=1f(0)=1，与卡特兰数的递推定义完全一致。卡特兰数通项与模运算处理
第n项卡特兰数的通项公式为：
C a t ( n ) = 1 n + 1 ( 2 n n ) Cat(n) = \frac{1}{n+1} \binom{2n}{n}Cat(n)=n+11(n2n)
由于模数10 9 + 7 10^9+7109+7是质数，除法需转化为模意义下的乘法逆元。根据费马小定理，x xx的逆元为x m o d − 2 m o d m o d x^{mod-2} \bmod modxmod−2modmod，因此公式可改写为：
C a t ( n ) = ( 2 n n ) × i n v ( n + 1 ) ( m o d m o d ) Cat(n) = \binom{2n}{n} \times inv(n+1) \pmod{mod}Cat(n)=(n2n)×inv(n+1)(modmod)组合数快速计算
- 预处理阶乘数组：线性递推得到0 ! ∼ 2 n ! 0! \sim 2n!0!∼2n!的模值，时间复杂度O ( n ) O(n)O(n)。
- 组合数计算：( a b ) = f a c t [ a ] × i n v ( f a c t [ b ] ) × i n v ( f a c t [ a − b ] ) ( m o d m o d ) \binom{a}{b} = fact[a] \times inv(fact[b]) \times inv(fact[a-b]) \pmod{mod}(ba)=fact[a]×inv(fact[b])×inv(fact[a−b])(modmod)，通过快速幂计算阶乘的逆元。
算法总时间复杂度为O ( n ) O(n)O(n)，完全适配n ≤ 10 5 n \le 10^5n≤105的数据约束。
总结
核心逻辑：将圆周非交叉配对问题映射为卡特兰数模型，通过阶乘预处理与费马小定理求逆元，快速计算组合数得到最终方案数。
关键操作：卡特兰数模型对应、阶乘线性预处理、快速幂求逆元、模运算下的组合数计算。
效率保障：线性时间预处理阶乘，单次查询常数时间计算，十万级数据无运行压力。
代码简要说明
- 快速幂函数
qpow：实现模意义下的快速幂运算，用于计算乘法逆元。 - 阶乘初始化
init：递推计算阶乘数组c，c[i]存储i ! m o d m o d i! \bmod modi!modmod，从0到最大长度依次线性计算。 - 组合数函数
C：基于阶乘与逆元计算组合数( n m ) \binom{n}{m}(mn)，分别乘以分子阶乘、分母两个阶乘的逆元，全程取模保证结果合法。 - 卡特兰数函数
Catalan：先计算组合数( 2 n n ) \binom{2n}{n}(n2n)，再乘以n + 1 n+1n+1的模逆元，得到第n项卡特兰数。 - 主函数：读取n值，完成阶乘预处理，调用卡特兰数函数计算结果并输出。
- 输入优化：关闭同步流并解绑tie，提升输入输出效率。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll maxn=200005;constll maxs=200002;ll f[maxn],c[maxn],ans;llqpow(ll a,ll x){ll r=1;while(x){if(x&1)r=r*a%mod;a=a*a%mod;x>>=1;}returnr;}voidinit(){c[0]=1;for(ll i=1;i<=maxs;i++)c[i]=c[i-1]*i%mod;}llC(ll n,ll m){returnc[n]*qpow(c[m],mod-2)%mod*qpow(c[n-m],mod-2)%mod;}llCatalan(ll n){returnC(2*n,n)*qpow(n+1,mod-2)%mod;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cin>>n;init();cout<<Catalan(n)<<endl;return0;}