Acwing - 算法基础课 - 笔记（数学知识 · 三）（补）

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

int solve() {
	int c = 0, r = 0;
	for (; c < n; c++) {
        // 每轮循环消掉一列
		int t = r;
        // 先找到当前需要处理的列的最大系数的那一行
		for (int i = r + 1; i < n; i++) {
			if (fabs(a[i][c]) > fabs(a[t][c])) t = i;
		}
        // 当前列的最大系数为0, 则不用处理
		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];
		
        // 用该行消掉下面所有行的该列
		for (int i = r + 1; i < n; i++) {
			for (int j = n; j >= c; j--) {
				a[i][j] -= a[r][j] * a[i][c];
			}
		}
		// 有效方程数+1
		r++;
	}
	
	if (r < n) {
        // 有效方程数 < n, 可能是无解或无穷多解
		for (int i = r; i < n; i++) {
			if (fabs(a[i][n]) > eps) return 0; // 无解
		}
		return 2; // 无穷多解
	} else {
		// 唯一解
		for (int i = n - 1; i >= 0; i--) {
			for (int j = n - 1; j > i; j--) {
				a[i][n] -= a[i][j] * a[j][n];
			}
		}
		return 1;
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	
	int res = solve();
	if (res == 0) printf("No solution\n");
	else if (res == 2) printf("Infinite group solutions\n");
	else {
		for (int i = 0; i < n; i++) {
		    if (fabs(a[i][n]) < eps) a[i][n] = 0;
			printf("%.2lf\n", a[i][n]);
		}
	}
	return 0;
}

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

#include <iostream>
using namespace std;
const int N = 110;
int a[N][N];
int n;

int solve() {
	int c = 0, r = 0;
	for (; c < n; c++) {
        // 找到第一个系数非0的列
		int t = -1;
		for (int i = r; i < n; i++) {
			if (a[i][c] == 1) {
				t = i;
				break;
			}
		}
		if (t == -1) continue;
		// 交换到最上方
		for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);
		// 消掉下面方程的该列
		for (int i = r + 1; i < n; i++) {
            // 只有系数同样为1时才能消掉
			if (a[i][c] == 0) continue;
			for (int j = c; j <= n; j++) {
				a[i][j] = a[r][j] ^ a[i][j];
			}
		}
		r++;
	}
	
	if (r < n) {
		for (int i = r; i < n; i++) {
			if (a[i][n]) return 0;
		}
		return 2;
	} else {
		for (int i = n - 1; i >= 0; i--) {
			for (int j = n - 1; j > i; j--) {
                // 只有系数为1时, 需要异或上这个值
				if (a[i][j]) a[i][n] ^= a[j][n];
			}
		}
		return 1;
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	
	int res = solve();
	if (res == 0) printf("No solution\n");
	else if (res == 2) printf("Multiple sets of solutions\n");
	else {
		for (int i = 0; i < n; i++) {
			printf("%d\n", a[i][n]);
		}
	}
	return 0;
}

#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;

const int N = 2010;

int c[N][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] + c[i - 1][j - 1]) % MOD;
        }
    }
}

int main() {
    int n;
    cin >> n;
    init();
    while(n--) {
        int a, b;
        cin >> a >> b;
        cout << c[a][b] << endl;
    }
}

#include <iostream>
typedef long long LL;
using namespace std;
const int N = 100010, MOD = 1e9 + 7;

LL fac[N], infac[N];

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

