数学知识（二）

高斯消元

初等行列变换

1、把某一行乘一个非零的数

2、交换某两行

3、某行若干倍加到另一行上去

目的：通过初等行列变换将增广矩阵变为阶梯型矩阵

操作

1、找到当前列绝对值最大的一行

2、把这一行换到最上面（未确定行的最上面）交换某两行

3、将该行的第一个数变成1 **乘上一个非零数 **

4、将下面所有行的当前列的值变成0 某行若干倍加到另外一行

模板

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
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;//如果最大值是0就跳过

        for (int i = c; i < n + 1; i ++ ) swap(a[t][i],a[r][i]);//换到最上面那一行
        for (int i = n; i >= c; i --) a[r][i] /= a[r][c];//每行第一个数变成1(除上一个数),倒着操作才能保证正确，如果正序，a[r][c]一直是1，对后面没有影响
        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];//（加减一行的整数倍，如此操作可以让该列的数变成0）同理，如果正序更新，a[i][c]会发生变化。
        r++;
    }
    if (r < n) {
        for (int i = r; i < n; i ++) 
            if (fabs(a[i][n] < eps)) return 2;//b[i] = 0,那么有无穷组解
        return 1;//0 == !0 ，无解
    }
    for (int i = n - 1; i >= 0 ; i  --){
        for (int j = i + 1;  j< n; j ++ )
        a[i][n] -= a[j][n]*a[i][j];//减去其他解*系数得到该位置上的解
    }
    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 ans = gauss();
    if (ans == 0) {
        for (int i = 0;  i< n; i ++) printf("%.2lf\n",a[i][n]);
    }else if (ans == 2) puts("Infinite group solutions");
    else puts("No solution");
}

模板(异或线性方程组)

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
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 110;
int n;
int a[N][N];

int gauss(){
    int r ,c;
    for (c = r = 0; c < n;  c ++ ){
        int t = r;
        for (int i = r ; i < n; i ++ ) if (a[i][c]) {
            t = i; break;
        }
        if (!a[t][c]) continue;
        for (int i =c ; i<= n; i ++ ) swap(a[t][i],a[r][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[j][n] * a[i][j];
    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 == 2) puts("Multiple sets of solutions");
    else if (t == 1) puts("No solution") ;
    else for ( int i  = 0 ; i< n ;i ++ ) cout << a[i][n] << endl;
}

组合计数

按照数据范围可分为四种

递推

杨辉三角

例题 ：

https://www.acwing.com/problem/content/887/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

const int N = 2020,mod = 1e9 + 7;
int c[N][N];
int n,a,b;
void init(){
    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 main(){
    cin >> n;
    init();
    while (n--){
        cin >> a >> b;
        cout << c[a][b] << '\n';
    }
}

预处理

例题：

https://www.acwing.com/problem/content/888/

预处理出所有的阶乘，除法使用逆元求解。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7,mod = 1e9 +7;
int n;
int fact[N],infact[N];
int qmi(int a,int b,int p){
    ll res = 1;
    while (b){
        if (b & 1)
        res = res * a % p;
        a = (ll)a * a % p;
        b >>= 1;
    }
    return res;
}

int main(){
    cin >> n;
    fact[0] = infact[0] = 1;
    for (int i =1 ; i < N; i ++ ){
        fact[i] = (ll)fact[i-1]*i%mod;
        infact[i] = (ll)infact[i-1] % mod * qmi(i,mod - 2,mod) % mod;
    }
    while (n --){
        int a,b;
        cin >> a >> b;
        cout <<(ll) fact[a] % mod* infact[a-b]%mod * infact[b] % mod<<endl;
    }
}

例题：

https://www.acwing.com/problem/content/889/

1