高斯消元解线性方程组
#include<bits/stdc++.h>
#define int long long
/*
1.找最大行
2.交换
3.当前行首位变成1
4.用当前行将下面所有的列消成0
*/
using namespace std;
const int N = 2e2 + 10;
const double eps = 1e-9; // 防止精度问题
double a[N][N];
int n;
int gauss() {
int c = 0, r = 0;
for (; 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]); // 将这一行调到最上面
for (int i = n; i >= c; i--) a[r][i] /= a[r][c]; // 要倒着算，否则会影响后面的数
for (int i = r + 1; i < n; i++) { // 第四步
if (fabs(a[i][c]) > eps) { // 如果是0就不用操作了
for (int j = n; j >= c; j--) {
a[i][j] -= a[r][j] * a[i][c];
}
}
}
r++;
}
if (r < n) { //y总口中的非完美三角形
for (int i = r; i < n; i++) {
if (fabs(a[i][n]) > eps) { // 0 != 0
return 2; // 无解
}
}
return 1; // 无穷个解, 0=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];
}
}
return 0;
}
int main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
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 ++ ) {
if (fabs(a[i][n]) < eps) a[i][n] = 0.00; //防止-0.0
cout << a[i][n] << '\n';
}
}
else if (t == 1) puts("Infinite group solutions");
else puts("No solution");
}
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e2 + 10;
int a[N][N], n;
int gauss() {
int c = 0, r = 0;
for (; c < n; c++) {
int t = r;
for (int i = r; i < n; i++)
if (a[i][c])
t = i;
if (!a[t][c]) continue;
for (int i = c; i <= n; i++) swap(a[r][i], a[t][i]);
for (int i = r + 1; i < n; i++)
if (a[i][c])
for (int j = n; j >= c; j--)
a[i][j] ^= a[r][j];
r ++ ;
}
if (r < n) {
for (int i = r; i < n; i++)
if (a[i][n])
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;
}
signed main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j <= n; j++)
cin >> a[i][j];
int t = gauss();
if(t == 0){
for(int i = 0; i < n; i++) cout << a[i][n] << '\n';
}else if(t == 1){
cout << "Multiple sets of solutions\n";
}else{
cout << "No solution\n";
}
return 0;
}
求排列组合
1.递推法预处理求排列组合，复杂度最大为O(N2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 10, mod = 1e9 + 7;
int dp[N][N];
signed main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < N; i++)
for (int j = 0; j <= i; j++){
if(!j) dp[i][j] = 1;
else dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod;
// C(b, a) = C(b, a - 1) + C(b - 1, a - 1)
}
while(n--){
int a, b;
cin >> a >> b;
cout << dp[a][b] << '\n';
}
return 0;
}
2.预处理逆元求组合，复杂度最大为O(nlogn)
#include<bits/stdc++.h>
#define int long long
using namespace std;
/*
C(b,a) = a! / b! / (a - b)!
*/
const int N = 1e5 + 10, mod = 1e9 + 7;
int ksm(int a, int b){//快速幂模版~这里用快速幂求逆元是因为p是素数
int ans = 1;
while(b){
if(b & 1) ans = ans * a % mod;
ans %= mod;
a = a * a % mod;
a %= mod;
b >>= 1;
}
return ans;
}
int fact/*阶乘*/[N], infact/*逆元*/[N], n;
signed main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
fact[0] = infact[0] = 1;
for(int i = 1; i < N; i++){
fact[i] = fact[i - 1] * i % mod; //求阶乘
infact[i] = infact[i - 1] * ksm(i, mod - 2) % mod;
}
while(n--){
int a, b;
cin >> a >> b;
cout << fact[a] * infact[b] % mod * infact[a - b] % mod << '\n';
//除阶乘 -> 乘逆元
}
return 0;
}
3. lucas(卢卡斯)定理求组合数 O(nlog2n)
AcWing 885. 求组合数 III Cabmodp=Camodpbmodp∗Ca/pb/p 但是，p必须为素数
#include<bits/stdc++.h>
#define int long long
/*
lucas(卢卡斯)定理来了，喵~
*/
using namespace std;
int p;
int ksm(int a, int b){
int ans = 1;
while(b){
if(b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int C(int a, int b){
int ans = 1;
for(int i = 1, j = a; i <= b; i++, j--){
ans = ans * j % p;
ans = ans * ksm(i, p - 2) % p;
}
return ans;
}
int lucas(int a, int b){
if(a < p && b < p) return C(a, b);
return C(a % p, b % p) % p * lucas(a / p, b / p);
}
signed main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m >> p;
cout << lucas(n + m, n) % p << '\n';
}
return 0;
}
#include<bits/stdc++.h>
#define int long long
using namespace std;
int p;
int ksm(int a, int b){
int ans = 1;
while(b){
if(b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int C(int a, int b){
int ans = 1;
for(int i = 1, j = a; i <= b; i++, j--){
ans = ans * j % p;
ans = ans * ksm(i, p - 2) % p;
}
return ans;
}
int lucas(int a, int b){
if(a < p && b < p) return C(a, b);
return C(a % p, b % p) % p * lucas(a / p, b / p);
}
signed main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m >> p;
cout << lucas(n + m, n) % p << '\n';
}
return 0;
}
欧拉筛+分解质因数+高精度求非模的组合数
先去筛素数，筛完后去分解质因数，然后用容斥原理∣a∩b∣=∣a∣+∣b∣+∣a∪b∣求出求每个质因数在Cab出现了几次，最后用高精度求出答案ans
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 10;
int prime[N], a, b, num, sum[N];
bool st[N];
void primes() {//线性筛(欧拉筛)
for (int i = 2; i < N; i++) {
if (!st[i])prime[num++] = i;
for(int j = 0; prime[j] * i < N; j++) {
st[prime[j] * i] = true;
if (i % prime[j] == 0)break;
}
}
}
int get(int n, int p) {//求n!的中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 < (int)(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;
}
signed main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a, b;
cin >> a >> b;
primes();
for (int i = 0; i < num; i++) {
int p = prime[i];
sum[i] = get(a, p) - get(a - b, p) - get(b, p);
//容斥原理求贡献
}
vector<int> ans;
ans.push_back(1);
for (int i = 0; i < num; i++)//算答案
for (int j = 0; j < sum[i]; j++)
ans = mul(ans, prime[i]);
for (int i = ans.size() - 1; i >= 0; i --)
cout << ans[i] ;
cout << '\n';
return 0;
}
卡特兰数
Catalan(n)=C2∗nn/(n+1)
#include<bits/stdc++.h>
#define int long long
using namespace std;
/*
卡特兰数：
C(n * 2, n) / (n + 1)
*/
const int mod = 1e9 + 7;
int ksm(int a, int b){
int ans = 1;
while(b){
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
signed main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int a = 2 * n, b = n, ans = 1;
for(int i = a; i > a - b; i--) ans = ans * i % mod;
for(int i = 1; i <= b; i++) ans = ans * ksm(i, mod - 2) % mod;
ans = ans * ksm(n + 1, mod - 2) % mod;/*除n + 1等于乘上他的逆元*/
cout << ans << '\n';
return 0;
}