Matrix Equation(高斯线性异或消元+bitset优化)

题目：

登录—专业IT笔试面试备考平台_牛客网

思路：

我们发现对于矩阵C可以一列一列求。

mod2，当这一行相乘1的个数为奇数时，z(i,j)为1，偶数为0，是异或消元。

对于b[i，j]*c[i,j],b[i,j]可以与a[i,i]异或让他转换到左边，而右边一列全为0。

每一列的解是不能确定元素cn个的2^cn。

异或消元可以用bitset优化。

代码：

#include <iostream>
#include<map>
#include<queue>
#include<unordered_map>
#include<cmath>
#include<bitset>
using namespace std;
#define LL long long
const int N=1e3+100;
double eps=1e-12;
const long long mod=998244353;
std::bitset<210> A[210],a[210],b[210];
int n;
LL quick(LL a,LL b,LL mod){
   LL ans=1;
   while(b){
    if(b&1) ans=ans*a%mod;
    b>>=1;
    a=a*a%mod;
   }
   return ans;
}
LL guss()
{   int c=1,r=1;
   for(c=1;c<=n;c++)
   {  int t=r;
    for(int i=r+1;i<=n;i++) if(a[i][c]>a[t][c]) t=i;
     if(!a[t][c]) continue;
    swap(a[t],a[r]);
    for(int i=r+1;i<=n;i++)
        if(a[i][c])
        a[i]=a[i]^a[r];
      r++;
   }
   return quick(2,n-r+1,mod);
}
int main()
{  cin>>n;
  for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
  {  int x;
      scanf("%d",&x);
      if(x) A[i][j]=1;
  }
  for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
  {  int x;
      scanf("%d",&x);
      if(x) b[i][j]=1;
  }
   LL ans=1;
   for(int j=1;j<=n;j++)
   {
     for(int i=1;i<=n;i++)
     for(int k=1;k<=n;k++)
     a[i][k]=A[i][k];
     for(int i=1;i<=n;i++) a[i][n+1]=0;
     for(int i=1;i<=n;i++)
     a[i][i]=a[i][i]^b[i][j];
     ans=ans*guss()%mod;
   }
   cout<<ans<<endl;
    return 0;
}