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

原题链接

• 洛谷 P13776 「o.OI R2」Easy ver.

题意简述

求满足以下条件的 $n$ 行 $m$ 列的 $01$ 矩阵 $a$ 的个数：对于任意大小为 $k$ 的四连通块，其内所有元素的异或和为 $0$。

解题思路

分类讨论：

1. $nm<k$：不存在大小为 $k$ 的连通块，条件对所有矩阵真空成立。因此答案为 $s=2^{nm}$。
2. $nm=k$：唯一的大小为 $k$ 的连通块就是整个矩阵，恰好有一半的矩阵异或和为 $0$。因此答案为 $\frac{2^{nm}}{2}=2^{nm-1}$。
3. $n=1\lor m=1$：前两个条件已保证 $k<\max(n,m)$。对于一维序列，任意两个长度为 $k$ 的相邻子段，异或的差只在端点 $x_i$ 和 $x_{i+k}$ 上。若两段异或都为 $0$，则必有 $x_i=x_{i+k}$，即序列以周期 $k$ 重复。又因为前 $k$ 位中 $1$ 的个数需为偶数，所以前 $k$ 位有 $k-1$ 个自由位，最后一位被“补成偶数”。因此答案为 $2^{k-1}$。
4. 否则，类似一维情况，取两块仅相差一个格子的连通块，可推出这两个格子值相等，从而整个矩阵必须同值。若 $k$ 为奇数，只能全为 $0$，答案为 $1$；若 $k$ 为偶数，可以全为 $0$ 或 $1$，答案为 $2$。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int mod=1000000007;
ll Pow(ll x,ll y)
{
	x%=mod;
	ll res=1;
	while(y)
	{
		if(y&1)res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		ll n,m,k;
		cin>>n>>m>>k;
		if(n*m<k)cout<<Pow(2,n*m)<<'\n';
		else if(n*m==k)cout<<Pow(2,n*m-1)<<'\n';
		else if(n==1||m==1)cout<<Pow(2,k-1)<<'\n';
		else cout<<(k&1?1:2)<<'\n';
	}
	return 0;
}