专栏文章

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

LLionBlaze
P13776题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio85vgg
此快照首次捕获于
2025/12/02 14:56
3 个月前
此快照最后确认于
2025/12/02 14:56
3 个月前
查看原文
⊕\oplus 表示异或。
先说赛时思路，后面是结论和证明，前面可以跳过。

赛时思路

题目的“连通块”有点抽象，其实就是连通的一块啦，和权值无关。
先分析样例。
第一个样例是一行八列，那么连通块必然是一个子段。所以假设从左往右是 x1,x2,x3,…,x8x_1,x_2,x_3,\dots,x_8，那么有 ⨁i=16xi=⨁i=27xi=⨁i=38xi=0\displaystyle\bigoplus_{i=1}^6 x_i=\bigoplus_{i=2}^7 x_i=\bigoplus_{i=3}^8 x_i=0。
根据异或的性质，我们有 x1⊕x7=x2⊕x8=0x_1\oplus x_7=x_2\oplus x_8=0，也就是 x1=x7,x2=x8x_1=x_7,x_2=x_8。所以根据 x1,x2,x3,x4,x5x_1,x_2,x_3,x_4,x_5 就可以确定 x6x_6，然后 x7=x1,x8=x2x_7=x_1,x_8=x_2 确定所有数字。对于任意 x1…x5x_1\dots x_5 都是合法的，所以答案是 25=322^5=32。
第二个样例是 5×55\times 5，连通块大小为 55。直觉上因为大小为 55 的连通块形状太自由了，所以所有数字都是一样的。证明一下？如果有这样一个形状
PLAINTEXT
a b c
d e f
g h i
选择 a,b,c,e,fa,b,c,e,f 和 b,c,d,e,fb,c,d,e,f 可以知道 a=da=d，相应地 a=d=g,c=f=i,a=b=c,g=h=ia=d=g,c=f=i,a=b=c,g=h=i，所以外圈全部相等。然后选择 a,b,c,d,ea,b,c,d,e 和 a,b,c,d,fa,b,c,d,f 可以知道 e=fe=f，所以所有的都相等。
那么用 3×33\times 3 显然可以证明 5×55\times 5。证毕。
而所有数字都一样，55 又是奇数，奇数个 11 异或还是 11，所以一定是全是 00。所以只有一种可能。
样例 33？114×514114\times 514 一眼看过去就小于 19198101919810，所以相当于没有限制，答案是 2114×5142^{114\times 514}，要对 109+710^9+7 取模。
这些故事样例告诉我们一些道理结论：
  • n×m<kn\times m < k 答案是 2n×m2^{n\times m}；
  • 虽然没说但是考虑一下 n×m=kn\times m=k 答案是 2n×m−12^{n\times m-1}，自证不难；以下讨论都不包含上面的两种情况。
  • n=1n=1 或 m=1m=1 答案是 2k−12^{k-1}。
  • n,m>1n,m>1 答案很可能是 11 或 22，当 kk 是奇数的时候是 11，偶数是 22。
如果最后的结论是正确的那么这题就做完了！赛时想了想挺对的，感觉证明挺麻烦就交上去过了（WA 了一发，因为没开 long long）。但是我们要在这里进行一个证明（赛时没证）。

证明

证明的思路是，证明在某个区域内所有数字都相同。第一个思路是模仿样例 22，考虑 3×t3\times t，实际上这样并不是很行，因为 tt 可能大于 nn。但是其实这样做是有普适性的，所以我们不必使用 33 这个数字，我们可以使用 n×tn\times t，不管先要证明 t≥2t\ge 2，不然不好做。很简单但是直接做会有问题，k=1k=1 证不了全相同，但是可以证明全是 00。
不妨设 n≤mn\le m，首先考虑 k=1k=1。显然全是 00，答案是 11。然后考虑 2≤k≤n2\le k\le n 的情况。显然可以横竖交叉证明 k×kk\times k 全相同，然后显然易证 n×mn\times m 可以。
然后的思路是，填满它。
若 k>nk>n，则我们从上到下，从左到右填 kk 个 X。把其中一个替换为 O，然后在它右边紧贴着的地方填一个 U（因为 k<nmk<nm，所以必然可以填上 U）：
PLAINTEXT
XXXXXXXXX
XXXXXXXXX
XXXXXXXX
XXXOXXXX
XXXXXXXXU
XXXXXXXX
X+O 是连通的，X+U 也是连通的，所以 O=UO=U。只要 O 和 U 不相邻就可以这么干（有一种特殊情况就是相邻也可以这么干但是我们不用管它）。所以选定一个 U 我们就能够证明长方形的所有部分除了和 U 直接相连的那个格子之外都是一样的。又 n≥2n\ge 2，所以至少有 22 个这样的不同的信息，所以所有 X 都相同。
这样我们知道了所有行中数字都是一样的，相应地交换 n,mn,m，可以知道所有列也都是一样的，故所有数字相同，证毕！

代码实现&提交记录

可可爱爱的赛时代码。
CPP
/*
样例 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;
}
可可爱爱的赛时提交记录。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...