数据结构与算法-数学-容斥原理，高斯消元解线性方程组

容斥原理

容斥原理用于计算多个集合的并集元素个数，公式为 ∣A1∪A2∪⋯∪An∣=∑i=1n∣Ai∣−∑1≤i<j≤n∣Ai∩Aj∣+∑1≤i<j<k≤n∣Ai∩Aj∩Ak∣−⋯+(−1)n−1∣A1∩A2∩⋯∩An∣

举一个例题：
给定一个整数 nn 和 mm 个不同的质数 p1,p2,…,pm。

请你求出1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

1~n中能被pi整除的数的个数记作numi

ans=num1+num2.....+numm -(num(12)+num(13).....+num(1m)....num (m-1m) )+.....

简单的看1~n中可以被2整除的数 n/2个，能被2,3同时整除的数的个数n/6.

这样看是不是就很简单了

m*2^m:枚举1~m,表示几个数，然后再去1~m中选择这些数的组合

代码;

#include <bits/stdc++.h>

using namespace std;

const long long N=20;

long long a[N];

long long n,m;

long long p;

long long res=0;

void dfs(long long len,long long cur,long long mul,long long limit){

    if(mul>n)return;

    if(len==limit){

        res+=p*(n/mul);

        return;

    }

    if(cur>m)return;

    dfs(len+1,cur+1,mul*a[cur],limit);

    dfs(len,cur+1,mul,limit);

}

signed main(){

    scanf("%lld%lld",&n,&m);

    p=-1;

    for(long long i=1;i<=m;i++)scanf("%lld",&a[i]);

    for(long long i=1;i<=m;i++){

        p=(-p);

        dfs(0,1,1,i);

    }

    cout<<res;

}

高斯消元

高斯消元解线性方程组

原理：通过一系列的初等行变换将线性方程组的增广矩阵化为行阶梯形矩阵或行最简形矩阵，从而求解方程组。初等行变换包括交换两行、某一行乘以非零常数、某一行加上另一行的倍数。

简述一下高斯消元求解线性方程组的思路：

第一步：找到每一列的绝对值最大的数的行号
在当前处理的列中，遍历该列中所有尚未处理的行，找出绝对值最大的那个数所在的行号。这一步的目的是为了在进行消元操作时，选择一个相对较大的主元（即当前列的首非零元素），这样可以减少计算过程中的误差积累，提高计算的稳定性。

第二步：将这行交换到最上面一行
将找到的绝对值最大的那一行与当前处理的最上面一行进行交换。通过交换行的操作，将主元放到一个更便于进行后续计算的位置，即当前处理部分的第一行。

第三步：把第一行的最前面的非 0 的数变为 1（整体除以这个数）
用第一行的每个元素除以主元（即最前面的非零数），使得主元变为 1。这样做是为了后续能够方便地对其他行进行消元操作，将其他行中对应列的元素消为 0。

第四步：将下面的所有行中该列非 0 的行全部消去成为 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 + 1; 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)

                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[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 == 0)

    {

        for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]);

    }

    else  puts("No Solution");

    return 0;

}

高斯消元解异或线性方程组

原理：与普通高斯消元类似，但运算规则基于异或运算。异或运算满足交换律、结合律，且a⊕a=0，a⊕0=a。

算法设计思路：同样是通过初等行变换将异或线性方程组的系数矩阵化为行最简形矩阵。在进行行变换时，使用异或运算来消除某一列的非零元素。最后根据化简后的矩阵求解未知数，由于异或运算的特殊性，求解过程相对简单直接，可直接根据矩阵中的1来确定未知数的值。

first: 从第一列开始，遍历该列中所有尚未处理的行，找到第一个该列元素为 1 的行号。这是因为在异或运算中，1 可以作为有效的 “主元” 来进行后续的消元操作，而异或运算的特点也决定了我们需要寻找值为 1 的元素来开启消元过程。

second: 将找到的这一行交换到最上面一行。这样做的目的是把当前列中值为 1 的行放到一个便于对下面行进行消元操作的位置，就如同普通高斯消元中交换主元所在行的作用一样。

third: 对于下面的所有行，如果某行在该列的元素为 1，就将这行与最上面一行进行异或操作。由于异或运算的特性（相同为 0，不同为 1），当这两行进行异或时，该列的元素就会变为 0，同时其他列的元素也会根据异或规则相应改变，从而达到消去该列非零元素的目的。

