当前位置：首页 > web >正文

洛谷 P1375：小猫 ← 预处理模逆元 + 卡特兰数

web 2025/5/17 6:59:41

【题目来源】
https://www.luogu.com.cn/problem/P1375

【题目描述】
有 2n 只小猫站成一圈，主人小明想把它们两两之间用绳子绑住尾巴连在一起。同时小明是个完美主义者，不容许看到有两根绳子交叉。请问小明有几种连线方案，可以把让所有小猫两两配对？
方案数很大，仅需输出方案数模 10^9+7（一个质数）的值。

【输入格式】
输入共一行，一个整数 n。

【输出格式】
输出方案数对 10^9+7 取模后的值。

【输入样例】
3

【输出样例】
5

【数据范围】
对于 60% 的数据，1≤N≤100。
对于 100% 的数据，1≤N≤10^5。

【算法分析】
（一）预处理 1~n 的模 p 逆元‌（详见：https://blog.csdn.net/hnjzsyjyj/article/details/147778571）
若在竟赛中需频繁计算 1, 2, …, n 的逆元，也可以用“逆元预处理“技巧。其可以仅需 O(n) 时间得到所有值的逆元。
● 预处理 1~n 的模 p 逆元‌的理论证明

定理：inv[i]=(p-p/i)*inv[p%i]%p，其中 p 为质数。
证明：设 k=p/i，r=p%i，则有 p=k*i+r
两边模 p 得：k*i+r≡0 (mod p) → i≡-r/k (mod p)
因此，inv[i]≡-k*inv[r] (mod p)。
之后，利用公式 (p+x%p)%p 将 inv[i]≡-k*inv[r] (mod p) 调整为对应的正数:
inv[i]=(p-k*inv[r]%p)%p=(p-(p/i)*inv[p%i]%p)%p。
由于 p≡0 (mod p)，故 (p-(p/i)*inv[p%i]%p)%p 可简化为：−(p/i)*inv[p%i]%p
又根据模运算性质 -x≡p-x(mod p)，
所以，−(p/i)*inv[p%i]%p 等价于 (p−(p/i)*inv[p%i])%p=(p−p/i)*inv[p%i]%p
综上，得证。

● 预处理 1~n 的模 p 逆元‌的模板代码：inv[i]=(p-p/i)*inv[p%i]%p

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=3e6+5;
LL inv[N];int main() {LL n,p;scanf("%lld %lld",&n,&p);inv[1]=1;for(int i=2; i<=n; i++) {inv[i]=(p-p/i)*inv[p%i]%p;}for(int i=1; i<=n; i++) {printf("%lld\n",inv[i]);}return 0;
}/*
in:
10 13out:
1
7
9
10
8
11
2
5
3
4
*/

（二）快速幂（详见：https://blog.csdn.net/hnjzsyjyj/article/details/143168167）
● 快速幂的模板代码

#include <bits/stdc++.h>
using namespace std;typedef long long LL;int fastPow(LL a,LL b,LL p) {LL ans=1;while(b) {if(b & 1) ans=ans*a%p;a=a*a%p;b>>=1;}return ans%p;
}int main() {int a,b,p;int T;cin>>T;while(T--) {cin>>a>>b>>p;cout<<fastPow(a,b,p)<<endl;}return 0;
}/*
in:
2
3 2 5
4 3 9out:
4
1
*/

（三）卡特兰数
● 卡特兰数（Catalan number）是组合数学中一个常出现在各种计数问题中的数列。若从第 0 项开始，则卡特兰数列 h[n] 为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, …。其中，常用的卡特兰数列 h[n] 有如下 4 种等价的递推式：
h[n]=h[0]*h[n−1]+h[1]*h[n−2]+...+h[n−1]*h[0], (n≥2, h[0]=h[1]=1)
h[n]=h[n−1]*(4*n−2)/(n+1), (n≥2)
h[n]=C(2n,n)−C(2n,n−1), (n=0,1,2,...)
h[n]=C(2n,n)/(n+1), (n=0,1,2,...)

● 卡特兰数的模板代码一
依据递推式 h[n]=h[n−1]*(4*n−2)/(n+1), (n≥2) 编码。

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn=1e5+5;
LL h[maxn];
LL n;int main() {scanf("%lld",&n);h[0]=1,h[1]=1;for(int i=2; i<=n; i++) {h[i]=h[i-1]*(4*i-2)/(i+1);}for(int i=0; i<=n; i++) {printf("%lld ",h[i]);}return 0;
}/*
in:6
out:1 1 2 5 14 42 132
*/

● 卡特兰数的模板代码二
依据递推式 h[n]=h[0]*h[n−1]+h[1]*h[n−2]+...+h[n−1]*h[0], (n≥2, h[0]=h[1]=1) 编码。

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn=1e5+5;
LL h[maxn];
LL n;int main() {scanf("%lld",&n);h[0]=1,h[1]=1;for(int i=2; i<=n; i++) {for(int j=0; j<=i-1; j++) {h[i]+=h[j]*h[i-j-1];}}for(int i=0; i<=n; i++) {printf("%lld ",h[i]);}return 0;
}/*
in:6
out:1 1 2 5 14 42 132
*/

【算法代码】

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int p=1e9+7;
const int maxn=1e5+5;
LL h[maxn],inv[maxn];
int n;int main() {scanf("%d",&n);inv[1]=1;for(int i=2; i<=n+1; i++) {inv[i]=(p-p/i)*inv[p%i]%p;}h[0]=h[1]=1;for(int i=2; i<=n; i++) {h[i]=h[i-1]*(4*i-2)%p*inv[i+1]%p;}printf("%lld",h[n]);return 0;
}/*
in:3
out:5
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/145842440
https://blog.csdn.net/hnjzsyjyj/article/details/129148916
https://www.luogu.com.cn/problem/U140713
https://www.luogu.com.cn/problem/P1375
https://www.luogu.com.cn/problem/P1976
https://www.luogu.com.cn/problem/P1044
https://www.luogu.com.cn/problem/P1641
https://blog.csdn.net/zsyz_ZZY/article/details/80418515