MatrixEquation

NC216159. MatrixEquation

描述

We call a matrix "01 Square" if and only if it's a $N\times N$ matrix and its elements are all $0$ or $1$ .

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

$Z_{i,j}=(\sum_{k=1}^{N}X_{i,k}Y_{k,j})~mod~2$

$D_{i,j}=X_{i,j}Y_{i,j}$

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

$A\times C=B\odot 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 

Then there are  lines and each line has  integers, the j-th integer of the i-th line denotes 

Then there are  lines and each line has  integers, the j-th integer of the i-th line denotes 

,

输出描述

Output the answer module .

示例1

输入:

输出:

示例2

输入:

输出:

示例3

输入:

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 37ms, 内存消耗: 600K, 提交时间: 2022-11-04 18:17:08

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)
using namespace std;
const int N=233,P=998244353;
int n,x,ans=1,cnt;
bitset<N> a[N],b[N],c[N],f[N];
void ins(bitset<N> x){
    rep(i,1,n) if(x[i]){
        if(f[i][i]) x^=f[i];
        else{f[i]=x,--cnt;break;}
    }
}
int main(){
    scanf("%d",&n);
    rep(i,1,n) rep(j,1,n) scanf("%d",&x),a[i][j]=x;
    rep(i,1,n) rep(j,1,n) scanf("%d",&x),b[i][j]=x;
    rep(j,1,n){
        rep(i,1,n) c[i]=a[i],c[i][i]=c[i][i]^b[i][j],f[i]=0;cnt=n;
        rep(i,1,n) ins(c[i]);
        rep(i,1,cnt) ans=2ll*ans%P;
    }
    printf("%d\n",ans);
    return 0;
}

上一题

下一题

详情