题外话

好久没被一道黄题诈骗了。

思路

首先进行分类讨论。我们发现若

n\times m<k

时可以随便填，因为根本没有

k

连通块。由于每个位置可以填

1

或

0

，答案为

2^{n\times m}

。

我们继续讨论，发现当

n=1

或

m=1

或

n\times m=k

时，答案为

2^{k-1}

。因为若

n=1

或

m=1

，矩阵相当于一个序列，我们可以依次选长度为

k

的区间，由于异或值都为

0

，此时第

i

个位置和第

i+k

个位置的值必须相等。我们只需要保证前

k

个位置有偶数个

1

即可。这是个经典的组合数问题，答案为

2^{k-1}

。

n\times m=k

同理。

我们注意力惊人，发现当

n\times m>k

时矩阵的数必须全相等，举个例子：

对于图中

1,2,3

种选法，由于每回只有两个位置选与不选发生了改变，其它位置状态不变，而每回选完后

1

的个数都是偶数，所以可以推出最后一列后三个数相等。同理可得，整个矩阵的数都相等。

此时，若

k

为偶数，那么矩阵可以全填

1

或

0

，答案为

2

。若为奇数，那么只能全填

0

了，答案为

1

。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int t,n,m,k;
int qpow(int a,int b) {
	int ret=1;
	while(b) {
		if(b&1)ret*=a,ret%=mod;
		a*=a,a%=mod,b>>=1;
	}
	return ret;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--) {
		cin>>n>>m>>k;
		if(n*m<k) {
			cout<<qpow(2,n*m)<<"\n";
		} else if(n==1||m==1||n*m==k) {
            cout<<qpow(2,k-1)<<"\n";
		} else {
			if(k%2==0)cout<<2<<"\n";
			else cout<<1<<"\n";
		}
	}
	return 0;
}

题解：P13776 「o.OI R2」Easy ver.

文章操作

题外话

思路

代码

相关推荐

评论

题解：P13776 「o.OI R2」Easy ver.