Codeforces Round #697 (Div. 3) F. Unusual Matrix (思维,数学）

题意:给你一个矩阵\(a\)和\(b\),你可以对\(a\)的任意一行或任意一列的所有元素xor\(1\)任意次,问最终是否能够得到\(b\).
题解:由\(a\ xor\ b=c\),可得:\(a\ xor \ c=b\),根据线性代数的知识我们只需要判断\(c\)是否能由零矩阵通过上述变换得来即可.因为\(a\ xor\ c\)可以看成\(a\ xor \ 0(进行上述变换得到c)\).也就说明\(a\)可以通过上述变换得到\(b\),而\(c\)的判断,我们只需确定一行或者一列\(0\)后,b变换其他列或行判断即可.
代码:

#include <bits/stdc++.h>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

#define rep(a,b,c) for(int a=b;a<=c;++a)

#define per(a,b,c) for(int a=b;a>=c;--a)

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int _;

char a[1010][1010];

char b[1010][1010];

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>_;

	while(_--){

		int n;

		cin>>n;

		rep(i,1,n){

			rep(j,1,n){

				cin>>a[i][j];

			}

		}

		rep(i,1,n){

			rep(j,1,n){

				cin>>b[i][j];

				a[i][j]^=b[i][j];

			}

		}

		rep(i,1,n){

			if(a[i][1]==1){

				rep(j,1,n) a[i][j]^=1;

			}

		}

		rep(j,1,n){

			if(a[1][j]==1){

				rep(i,1,n) a[i][j]^=1;

			}

		}

		bool flag=true;

		rep(i,1,n){

			rep(j,1,n){

				if(a[i][j]==1){

					flag=false;

					break;

				}

			}

			if(!flag) break;

		}

		if(flag) cout<<"YES\n";

		else cout<<"NO\n";

	}

    return 0;

}

巴特西

Codeforces Round #697 (Div. 3) F. Unusual Matrix (思维,数学）

最新文章

热门文章