void init() {
	fac[0] = infac[0] = 1;
	for (int i = 1; i < N; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		infac[i] = infac[i - 1] * qmi(i, MOD - 2, MOD) % MOD;
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	init();
	int n, a, b;
	cin >> n;
	while (n--) {
		cin >> a >> b;
		LL res = fac[a] * infac[a - b] % MOD * infac[b] % MOD;
		printf("%lld\n", res);
	}
	return 0;
}

// 1283ms
#include <iostream>
typedef long long LL;
using namespace std;

// 快速幂
LL qmi(LL a, LL b, LL p) {
	LL res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

// 小于p的组合数直接求
LL C(LL a, LL b, LL p) {
    if (b > a) return 0;
	LL res = 1;
	for (int i = a, j = 1; j <= b; j++, i--) {
		res = res * i % p;
		res = res * qmi(j, p - 2, p) % p;
	}
	return res;
}

// 卢卡斯定理
LL lucas(LL a, LL b, LL p) {
	if (a < p && b < p) return C(a, b, p);
	return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

int main() {
	std::ios::sync_with_stdio(false);
	LL n, a, b, p;
	cin >> n;
	while (n--) {
		cin >> a >> b >> p;
		printf("%lld\n", lucas(a, b, p));
	}
	return 0;
}

LL C(LL a, LL b, LL p) {
	if (b > a) return 0;
	if (b > a - b) b = a - b;
	LL x = 1, y = 1;
	for (int i = a, j = 1; j <= b; j++, i--) {
		x = x * i % p;
		y = y * j % p;
	}
	return x * qmi(y, p - 2, p) % p;
}

// 66ms
#include <iostream>
typedef long long LL;
using namespace std;

LL qmi(LL a, LL b, LL p) {
	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, LL p) {
	if (b > a) return 0;
	if (b > a - b) b = a - b; //小优化, 因为 C(a, b) = C(a, a - b)
	LL x = 1, y = 1;
	for (int i = a, j = 1; j <= b; j++, i--) {
		x = x * i % p;
		y = y * j % p;
	}
    // 只在最后求一次乘法逆元
	return x * qmi(y, p - 2, p) % p;
}

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

int main() {
	std::ios::sync_with_stdio(false);
	LL n, a, b, p;
	cin >> n;
	while (n--) {
		cin >> a >> b >> p;
		printf("%lld\n", lucas(a, b, p));
	}
	return 0;
}

// 47ms
#include <iostream>
#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) {
	int c = 0;
	vector<int> res;
	for (int i = 0; i < a.size(); i++) {
		c += a[i] * b;
		res.push_back(c % 10);
		c /= 10;
	}
	while (c) {
		res.push_back(c % 10);
		c /= 10;
	}
	return res;
}

int main() {
    std::ios::sync_with_stdio(false);
	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(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]);
	}
	printf("\n");
	return 0;
	
}

// 53ms
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

void process(int x, unordered_map<int, int>& m, bool add) {
	for (int i = 2; i <= x / i; i++) {
		while (x % i == 0) {
			if (add) m[i]++;
			else m[i]--;
			x /= i;
		}
	}
	if (x > 1) {
		if (add) m[x]++;
		else m[x]--;
	}
}

vector<int> mul(vector<int> a, int b) {
	vector<int> res;
	int c = 0;
	for (int i = 0; i < a.size(); i++) {
		c += a[i] * b;
		res.push_back(c % 10);
		c /= 10;
	}
	while (c) {
		res.push_back(c % 10);
		c /= 10;
	}
	return res;
}

int main() {
	std::ios::sync_with_stdio(false);
	int a, b;
	cin >> a >> b;
	unordered_map<int, int> primes;
	
	for (int i = a, j = 1; j <= b; j++, i--) {
		process(i, primes, true);
		process(j, primes, false);
	}
	
	vector<int> res;
	res.push_back(1);
	
	for (auto& [k, v] : primes) {
		for (int i = 0; i < v; i++) {
			res = mul(res, k);
		}
	} 
	
	for (int i = res.size() - 1; i >= 0; i--) {
		printf("%d", res[i]);
	}
	printf("\n");
	return 0;
}

// 295ms
#include <iostream>
typedef long long LL;
using namespace std;
const int MOD = 1e9 + 7;

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

int main() {
    std::ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int res = 1;
	for (int i = 2 * n, j = 1; j <= n; j++, i--) {
		res = (LL)res * i % MOD;
		res = (LL)res * qmi(j, MOD - 2, MOD) % MOD;
	}
	res = (LL)res * qmi(n + 1, MOD - 2, MOD) % MOD;
	printf("%d\n", res);
	return 0;
}

// 20ms
#include <iostream>
typedef long long LL;
using namespace std;
const int MOD = 1e9 + 7;

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

int main() {
    std::ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int x = 1, y = n + 1;
	for (int i = 2 * n, j = 1; j <= n; j++, i--) {
		x = (LL)x * i % MOD;
		y = (LL)y * j % MOD;
	}
	int res = (LL)x * qmi(y, MOD - 2, MOD) % MOD;
	printf("%d\n", res);
	return 0;
}