fourth: 完成对当前列的消元后，看下一列，回到 first。不断重复上述的 first 到 third 步骤，对每一列进行处理，直到所有列都处理完毕。通过这样的操作，原异或线性方程组的系数矩阵会逐渐被化为一个上三角形式（类似倒置梯形），但这里是基于异或运算的特殊形式。

消去完成后，得到一个上三角形式的方程组。此时，从最后一行开始，因为最后一行只有一个未知数（其系数为 1），可以直接根据该行等式右边的值确定该未知数的值。然后将这个已求出的未知数的值代入上一行方程，由于上一行方程中除了已求解的未知数外，其他未知数的系数在消元过程中也有相应的形式，再结合异或运算的规则，就可以求解出上一行的未知数。以此类推，依次从下向上求解每个未知数，最终得到整个异或线性方程组的解。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

const int N = 210;

int n;

int a[N][N];

void print(){

    for(int i=0;i<n;i++){

        for(int j=0;j<=n;j++)cout<<a[i][j]<<' ';

        cout<<endl;

    }

}

int g(){

    int r,c;

    for(c=0,r=0;c<n;c++){

        int t=n;

        for(int i=r;i<n;i++){

            if(a[i][c]){

                t=i;

                break;

            }

        }

        if(t>=n)continue;

        if(t!=r)

        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=c;j<=n;j++){

                    int w=a[i][j]^a[r][j];

                    a[i][j]=w;//为什么把w赋值给a[i][j]就会超时

                }

            }

        }

        r++;

    }

    if(r<n){//不止有一组解

        for(int i=r;i<n;i++)if(a[i][n])return 2;//无解

        return 1;//有解

    }

    for(int i=n-2;i>=0;i--){

        for(int j=n-1;j>i;j--)

            if(a[i][j])

                a[i][n]=a[i][n]^a[j][n];

    }

    return 0;//唯一解

}

void read(){

    

    scanf("%d",&n);

    for(int i=0;i<n;i++)

        for(int j=0;j<=n;j++)

            scanf("%d",&a[i][j]);   

}

int main(){

    read();

    int t=g();

    if(t==2){

        cout<<"No solution";

    }else if(t==1){

        cout<<"Multiple sets of solutions";

    }else for(int i=0;i<n;i++)cout<<a[i][n]<<endl;

}

容斥原理

容斥原理用于计算多个集合的并集元素个数，公式为 ∣A1∪A2∪⋯∪An∣=∑i=1n∣Ai∣−∑1≤i<j≤n∣Ai∩Aj∣+∑1≤i<j<k≤n∣Ai∩Aj∩Ak∣−⋯+(−1)n−1∣A1∩A2∩⋯∩An∣

举一个例题：
给定一个整数 nn 和 mm 个不同的质数 p1,p2,…,pm。

请你求出1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

1~n中能被pi整除的数的个数记作numi

ans=num1+num2.....+numm -(num(12)+num(13).....+num(1m)....num (m-1m) )+.....

简单的看1~n中可以被2整除的数 n/2个，能被2,3同时整除的数的个数n/6.

这样看是不是就很简单了

m*2^m:枚举1~m,表示几个数，然后再去1~m中选择这些数的组合

代码;

#include <bits/stdc++.h>

using namespace std;

const long long N=20;

long long a[N];

long long n,m;

long long p;

long long res=0;

void dfs(long long len,long long cur,long long mul,long long limit){

    if(mul>n)return;

    if(len==limit){

        res+=p*(n/mul);

        return;

    }

    if(cur>m)return;

    dfs(len+1,cur+1,mul*a[cur],limit);

    dfs(len,cur+1,mul,limit);

}

signed main(){

    scanf("%lld%lld",&n,&m);

    p=-1;

    for(long long i=1;i<=m;i++)scanf("%lld",&a[i]);

    for(long long i=1;i<=m;i++){

        p=(-p);

        dfs(0,1,1,i);

    }

    cout<<res;

}

高斯消元

高斯消元解线性方程组

原理：通过一系列的初等行变换将线性方程组的增广矩阵化为行阶梯形矩阵或行最简形矩阵，从而求解方程组。初等行变换包括交换两行、某一行乘以非零常数、某一行加上另一行的倍数。

简述一下高斯消元求解线性方程组的思路：

第一步：找到每一列的绝对值最大的数的行号
在当前处理的列中，遍历该列中所有尚未处理的行，找出绝对值最大的那个数所在的行号。这一步的目的是为了在进行消元操作时，选择一个相对较大的主元（即当前列的首非零元素），这样可以减少计算过程中的误差积累，提高计算的稳定性。

