正经题解｜或矩阵

题目大意

当前有一个矩阵$M$，需要判定当前矩阵是否存在可以通过指定方式变换而来。变换的方式是$M_{(i,j)}$是由$a_i$|$a_j$所得。

题目思路

根据题意，如果存在一个序列$a$按照指定方式变换成目标矩阵，那我们可以分析得到如下操作:

$a_i$这个位置只会影响到$M_{(i,j)}$和$M_{(i,j)}$,所以我们将$a_i$转换为二进制，并且假设每一位上都是$1$。

因为$a_i$上最多只能存在格子$M_{(i,j)}$和格子$M_{(i,j)}$二进制下存在的1，所以把两个格子的数值依次跟$a_i$进行&运算即可。最后验证是否可以变成指定矩阵即可。

代码演示

#include<bits/stdc++.h>
using namespace std;
long long mi[100005];
long long mp[1005][1005];
void solve()
{
	int n;
	cin >> n ;
	for(int i = 1 ; i <= n ; i ++ ) mi[i] = (1<<30)-1; 
	for(int i = 1 ; i <= n ; i ++ )
	{
		for(int j = 1 ; j <= n ; j ++ )
		{
			cin >> mp[i][j];
			if(i!=j)
			{
				mi[i] &= mp[i][j];
				mi[j] &= mp[i][j];
			}
		}
	}
	if(n == 1)
	{
		cout << "YES" << endl << "1" << endl;
		return;
	}
	for(int i = 1 ; i <= n ; i ++ )
	{
		for(int j = 1 ; j <= n ; j ++ )
		{
			if(i == j )continue;
			if((mi[i] | mi[j]) != mp[i][j])
			{
				cout << "NO" << endl;
				return ;
			}
		}
	}
	cout << "YES" << endl;
	for(int i = 1 ; i <= n ; i ++ )
	{
		cout << mi[i] << " " ;
	}
	cout << endl;
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}