1.利用递推式预处理组合数取模
题目描述
给定
n
n
n 组询问，每组询问给定两个整数
a
,
b
a, b
a,b，请你输出
C
a
b
m
o
d
(
1
0
9
+
7
)
C_a^b \ mod \ (10^9+7)
Cab mod (109+7) 的值。
数据范围
1
≤
n
≤
10000
1 \le n \le 10000
1≤n≤10000
1
≤
b
≤
a
≤
2000
1 \le b \le a \le 2000
1≤b≤a≤2000
递推式
C
a
b
=
C
a
−
1
b
+
C
a
−
1
b
−
1
C_a^b = C_{a-1}^{b}+C_{a-1}^{b-1}
Cab=Ca−1b+Ca−1b−1
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int c[N][N];
void init()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j <= i; j++)
{
if (!j)
{
c[i][j] = 1;
}
else
{
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
}
}
int main()
{
init();
int n;
scanf("%d", &n);
while (n--)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", c[a][b]);
}
return 0;
}
2.预处理阶乘的余数和阶乘逆元的余数
题目描述
给定
n
n
n 组询问，每组询问给定两个整数
a
,
b
a, b
a,b，请你输出
C
a
b
m
o
d
(
1
0
9
+
7
)
C_a^b\ mod\ (10^9+7)
Cab mod (109+7) 的值。
数据范围
1
≤
n
≤
10000
1 \le n \le 10000
1≤n≤10000
1
≤
b
≤
a
≤
1
0
5
1 \le b \le a \le 10^5
1≤b≤a≤105
逆元
若
a
∗
x
≡
1
(
m
o
d
b
)
a ∗ x ≡ 1 \ (mod \ b)
a∗x≡1 (mod b) 且
a
a
a 与
b
b
b 互质，那么我们就能定义
x
x
x 为
a
a
a 的逆元，记为
a
−
1
a^{−1}
a−1，所以我们也可以称
x
x
x 为
a
a
a 在
m
o
d
b
mod\ b
mod b 意义下的倒数。
因此，对于
a
b
(
m
o
d
p
)
\frac{a}{b}\ (mod\ p)
ba (mod p)，我们就可以求出
b
b
b 在
m
o
d
p
mod\ p
mod p 下的逆元，然后乘上
a
a
a，再
m
o
d
p
mod\ p
mod p，就是这个分数的值了。
快速幂求逆元
这个做法要利用费马小定理，如下：
若
p
p
p 为素数，
a
a
a 为正整数，且
a
a
a、
p
p
p 互质，则有
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p−1} ≡ 1 \ (mod \ p)
ap−1≡1 (mod p)。
可以发现这个式子右边刚好为
1
1
1，因此，代入原式即可得到：
a
∗
x
≡
1
(
m
o
d
p
)
a ∗ x ≡ 1\ (mod\ p)
a∗x≡1 (mod p)
a
∗
x
≡
a
p
−
1
(
m
o
d
p
)
a ∗ x ≡ a^{p−1}\ (mod\ p)
a∗x≡ap−1 (mod p)
x
≡
a
p
−
2
(
m
o
d
p
)
x ≡ a^{p−2}\ (mod\ p)
x≡ap−2 (mod p)
所以我们可以用快速幂来算出
a
p
−
2
(
m
o
d
p
)
a^{p−2}\ (mod\ p)
ap−2 (mod p) 的值，这个数就是它的逆元了。
组合数
C
a
b
=
a
∗
(
a
−
1
)
∗
.
.
.
∗
(
a
−
b
+
1
)
b
∗
(
b
−
1
)
∗
.
.
.
∗
1
=
a
!
b
!
∗
(
a
−
b
)
!
C_a^b = \frac{a*(a-1)*...*(a-b+1)}{b*(b-1)*...*1} = \frac{a!}{b!*(a-b)!}
Cab=b∗(b−1)∗...∗1a∗(a−1)∗...∗(a−b+1)=b!∗(a−b)!a!
首先，预处理阶乘的余数和阶乘逆元的余数：
f
a
c
t
[
i
]
=
(
i
!
)
m
o
d
(
1
0
9
+
7
)
fact[i] = (i!)\ mod \ (10^9+7)
fact[i]=(i!) mod (109+7)
i
n
f
a
c
t
[
i
]
=
(
i
!
)
−
1
m
o
d
(
1
0
9
+
7
)
infact[i] = (i!)^{-1}\ mod\ (10^9+7)
infact[i]=(i!)−1 mod (109+7)
那么，组合数求解如下：
C
a
b
=
f
a
c
t
[
a
]
∗
i
n
f
a
c
t
[
b
]
∗
i
n
f
a
c
t
[
a
−
b
]
C_a^{b} = fact[a]*infact[b]*infact[a-b]
Cab=fact[a]∗infact[b]∗infact[a−b]
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 100010, mod = 1e9 + 7;
int fact[N], infact[N];
int qmi(int a, int b, int m)
{
int res = 1;
while (b)
{
if (b & 1) res = (ll)res * a % mod;
a = (ll)a * a % mod;
b >>= 1;
}
return res;
}
int main()
{
// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = 1, infact[0] = 1;
for (int i = 1; i < N; i++)
{
fact[i] = (ll)fact[i - 1] * i % mod;
infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
int n;
scanf("%d", &n);
while (n--)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", (ll)fact[a] * infact[b] % mod * infact[a - b] % mod);
}
return 0;
}
3.卢卡斯定理
题目描述
给定
n
n
n 组询问，每组询问给定三个整数
a
,
b
,
p
a,b,p
a,b,p，其中
p
p
p 是质数，请你输出
C
a
b
m
o
d
p
C_a^b\ mod\ p
Cab mod p 的值。
数据范围
1
≤
n
≤
20
1 \le n \le 20
1≤n≤20
1
≤
b
≤
a
≤
1
0
18
1 \le b \le a \le 10^{18}
1≤b≤a≤1018
1
≤
p
≤
1
0
5
1 \le p \le 10^5
1≤p≤105
Lucas定理
若
p
p
p 是质数，则对于任意整数
1
≤
m
≤
n
1 \leq m \leq n
1≤m≤n 有
C
n
m
≡
C
n
m
o
d
p
m
m
o
d
p
∗
C
n
/
p
m
/
p
(
m
o
d
p
)
C_n^m \equiv C_{n\ mod\ p}^{m\ mod \ p}*C_{n/p}^{m/p}\ (mod\ p)
Cnm≡Cn mod pm mod p∗Cn/pm/p (mod p)。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
// 快速幂模板
int qmi(int a, int b, int p)
{
int res = 1;
while (b)
{
if (b & 1) res = (ll)res * a % p;
a = (ll)a * a % p;
b >>= 1;
}
return res;
}
// 通过定义求组合数C(a, b)
int C(int a, int b, int p)
{
if (b > a) return 0;
int res = 1;
for (int i = 1, j = a; i <= b; i++, j--)
{
res = (ll)res * j % p;
res = (ll)res * qmi(i, p - 2, p) % p;
}
return res;
}
int lucas(ll a, ll b, int p)
{
if (a < p && b < p) return C(a, b, p);
return (ll)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
int main()
{
int n;
scanf("%d", &n);
while (n--)
{
ll a, b;
int p;
scanf("%lld%lld%d", &a, &b, &p);
printf("%d\n", lucas(a, b, p));
}
return 0;
}
4.将组合数分解质因数+高精度乘低精度
题目描述
输入
a
,
b
a, b
a,b，求
C
a
b
C_a^b
Cab 的值。注意结果可能很大，需要使用高精度计算。
数据范围
1
≤
b
≤
a
≤
5000
1 \le b \le a \le 5000
1≤b≤a≤5000
思路
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用。
C
a
b
=
a
∗
(
a
−
1
)
∗
.
.
.
∗
(
a
−
b
+
1
)
b
∗
(
b
−
1
)
∗
.
.
.
∗
1
=
a
!
b
!
∗
(
a
−
b
)
!
C_a^b = \frac{a*(a-1)*...*(a-b+1)}{b*(b-1)*...*1} = \frac{a!}{b!*(a-b)!}
Cab=b∗(b−1)∗...∗1a∗(a−1)∗...∗(a−b+1)=b!∗(a−b)!a!
首先筛选出范围内的所有质数，然后将组合数分解质因数为
p
1
c
1
∗
p
2
c
2
∗
.
.
.
∗
p
k
c
k
p_1^{c_1} * p_2^{c_2} * ... * p_k^{c_k}
p1c1∗p2c2∗...∗pkck，最后用高精度乘法将所有质因子乘起来即可。
如何求
n
!
n!
n! 中有多少个质因子
p
p
p 呢？
⌊
n
p
⌋
+
⌊
n
p
2
⌋
+
⌊
n
p
3
⌋
+
.
.
.
\lfloor \frac{n}{p} \rfloor+\lfloor \frac{n}{p^2} \rfloor+\lfloor \frac{n}{p^3} \rfloor+...
⌊pn⌋+⌊p2n⌋+⌊p3n⌋+...
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 5010;
int primes[N], cnt;
bool st[N];
int sum[N];
// 线性筛
void get_primes(int n)
{
for (int i = 2; i <= n; i++)
{
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= n / i; j++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
// 求n!中有多少个质因子p
int get(int n, int p)
{
int res = 0;
while (n)
{
res += n / p;
n /= p;
}
return res;
}
// 高精度乘以低精度
vector<int> mul(vector<int> a, int b)
{
vector<int> c;
int t = 0;
for (int i = 0; i < a.size(); i++)
{
t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (t)
{
c.push_back(t % 10);
t /= 10;
}
return c;
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
get_primes(a);
for (int i = 0; i < cnt; i++)
{
int p = primes[i];
sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}
vector<int> res;
res.push_back(1);
for (int i = 0; i < cnt; i++)
{
for (int j = 0; j < sum[i]; j++)
{
res = mul(res, primes[i]);
}
}
for (int i = res.size() - 1; i >= 0; i--)
{
printf("%d", res[i]);
}
return 0;
}
