组合数取模总结

题目描述

ACM竞赛现在叫JB竞赛?中,经常会遇到组合数取模的题目;就我现在的水平而言,大概分为以下三类,以后遇到新的方法会在做补充;

第一种:

在这里插入图片描述
n和m都较小 (<1000),在这个数据范围内,我们可以直接用杨辉三角O(n^2)的复杂度内预处理出所有的组合数,然后直接输出即可;典型例题就是给你一个二项式,例如:
在这里插入图片描述
这样子的题目,组合数我们可以O(n^2)预处理出来(利用递推式子来处理)。a^b之类的东西我们可以用快速幂logn的复杂度内处理出来; 这种题由于数据范围过小,当水题处理就行;
代码大概是这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

#define MOD 10007
#define long long long

long pow_MOD(long a, long b)
{
long tmp = 1;
while(b)
{
if(b & 1)
{
tmp = (tmp % MOD * a % MOD) % MOD;
}
a = (a * a) % MOD;
b >>= 1;
}
return tmp;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int p, q, a, b, k;
cin >> p >> q >> k >> a >> b;
long tmp = 1;
for(int i = 1; i <= b; i++)
{
if(tmp % i == 0)
{
tmp = tmp / i * (k - i + 1) % MOD;
}
else
{
tmp = tmp * (k - i + 1) / i % MOD;
}
}
//cout << "tmp = " << tmp << endl;
cout << ((tmp % MOD) * (pow_MOD(p, a) % MOD) * (pow_MOD(q, b) % MOD)) % MOD;
return 0;
}

第二种

给定的n和m不太大 (1e5范围左右),给定的p较大(一般是1e9+7);这时候如果我们还是利用杨辉三角之类的东西就不行了;第一空间不足,没办法开出来1e51e5这么大的数组,第二在时间也是不允许的n^2的复杂度,肯定会T掉;所以我们需要利用线性方法递推组合数 公式大概是这样
在这里插入图片描述;
就是可以依赖前一项的组合数推出下一项的组合数,在O(n)的时间内可以出结果;但是,这里由于在求余过程中,除法是不具有同余性;即
(a + b) % mod = (a % mod + b % mod) % mod
(a - b) % mod = (a % mod - b % mod) % mod
(a
b) % mod = (a % mod b % mod) % mod
加法、减法、乘法都是有这个性质,只有除法不满足,所以中间直接模的话会出错;所以我们得预处理一下1-n关于p的逆元,把除法换为乘法。这样就没啥问题了;
显然,他一共要走n+m-2步,所以答案就是;但是受限于数据范围,我们得先预处理一下逆元,然后线性推组合数即可;
对了,处理逆元有很多种办法;
如果要求单个数字的逆元我们可以用扩展欧几里得或者快速幂(建议exgcd,更快点);
如果要处理的是一堆,就是1-n所有数字的逆元,我们可以用欧拉筛打出逆元表,或者直接利用递推inv[i] = (p - p / i)
(inv[p % i]) % p;这样子;
经典问题就是走迷宫之类的东西,例如:
在这里插入图片描述
我们先用线性推预处理逆元,然后用组合数的递推式递推组合数,即可AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

#define long long long
#define MOD 1000000007
#define N 1000010

long inv[N];

int main()
{
long n, m;
cin >> n >> m;
inv[1] = 1;
if(n > m)
swap(n, m);
for(int i = 2; i <= n; i++)
{
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
}
long tmp = 1, val = n + m - 2;
for(int i = 1; i <= n-1; i++)
{
tmp = tmp % MOD * (val - i + 1) % MOD * inv[i] % MOD;
}
cout << tmp << endl;
return 0;
}

第三种

第三种就是n和m都较大(1e9左右), p较小(1e5左右);这种情况下,第二种做法都不行了,这时候我们得用Lucas定理来解决;Lucas就是把大化小把一个大的组合数拆分为很多小的组合数乘积的结果;有兴趣可以了解一下;就是将n,m都改为p进制,然后累乘;这样子;
HDU-3037

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include <bits/stdc++.h>
using namespace std;

#define long long long
#define N 100010

long a[N], p;

long exgcd(long a, long b, long &x, long &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
long r = exgcd(b, a%b, x, y);
long tmp = x;
x = y;
y = tmp - a / b * y;
return r;
}

long C(long n, long m)
{
if(n < m)
return 0;
long x, x1, y, y1;
exgcd(a[m], p, x, y);
exgcd(a[n-m], p, x1, y1);
x = (x + p) % p;
x1 = (x1 + p) % p;
return ((a[n] % p) * x % p * x1 % p) % p;
}

long Lucas(long n, long m)
{
if(!m)
return 1;
return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}

int main()
{
int t;
cin >> t;
while(t--)
{
long n, m;
cin >> n >> m >> p;
a[0] = 1;
for(int i = 1; i <= p; i++)
{
a[i] = (a[i-1] * i) % p;
}
cout << Lucas(n+m, m) << endl;
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------