高斯消元

可以在 $O(n^3)$ 时间复杂度内 n 个未知数的求解多元线性方程组。

枚举每一列
找到绝对值最大的一行
将这行换到最上面
将该行第 1 个数变成 1
将下面所有行的当前列消成 0

将系数矩阵化成阶梯型，有三种情况

完美阶梯型，有唯一解
0 = 非零，无解
0 = 0，有无穷多个解

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 110;
const double eps = 1e-6;
int n;
double a[N][N];

int gauss() {
    int c, r;
    // 枚举每一列
    for(c=0, r=0; c<n;c++) {
        int t = r;
        // 枚举每一行，找到绝对值最大的主元
        for(int i=r;i<n;i++) {
            if(fabs(a[i][c]) > fabs(a[t][c])) {
                t=i;
            }
        }
        if(fabs(a[t][c]) < eps) continue;
        // 将该行换到第一行
        for(int i=c;i<=n;i++) swap(a[t][i], a[r][i]);
        // 将主元系数变为 1
        for(int i=n;i>=c;i--) a[r][i]/=a[r][c];
        // 将其他列的系数消成 0
        for(int i=r+1;i<n;i++) {
            if(fabs(a[i][c]) > eps) {
                for(int j=n;j>=c;j--) {
                    a[i][j] -= a[r][j] * a[i][c];
                }
            }
        }
        r++;
    }

    if(r<n) {
        for(int i=r;i<n;i++) {
            if(fabs(a[i][n]) > eps) {
                return 2;
            }
        }
        return 1;
    }
    for(int i=n-1;i>=0;i--) {
        for(int j=i+1;j<n;j++) {
            a[i][n] -= a[i][j] * a[j][n];
        }
    }
    return 0;
}

int main() {
    cin >> n;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n+1;j++) {
            cin >> a[i][j];
        }
    }
    int t = gauss();
    if(t == 0) {
        for(int i=0;i<n;i++) printf("%.2lf\n", a[i][n]);
    } else if (t == 1) {
        puts("Infinite group solutions");
    } else {
        puts("No solution");
    }
    return 0;
}

组合数

$C_a^b (0 \le b \le a)$ 表示从 a 个元素中挑选 b 个元素的方案数。

组合数的计算公式为： $C_a^b = C_{a-1}^b + C_{a-1}^{b-1}$
含义为：假设有 a 个苹果，需要从里面挑出 b 个。先挑 1 个出来，记作 x，那么有两种方案，要么挑出来的 b 个苹果中包含 x，此时需要再从 a-1 个苹果中挑 b-1 个，要么不包含 x，此时需要再从 a-1 个苹果中挑 b 个，两种方案相加。

求组合数 I

预处理每个 $C_a^b$ ，利用递推公式求组合数。

#include <iostream>
using namespace std;

const int N = 2010, mod = 1e9+7;

int c[N][N];

int main() {
    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 n;
    cin >> n;
    while(n--) {
        int a, b;
        cin >> a >> b;
        cout << c[a][b] << endl;
    }
    return 0;
}

求组合数 II

预处理阶乘和阶乘的逆元，利用定义计算组合数

求组合数 III

使用卢卡斯定理：
$C_a^b \equiv C_{a \mod p}^{b \mod p} \cdot C_{a/p}^{b/p} \pmod {p}$

#include <iostream>
using namespace std;
typedef long long LL;
int p;

int qmi(int a, int k) {
  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 res = 1;
  for (int i = 1, j = a; i <= b; i++, j--) {
    res = (LL)res * j % p;
    // 除以 i 变成乘以 i 的逆元
    res = (LL)res * qmi(i, p - 2) % p;
  }
  return res;
}

// 这个求组合数的方法很妙
int C2(int a, int b) {
  int res = 1;
  for (int i = 1, j = a; i <= b; i++, j--) {
    res = (LL)res * j / i;
  }
  return res;
}

int lucas(LL a, LL b) {
  if (a < p && b < p) return C(a, b);
  return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main() {
  int n;
  cin >> n;
  while (n--) {
    LL a, b;
    cin >> a >> b >> p;
    cout << lucas(a, b) << endl;
  }
  return 0;
}