P1375 小猫网页链接P1375 小猫题目描述有2 n 2n2n只小猫站成一圈主人小明想把它们两两之间用绳子绑住尾巴连在一起。同时小明是个完美主义者不容许看到有两根绳子交叉。请问小明有几种连线方案可以把让所有小猫两两配对方案数很大仅需输出方案数模10 9 7 10^971097一个质数的值。输入格式输入共一行一个整数n nn。输出格式输出方案数对10 9 7 10^971097取模后的值。输入输出样例 #1输入 #13输出 #15说明/提示数据范围对于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_{i0}^{n-1} f(i) \cdot f(n-1-i)f(n)i0∑n−1​f(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}{n1} \binom{2n}{n}Cat(n)n11​(n2n​)由于模数10 9 7 10^971097是质数除法需转化为模意义下的乘法逆元。根据费马小定理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(n1) \pmod{mod}Cat(n)(n2n​)×inv(n1)(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递推计算阶乘数组cc[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 n1n1的模逆元得到第n项卡特兰数。主函数读取n值完成阶乘预处理调用卡特兰数函数计算结果并输出。输入优化关闭同步流并解绑tie提升输入输出效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll maxn200005;constll maxs200002;ll f[maxn],c[maxn],ans;llqpow(ll a,ll x){ll r1;while(x){if(x1)rr*a%mod;aa*a%mod;x1;}returnr;}voidinit(){c[0]1;for(ll i1;imaxs;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(n1,mod-2)%mod;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cinn;init();coutCatalan(n)endl;return0;}