2020ICPC济南站 A题 Matrix Equation高斯消元求异或方程组

传送门：https://ac.nowcoder.com/acm/contest/10662/A

题意

设$A×C=B⋅C，$求C的个数。

思路

比赛的时候猜答案是2的幂次，确实没错，然后想解法是先求A的逆，最后答案为$C=A^{-1}×B⋅C$，那么就意味着，$A^{-1}×B$这个结果，如果为0，那么可以去0或1，如果是1，那么只能取1，所以答案为$2^{0的个数}$,可是，A可能没有逆，所以这个方法是行不通的。

先来观察式子：

所以每列都是相互独立的，所以我们求每列的种数，最后全部乘起来就好。

由于这个矩阵乘法有一个要求，最后求得的要相加并\%2，这是什么？这不就是异或吗？

那么答案是多少？每一列的种数是多少？答案就是上面每一个异或方程组的自由元的个数n-r，r为方程组的秩。每个值都可以取0或1，即答案为$2^{n-r}$。最后将所有列的种数相乘即可。

Code

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
##include "bits/stdc++.h"

using namespace std;

##define FZT_ACM_LOCAL 1

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

 const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

const int N = 210;
int a[N][N];//增广矩阵
int x[N];//解集
int freeX[N];//自由变元
// equ:方程个数 var:变量个数
int Gauss(int equ, int var) {//返回自由变元个数
    /*初始化*/
    for (int i = 0; i <= var; i++) {
        x[i] = 0;
        freeX[i] = 0;
    }

    /*转换为阶梯阵*/
    int col = 0;//当前处理的列
    int num = 0;//自由变元的序号
    int k;//当前处理的行
    for (k = 0; k < equ && col < var; k++, col++) {//枚举当前处理的行
        int maxr = k;//当前列绝对值最大的行
        for (int i = k + 1; i < equ; i++) {//寻找当前列绝对值最大的行
            if (a[i][col] > a[maxr][col]) {
                maxr = i;
                swap(a[k], a[maxr]);//与第k行交换
                break;
            }
        }
        if (a[k][col] == 0) {//col列第k行以下全是0，处理当前行的下一列
            freeX[num++] = col;//记录自由变元
            k--;
            continue;
        }

        for (int i = k + 1; i < equ; i++) {
            if (a[i][col] != 0) {
                for (int j = col; j < var + 1; j++) {//对于下面出现该列中有1的行，需要把1消掉
                    a[i][j] ^= a[k][j];
                }
            }
        }
    }

    /*求解*/
    //无解：化简的增广阵中存在(0,0,...,a)这样的行，且a!=0
    for (int i = k; i < equ; i++)
        if (a[i][col] != 0)
            return -1;

    //无穷解: 在var*(var+1)的增广阵中出现(0,0,...,0)这样的行
    if (k < var)//返回自由变元数
        return var - k;//自由变元有var-k个

    //唯一解: 在var*(var+1)的增广阵中形成严格的上三角阵
    for (int i = var - 1; i >= 0; i--) {//计算解集
        x[i] = a[i][var];
        for (int j = i + 1; j < var; j++)
            x[i] ^= (a[i][j] && x[j]);
    }
    return 0;
}

ll quick_pow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}
int A[N][N];
int B[N][N];

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> A[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> B[i][j];
        }
    }

    ll ans = 0;

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = A[i][j];
            }
            if (B[i][k]) a[i][i] ^= 1;
        }
        int cnt = Gauss(n, n);
        ans += cnt > 0 ? cnt : 0;
    }

    cout << quick_pow(2, ans) << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/01/27/2020-icpc-jinan-a/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！