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

哈哈人生 · 2025-08-21 15:05:13 · 题解

题外话

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

思路

首先进行分类讨论。我们发现若 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。

代码

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