2.组合数学

2.1预处理组合数

2.1.1递推求组合数 O($n^2$)

原理：$C_{a}^{b} = C_{a - 1}^{b} + C_{a - 1}^{b - 1}$

// a, b <= 1e3
void init()
{
    for(int i = 0; i < N; i ++)
        for(int j = 0; j <= i; j ++)
            if(!j) f[i][j] = 1;
            else f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % mod;
}

2.1.2快速幂(逆元)求组合数 O(a * log(mod))

// a b <= 1e6
const int N = 100010, mod = 1e9 + 7;

int fact[N], infact[N];

int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 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;
}

2.1.3卢卡斯定理求组合数 O($log_p(N)plog(p)$)

卢卡斯定理：$C_a^b \equiv C_{a mod p}^{b mod p} * C_{\frac{a}{p}}^{\frac{b}{p}}$

// a b <= 1e18, p <= 1e5
int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

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;
}

2.1.4高精度求组合数

为了简化，可以求出来每个质因子的次方，最后只写一个乘法的高精度

const int N = 5010;

int primes[N], cnt;
int sum[N];
bool st[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] * i <= n; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

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;
    cin >> a >> b;

    get_primes(a);

    for(int i = 0; i < cnt; i ++)
    {
        int p = primes[i];
        sum[i] = get(a, p) - get(a - b, p) - get(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]);
    puts("");

    return 0;
}

2.2卡特兰数 $\frac{C_{2n}^{n}}{n + 1}$

如果发现n = 3, ans = 5, 便可以猜测是卡特兰数

其他方法
1.递推式
f(n) = f(1) * f(n - 1) + f(2) * f(n - 2) + …
应用：二叉树的个数
2.挖掘性质
任意前缀中某种东西的个数 >= 另一种东西

/
acwing 1315
某城市的街道呈网格状，左下角坐标为 A(0,0)，右上角坐标为 B(n,m)，其中 n ≥ m。
现在从 A(0,0) 点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点 (x,y) 都要满足 x ≥ y，请问在这些前提下，到达 B(n,m) 有多少种走法。
/

将 (n, m) 按照y = x + 1做对称

(n, m) -> (n, m - 1) -> (m - 1, n) -> (m - 1, n + 1)

(n, m) <=> $C_{m + n}^{n}$

(m - 1, n + 1) <=> $C_{m + n}^{m - 1}$

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int primes[N], cnt;
bool st[N];
int a[N], b[N];

void init(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] * i <= n; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int get(int n, int p)
{
    int s = 0;
    while(n) s += n / p, n /= p;
    return s;
}

void mul(int r[], int &len, int x)
{
    int t = 0;
    for(int i = 0; i < len; i ++)
    {
        t += r[i] * x;
        r[i] = t % 10;
        t /= 10;
    }

    while(t)
    {
        r[len ++] = t % 10;
        t /= 10;
    }
}

void sub(int a[], int al, int b[], int bl)
{
    for(int i = 0, t = 0; i < al; i ++)
    {
        a[i] = a[i] - (t + b[i]);
        if(a[i] < 0)
        {
            a[i] += 10;
            t = 1;
        }
        else t = 0;
    }
}

int C(int x, int y, int r[N])
{
    int len = 1;
    r[0] = 1;

    for(int i = 0; i < cnt; i ++)
    {
        int p = primes[i];
        int s = get(x, p) - get(y, p) - get(x - y, p);
        while(s --) mul(r, len, p);
    }

    return len;
}

int main()
{
    init(N - 1);

    int n, m;
    cin >> n >> m;
    int al = C(n + m, m, a);
    int bl = C(n + m, n + 1, b);

    sub(a, al, b, bl);

    int k = al - 1;
    while(!a[k] && k > 0) k --;
    while(k >= 0) printf("%d", a[k --]);

    return 0;
}

2.3错位排列

定义：错位排列是指没有任何元素出现在其有序位置的排列。即 $a_i != i$

思路：递推（参考oi-wiki）

对于n封不同的信的错位排列

分为两种情况讨论

第一种：前面 n - 1个信封全部装错

第二种：前面 n - 1个信封有一个没有装错，其余全部装错

则对于第一种情况，因为前面 n - 1个已经全部装错了，所以第n封只需要与前面任意一个交换位置即可，共有$D_{n - 1} * (n - 1)$

对于第二种情况，若n - 1个信封中如果有一个没有装错，那么把那个没有装错与n交换，即可得到一个全错位排列情况

其他情况，不可能通过==一次操作==来把它变成一个长度为n的错排

故得到递推式，$D_{n} = (n - 1) * (D_{n - 1} + D_{n - 2})$

D[0] = 1, D[1] = 0, D[2] = 1;
for(int i = 3; i < N; i ++)
    D[i] = (LL)(i - 1) * (((LL)D[i - 1] + D[i - 2]) % mod) % mod;