首页 algorithm 杂杂的算法知识

给定 n 组询问，每组询问给定两个整数 a，b，请你输出Cabmod  (1e9+7)C_a^b\mod(1e9 + 7) 的值。

# 求组合数 Ⅰ

时间复杂度：O (n2n^2)

1≤n≤10000,1≤b≤a≤20001\leq n\leq 10000,1\leq b\leq a\leq 2000

  1. 数据量较小，直接将所有可能初始化
  2. Cab=Ca−1b−1+Ca−1bC_a^b=C_{a-1}^{b-1}+C_{a-1}^b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
const int N = 2e3 + 10, mod = 1e9 + 7;
long long C[N][N];
int n;
void Init()
{
    for(int i = 0; i < N; i++)
        for(int j = 0; j <= i; j++)
            if(j == 0) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
int main()
{
    Init();
    cin >> n;
    while(n--)
    {
        int a, b;
        cin >> a >> b;
        cout << C[a][b] << '\n';
    }
    return 0;
}

# 求组合数 Ⅱ

时间复杂度：O (nlogn)

1≤n≤1000,1≤b≤a≤105,mod=1e9+71\leq n\leq 1000,1\leq b\leq a\leq 10^5,mod = 1e9 + 7

C_a^b=\frac{a!}{b!(a-b)!}=a!\times b!^{-1}\times (a-b)!^

b!^{-1} = ((b-1)!b)^{-1}=(b-1)!^{-1}b^-1 = (b-1)!^{-1}b^

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
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, mod = 1e9 + 7;
ll f[N], inf[N], n;//f用来存储阶乘，inf用来存储阶乘的逆元
ll qmi(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;
}
void Init()
{
    f[0] = inf[0] = 1;
    for(int i = 1; i < 1e5 + 10; i++)
    {
        f[i] = f[i - 1] * i % mod;
        inf[i] = inf[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}
int main()
{
    cin >> n;
    Init();
    while(n--)
    {
        int a, b;
        cin >> a >> b;
        cout << f[a] * inf[b] % mod * inf[a - b] % mod << '\n';
    }
    return 0;
}

# 求组合数 Ⅲ

（适合 p 较小）

给定 n 组询问，每组询问给定三个整数 a,b,pa,b,p 其中 p 是质数，请你输出Cabmod  pC_a^b\mod p 的值。

1\leq n\leq 20,1\leq b\leq a \leq 10^{18},1\leq p\leq 10^

lucas 定理：Cab=CapbpCa mod pb mod p(mod p)C_a^b = C_{\frac{a}{p}}^{\frac{b}{p}}C_{a\ mod\ p}^{b\ mod\ p}(mod\ p)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, p, n;
ll qmi(ll a, ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
ll C(ll a, ll b)
{
    if(b > a) return 0;
    ll res = 1;
    for(int i = 1, j = a; i <= b; i++, j--)
    {
        res = res * j % p;
        res = res * qmi(i, p - 2) % p;
    }
    return res;
}
ll lucas(ll a, ll b)
{
    if(a < p && b <p) return C(a, b);
    return C(a % p, b % p) * lucas(a / p, b / p) % p; 
}
int main()
{
    cin >> n;
    while(n--)
    {
        cin >> a >> b >> p;
        cout << lucas(a, b) << '\n';
    }
}

# 求组合数 Ⅳ

输入 a，b，求CabC_a^b，其中1≤b≤a≤50001\leq b\leq a\leq 5000

因为没有 mod，所以结果可能会很大，所以需要用高精度

但是如果直接用高精会超时，所以将Cab=a!b!(a−b)!C_a^b=\frac{a!}{b!(a-b)!} 中的a! b! (a−b)!−1a!\ b!\ (a-b)!^{-1} 用质因子进行表示，只进行上标的减法

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5100;
int prime[N], st[N], cnt, num[N];
int a, b;
void get_prime(int x)//筛质数
{
    for(int i = 2; i <= x; i++)
    {
        if(!st[i]) prime[cnt++] = i;;
        for(int j = 0; prime[j] <= x / i; j++)
        {
            st[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
}
int count(int p, int n)//数n中含多少个因子p
{
    int res = 0;
    while(n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}
vector<int> mul(const vector<int>& A, const int p)//高精度乘法
{
    if(p == 0) return {0};
    int t = 0;
    vector<int> res;
    for(int i = 0; i < A.size() || t > 0; i++)
    {
        if(i < A.size()) t += A[i] * p;
        res.push_back(t % 10);
        t /= 10;
    }
    while(res.size() > 0 && res.back() == 0) res.pop_back();
    return res;
}
int main()
{
    cin >> a >> b;
    get_prime(a);
    for(int i = 0; i < cnt; i++)
        num[i] = count(prime[i], a) - count(prime[i], b) - count(prime[i], a - b);
    vector<int> res = {1};
    for(int i = 0; i < cnt; i++)
        for(int j = 0; j < num[i]; j++)
            res = mul(res, prime[i]);
    for(int i = res.size() - 1; i >= 0; i--) cout << res[i];
    return 0;
}