第二步：将这行交换到最上面一行
将找到的绝对值最大的那一行与当前处理的最上面一行进行交换。通过交换行的操作，将主元放到一个更便于进行后续计算的位置，即当前处理部分的第一行。

第三步：把第一行的最前面的非 0 的数变为 1（整体除以这个数）
用第一行的每个元素除以主元（即最前面的非零数），使得主元变为 1。这样做是为了后续能够方便地对其他行进行消元操作，将其他行中对应列的元素消为 0。

第四步：将下面的所有行中该列非 0 的行全部消去成为 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 + 1; 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)

                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[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 == 0)

    {

        for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]);

    }

    else  puts("No Solution");

    return 0;

}

高斯消元解异或线性方程组

原理：与普通高斯消元类似，但运算规则基于异或运算。异或运算满足交换律、结合律，且a⊕a=0，a⊕0=a。

算法设计思路：同样是通过初等行变换将异或线性方程组的系数矩阵化为行最简形矩阵。在进行行变换时，使用异或运算来消除某一列的非零元素。最后根据化简后的矩阵求解未知数，由于异或运算的特殊性，求解过程相对简单直接，可直接根据矩阵中的1来确定未知数的值。

first: 从第一列开始，遍历该列中所有尚未处理的行，找到第一个该列元素为 1 的行号。这是因为在异或运算中，1 可以作为有效的 “主元” 来进行后续的消元操作，而异或运算的特点也决定了我们需要寻找值为 1 的元素来开启消元过程。

second: 将找到的这一行交换到最上面一行。这样做的目的是把当前列中值为 1 的行放到一个便于对下面行进行消元操作的位置，就如同普通高斯消元中交换主元所在行的作用一样。

third: 对于下面的所有行，如果某行在该列的元素为 1，就将这行与最上面一行进行异或操作。由于异或运算的特性（相同为 0，不同为 1），当这两行进行异或时，该列的元素就会变为 0，同时其他列的元素也会根据异或规则相应改变，从而达到消去该列非零元素的目的。

fourth: 完成对当前列的消元后，看下一列，回到 first。不断重复上述的 first 到 third 步骤，对每一列进行处理，直到所有列都处理完毕。通过这样的操作，原异或线性方程组的系数矩阵会逐渐被化为一个上三角形式（类似倒置梯形），但这里是基于异或运算的特殊形式。

消去完成后，得到一个上三角形式的方程组。此时，从最后一行开始，因为最后一行只有一个未知数（其系数为 1），可以直接根据该行等式右边的值确定该未知数的值。然后将这个已求出的未知数的值代入上一行方程，由于上一行方程中除了已求解的未知数外，其他未知数的系数在消元过程中也有相应的形式，再结合异或运算的规则，就可以求解出上一行的未知数。以此类推，依次从下向上求解每个未知数，最终得到整个异或线性方程组的解。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

const int N = 210;

int n;

int a[N][N];

void print(){

    for(int i=0;i<n;i++){

        for(int j=0;j<=n;j++)cout<<a[i][j]<<' ';

        cout<<endl;

    }

}

int g(){

    int r,c;

    for(c=0,r=0;c<n;c++){

        int t=n;

        for(int i=r;i<n;i++){

            if(a[i][c]){

                t=i;

                break;

            }

        }

        if(t>=n)continue;

        if(t!=r)

        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=c;j<=n;j++){

                    int w=a[i][j]^a[r][j];

                    a[i][j]=w;//为什么把w赋值给a[i][j]就会超时

                }

            }

        }

        r++;

    }

    if(r<n){//不止有一组解

        for(int i=r;i<n;i++)if(a[i][n])return 2;//无解

        return 1;//有解

    }

    for(int i=n-2;i>=0;i--){

        for(int j=n-1;j>i;j--)

            if(a[i][j])

                a[i][n]=a[i][n]^a[j][n];

    }

    return 0;//唯一解

}

void read(){

    

    scanf("%d",&n);

    for(int i=0;i<n;i++)

        for(int j=0;j<=n;j++)

            scanf("%d",&a[i][j]);   

}

int main(){

    read();

    int t=g();

    if(t==2){

        cout<<"No solution";

    }else if(t==1){

        cout<<"Multiple sets of solutions";

    }else for(int i=0;i<n;i++)cout<<a[i][n]<<endl;

}