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

· · 题解

题意简述

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

解题思路

分类讨论：

  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;
}