湘潭做网站优化,个人建站项目,wordpress分类自定义title,修改wordpress上传图片地址题目#xff1a;
登录—专业IT笔试面试备考平台_牛客网
思路#xff1a;
我们发现对于矩阵C可以一列一列求。
mod2#xff0c;当这一行相乘1的个数为奇数时#xff0c;z(i,j)为1#xff0c;偶数为0#xff0c;是异或消元。
对于b[i#xff0c;j]*c[i,j],b[i,j]可以…题目
登录—专业IT笔试面试备考平台_牛客网
思路
我们发现对于矩阵C可以一列一列求。
mod2当这一行相乘1的个数为奇数时z(i,j)为1偶数为0是异或消元。
对于b[ij]*c[i,j],b[i,j]可以与a[i,i]异或让他转换到左边而右边一列全为0。
每一列的解是不能确定元素cn个的2^cn。
异或消元可以用bitset优化。
代码
#include iostream #includemap #includequeue #includeunordered_map #includecmath #includebitset using namespace std; #define LL long long const int N1e3100; double eps1e-12; const long long mod998244353; std::bitset210 A[210],a[210],b[210]; int n; LL quick(LL a,LL b,LL mod){ LL ans1; while(b){ if(b1) ansans*a%mod; b1; aa*a%mod; } return ans; } LL guss() { int c1,r1; for(c1;cn;c) { int tr; for(int ir1;in;i) if(a[i][c]a[t][c]) ti; if(!a[t][c]) continue; swap(a[t],a[r]); for(int ir1;in;i) if(a[i][c]) a[i]a[i]^a[r]; r; } return quick(2,n-r1,mod); } int main() { cinn; for(int i1;in;i) for(int j1;jn;j) { int x; scanf(%d,x); if(x) A[i][j]1; } for(int i1;in;i) for(int j1;jn;j) { int x; scanf(%d,x); if(x) b[i][j]1; } LL ans1; for(int j1;jn;j) { for(int i1;in;i) for(int k1;kn;k) a[i][k]A[i][k]; for(int i1;in;i) a[i][n1]0; for(int i1;in;i) a[i][i]a[i][i]^b[i][j]; ansans*guss()%mod; } coutansendl; return 0; }
