题解：CF1016D Vasya And The Matrix

思路

首先如果行的所有异或和和列的所有异或和不同，就不存在该矩阵。

然后我们考虑一个无法严谨证明的思路。

就是我们把从

(2,2)

到

(n,m)

的答案矩阵内元素均为

0

，即

ans_{i,j}=0 (i \in [2,n] ,j \in [2,m])

。

这样我们可以单独考虑每一行和每一列，行的异或和就是这一行的首元素，列的异或和就是这一列的首元素。即

ans_{i,1}=a_i(i \in[1,n]),ans_{1,i}=b_i(i \in [1,m])

。

但

(1,1)

点的值覆盖了第

1

行和第

1

列的答案，我们分别去计算一下通过行反推出来的答案和通过列反推出来的答案是否相等。若不相等，说明不存在该矩阵。无法严谨证明的地方就在这里。

这是

\text{AC}

代码。

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=105;
int n,m,a[N],b[N],xor1,xor2,ans[N][N];
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",a+i),xor1^=a[i];
    for(int i=1;i<=m;i++) scanf("%lld",b+i),xor2^=b[i];
    if(xor1!=xor2) return printf("NO"),0;
    for(int i=2;i<=n;i++) ans[i][1]=a[i];
    for(int i=2;i<=m;i++) ans[1][i]=b[i];
    xor1=b[1],xor2=a[1];
    for(int i=2;i<=n;i++) xor1^=a[i];
    for(int i=2;i<=m;i++) xor2^=b[i];
    if(xor1!=xor2) return printf("NO"),0;
    ans[1][1]=xor1;
    printf("YES\n");
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++) printf("%lld ",ans[i][j]);
    	printf("\n");
	}
	return 0;
}

先别走，还有容易证明的方法。

我们将疑惑值逐位拉开，类似于二进制，每一位是

0

或

1

。我们考虑这样的情况，不断找到此时最前的

1

，把行和列里最前面的

1

相配对，即设此时行最前的

1

出现于

i

位置，列最前的

1

出现于

j

位置，则令

ans_{i,j}=1

。

当行和列的

1

个数相同时，就不会有

1

剩下，此时全部匹配完即可。当行和列

1

的个数不同时，我们钦定行中

1

的个数大于列中

1

的个数，则令

len

表示行比列多的数量。我们知道，偶数个

1

疑惑起来是

0

，不会对列中的

0

产生影响。所以当

len

是偶数时，把所有的

1

堆在同一行即可。否则不存在该矩阵。

容易证明。撒花！

题解：CF1016D Vasya And The Matrix

文章操作

思路

相关推荐

评论

题解：CF1016D Vasya And The Matrix