组队训练赛（一）

组队训练赛（一）

题目1

题目链接

问题 A: Matrix Equation

题目描述

We call a matrix “01 Square” if and only if it’s a N × N matrix and its elements are all 0 or 1.

For two 01 Squares X,Y , we define two operators X × Y and XY . The value of them are also 01 Square matrices and calculated below(we use Z to abbreviate X × Y and D to abbreviate XY ):

Now MianKing has two 01 Squares A, B, he wants to solve the matrix equation below: A × C = B C

You need to help MainKing solve this problem by calculating how many 01 Squares C satisfy this equation.

The answer may be very large, so you only need to output the answer module 998244353.

输入

The first line has one integer N

Then there are N lines and each line has N integers, the j-th integer of the i-th line denotes $A_{i,j}$

Then there are N lines and each line has N integers, the j-th integer of the i-th line denotes $B_{i,j}$

1≤N≤200, $A_{i,j}$,$ B_{i,j}$∈{ 0, 1 }

输出

Output the answer module 998244353.

样例输入

【样例1】
2
0 1
1 1
1 0
0 1
【样例2】
3
1 0 0
0 1 0
0 0 1
1 1 1
1 1 1
1 1 1
【样例3】
4
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 1
1 0 1 1
0 1 1 1
1 0 0 1
1 1 1 0

样例输出

【样例1】
2
【样例2】
512
【样例3】
8

题解

高斯消元法求解矩阵的秩，对于每一列单独考虑可以将题目转换为以下方程：

对于每一个方程组系数矩阵，如果秩为k，则$C_k,C_{K+1} .... C_n$，可以任意选择0和1，则对应答案为$2^{n-k}$，最后将每一列的答案乘起来即为答案。

参考于：

https://blog.csdn.net/hddddh/article/details/111828336

https://blog.csdn.net/weixin_45697774/article/details/113198407

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
bitset<330> a[330];
int A[330][330] = {0};
int C[330][330] = {0};
ll ksm(ll a, ll b)
{
    ll ans1 = 1, ans2 = a;
    while (b != 0)
    {
        if (b & 1)
            ans1 = (ans1 * ans2) % mod;
        ans2 = (ans2 * ans2) % mod;
        b /= 2;
    }
    return ans1;
}
ll guess(ll n)
{
    ll maxx = 0, row = 0;
    for (ll col = 0; col < n; col++)
    {
        for (maxx = row; maxx < n; maxx++)
            if (a[maxx][col] != 0)
                break;
        if (maxx == n)
            continue;
        if (a[maxx][col] == 0)
            continue;
        swap(a[maxx], a[row]);
        for (ll i = row + 1; i < n; i++)
        {
            if (a[i][col] != 0)
                a[i] ^= a[row];
        }
        row++;
    }
    return ksm(2, n - row);
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &A[i][j]);

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

        for (int j = 0; j < n; j++)
            scanf("%d", &C[i][j]);

    ll ans = 1;
    for (int col = 0; col < n; col++)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                a[i][j] = A[i][j];

        for (int i = 0; i < n; i++)
            a[i][i] = A[i][i] ^ C[i][col];

        ans = (ans * guess(n)) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}