自己建的网站打不开,有道云笔记做网站,微信小程序页面模板,哈尔滨百度推广电话题意#xff1a;
题目给出两个矩阵X,Y,现在有两种操作 Z X Y D X⊙Y 问是否存在一个矩阵C#xff0c;使得ACB⊙C式子成立#xff0c;问矩阵C能有多少个
题解#xff1a; 这个式子在模2意义下的加法就等于异或 也就相当于 那现在有 将BC移到左边 然后将Ci,j的系数进…题意
题目给出两个矩阵X,Y,现在有两种操作 Z X × Y D X⊙Y 问是否存在一个矩阵C使得A×CB⊙C式子成立问矩阵C能有多少个
题解 这个式子在模2意义下的加法就等于异或 也就相当于 那现在有 将BC移到左边 然后将Ci,j的系数进行合并得到 aik Aik
A i,i B i,j时A i,i xor B i,j 0,ai,i 0 A i,i ! B i,j时ai,i 1 矩阵C是列独立的所以我们每次对Ci,j列出的向量只涉及第j列中未知数Cij 2^自由元总数即为答案个数。
代码
#include bits/stdc.h
using namespace std;
const int N210;
int a[N][N];//增广矩阵
int x[N];//解集
int freeX[N];//自由变元
// equ:方程个数 var:变量个数
int Gauss(int equ,int var){//返回自由变元个数/*初始化*/for(int i0;ivar;i){x[i]0;freeX[i]0;}/*转换为阶梯阵*/int col0;//当前处理的列int num0;//自由变元的序号int k;//当前处理的行for(k0;kequcolvar;k,col){//枚举当前处理的行int maxrk;//当前列绝对值最大的行for(int ik1;iequ;i){//寻找当前列绝对值最大的行if(a[i][col]a[maxr][col]){maxri;swap(a[k],a[maxr]);//与第k行交换break;}}if(a[k][col]0){//col列第k行以下全是0处理当前行的下一列freeX[num]col;//记录自由变元k--;continue;}for(int ik1;iequ;i){if(a[i][col]!0){for(int jcol;jvar1;j){//对于下面出现该列中有1的行需要把1消掉a[i][j]^a[k][j];}}}}/*求解*///无解化简的增广阵中存在(0,0,...,a)这样的行且a!0for(int ik;iequ;i)if(a[i][col]!0)return -1;//无穷解: 在var*(var1)的增广阵中出现(0,0,...,0)这样的行if(kvar)//返回自由变元数return var-k;//自由变元有var-k个//唯一解: 在var*(var1)的增广阵中形成严格的上三角阵for(int ivar-1;i0;i--){//计算解集x[i]a[i][var];for(int ji1;jvar;j)x[i]^(a[i][j]x[j]);}return 0;
}void testf(){for(int i0;i3;i){for(int j0;j3;j){cina[i][j];}}coutGauss(3,3);exit(0);
}int A[N][N];
int B[N][N];
const long long MOD998244353;
int main(){//testf();ios::sync_with_stdio(0);int n;cinn;for(int i0;in;i){for(int j0;jn;j){cinA[i][j];}}for(int i0;in;i){for(int j0;jn;j){cinB[i][j];}}long long ans_cnt0;for(int j0;jn;j){for(int i0;in;i){for(int k0;kn;k){a[i][k]A[i][k];}a[i][n]0;a[i][i](A[i][i]B[i][j]?0:1);}int cntGauss(n,n);if(cnt0){ans_cntcnt;}else if(cnt0){cout0;return 0;}}long long ans1;while(ans_cnt--){ans1;ans%MOD;}coutans;return 0;
}
