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

· · 题解

先说赛时思路，后面是结论和证明，前面可以跳过。

赛时思路

题目的“连通块”有点抽象，其实就是连通的一块啦，和权值无关。

先分析样例。

第一个样例是一行八列，那么连通块必然是一个子段。所以假设从左往右是 x_1,x_2,x_3,\dots,x_8，那么有 \displaystyle\bigoplus_{i=1}^6 x_i=\bigoplus_{i=2}^7 x_i=\bigoplus_{i=3}^8 x_i=0。

根据异或的性质，我们有 x_1\oplus x_7=x_2\oplus x_8=0，也就是 x_1=x_7,x_2=x_8。所以根据 x_1,x_2,x_3,x_4,x_5 就可以确定 x_6，然后 x_7=x_1,x_8=x_2 确定所有数字。对于任意 x_1\dots x_5 都是合法的，所以答案是 2^5=32。

第二个样例是 5\times 5，连通块大小为 5。直觉上因为大小为 5 的连通块形状太自由了，所以所有数字都是一样的。证明一下？如果有这样一个形状

a b c
d e f
g h i

选择 a,b,c,e,f 和 b,c,d,e,f 可以知道 a=d，相应地 a=d=g,c=f=i,a=b=c,g=h=i，所以外圈全部相等。然后选择 a,b,c,d,e 和 a,b,c,d,f 可以知道 e=f，所以所有的都相等。

那么用 3\times 3 显然可以证明 5\times 5。证毕。

而所有数字都一样，5 又是奇数，奇数个 1 异或还是 1，所以一定是全是 0。所以只有一种可能。

样例 3？114\times 514 一眼看过去就小于 1919810，所以相当于没有限制，答案是 2^{114\times 514}，要对 10^9+7 取模。

这些故事样例告诉我们一些道理结论：

如果最后的结论是正确的那么这题就做完了！赛时想了想挺对的，感觉证明挺麻烦就交上去过了（WA 了一发，因为没开 long long）。但是我们要在这里进行一个证明（赛时没证）。

证明

证明的思路是，证明在某个区域内所有数字都相同。第一个思路是模仿样例 2，考虑 3\times t，实际上这样并不是很行，因为 t 可能大于 n。但是其实这样做是有普适性的，所以我们不必使用 3 这个数字，我们可以使用 n\times t，不管先要证明 t\ge 2，不然不好做。很简单但是直接做会有问题，k=1 证不了全相同，但是可以证明全是 0。

不妨设 n\le m，首先考虑 k=1。显然全是 0，答案是 1。然后考虑 2\le k\le n 的情况。显然可以横竖交叉证明 k\times k 全相同，然后显然易证 n\times m 可以。

然后的思路是，填满它。

若 k>n，则我们从上到下，从左到右填 k 个 X。把其中一个替换为 O，然后在它右边紧贴着的地方填一个 U（因为 k<nm，所以必然可以填上 U）：

XXXXXXXXX
XXXXXXXXX
XXXXXXXX
XXXOXXXX
XXXXXXXXU
XXXXXXXX

X+O 是连通的，X+U 也是连通的，所以 O=U。只要 O 和 U 不相邻就可以这么干（有一种特殊情况就是相邻也可以这么干但是我们不用管它）。所以选定一个 U 我们就能够证明长方形的所有部分除了和 U 直接相连的那个格子之外都是一样的。又 n\ge 2，所以至少有 2 个这样的不同的信息，所以所有 X 都相同。

这样我们知道了所有行中数字都是一样的，相应地交换 n,m，可以知道所有列也都是一样的，故所有数字相同，证毕！

代码实现&提交记录

可可爱爱的赛时代码。

/*
样例 1：
????????
k=6
那么
123456
 234567
  345678

xor=0
也就是说
1=7
2=8
那么自由度为 6
然而给定了 12345 就能推断出 6,7,8
所以自由度为 5
输出 32
样例 2：
?????
?????
?????
?????
?????
k=5
可以推断出所有数字均相同
而 k 为奇数
所以是 1
样例 3：
看起来很唬人，实际上 114*514<1919810
所以是 2^(114*514) mod 1e9+7

那么？

不妨假设 nm>=k，n<=m

若 nm=k：答案为 2^(nm-1)

若 n=1：长条形，这样答案是容易计算的，容易发现 1&k+1,2&k+2,... 是相同的，然后 k 也不是自由的，所以答案为 2^(k-1)。

若 n>1：应该是可以推出所有数字相同的，那么 k 为奇数的时候是 1，偶数是 2
嗯我猜结论是对的。
*/
/*
好吧，炸了，6。
不过 subtask 0,1,2 是对的
3,4 不对
说明 n=1 讨论是对的
nm=k 草忘了写了
还有没开 long long
wssb
*/
#include <cstdio>
#include <algorithm>

using namespace std;

long long qpow(long long x, long long y)
{
    if(y == 0) return 1;
    if(y == 1) return x % 1000000007;
    long long res = qpow(x, y >> 1);
    res = res * res % 1000000007;
    if(y & 1) res = res * x % 1000000007;
    return res;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        if(n > m) swap(n, m);
        if(1ll*n*m < k) printf("%lld\n", qpow(2, 1ll*n*m));
        else if(1ll*n*m == k) printf("%lld\n", qpow(2, 1ll*n*m-1));
        else if(n == 1) printf("%lld\n", qpow(2, k-1));
        else printf("%lld\n", (k & 1) ? 1 : 2);
    }
    return 0;
}

可可爱爱的赛时提交记录。