【题解】[APIO2011] 方格染色 并查集+数学 LUOGU – 3631

这里是可爱的传送门酱~：[APIO2011] 方格染色

题意：

给一个 $n \times m$的表格图，你可以给它的每一个格子涂红色或者蓝色，且每一个 $2 \times 2$的子表格图内必须有奇数个红色格子，现在有人已经涂了一部分格子了，求你完成这个表格图的方案数。

这道题好可怕呀刚开始想的时候只会去想写点状压 dp 啥的，推完第一行之后发现后面被两个状态所控制（我太菜了所以现在才发现），接着就很容易证得只要确定整个表格的第一行和第一列就能确定整个表格（简单证明一下：一个完成的表格肯定有一个确定的第一行和第一列，一个确定的第一行第一列根据递推关系肯定能确定唯一一个表格，这两者互相一一映射）且第一行和第一列无论填什么都不会互相冲突，因此对于一个空的表格我们有 $2^{n + m – 1}$种填充方案。

然后蒟蒻的我就不会做了 QAQ。

后来我跑到了 luogu 题解里看到了 litble dalao 的蜜汁数学构造法（QwQ 太神奇了）。然后我就顺便发现了这个站 QAQ

首先我们先要考虑如何将表格里任意一个填好的点的影响映射到第一行和第一列中去，当这个填好的点在第一行或者第一列的时候当然是十分显然的（就只是控制了这个点），而当这个点不在第一行或第一列的时候，我们就要考虑将当前点与第一行第一列的点关联起来，对于一个点 $(x, y) \quad{\forall} x,y>1$，我们可以把由两个点 $[(1,1), (x,y)]$所围成的子表格图内的所有 $2 \times 2$的子表格图全部异或起来（也就是 $(x-1)\times(y-1)$个 $2 \times 2$的子表格图）由题意可知，一个合法的终态的任意一个 $2 \times 2$的子表格图的异或和 $=1$, 因此我们很容易得到上面那个操作的异或结果是 $(x-1) \& (y-1) \& 1$(即如果 $(x-1)$和 $(y-1)$都是奇数的话结果是 $1$，否则结果为 $0$)。

而且容易知道，在我们做完这些异或操作后，子表格图 $[(1,1), (x,y)]$内除了四个端点其它点都被异或了偶数次（即相当于没有进行异或）因此现在所得到的异或结果的意义就是这个子表格图的四个端点所应该得到的异或和。

好像不太直观哎。。。

那我就画个图吧（然后我发现权限不够）

哼我会表格操作 QwQ

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

（其中编号 $1,2,3,4,5,6,11,16,21$为第一行和第一列（废话））

为了方便起见我们把红色格子记为 $1$，蓝色格子记为 $0$
当你在 $19$的位置放了一个 $1$的时候，假设 $1$位置（也就是坐标 $(1,1)$处）已经有了一个 $0$，根据我们刚才的推导，由于子表格图 $[(1,1),(4,4)]$中有 $9$个 $2\times 2$的子表格图，因此当这个表格图合法的时候，这个表格的四个端点 (也就是位置 $1,4,16,19$) 的异或和必须是 $1$，否则就不可能是一个合法的方案。因为 $1$位置是 $0$，$2$位置是 $1$，因此位置 $4$和位置 $16$的异或值应该是 $0$。

话句话说，在整个表格的非首行首列涂颜色，相当于是间接地限制了两个属于首行首列的点之间的关系（同 or 异）

因此我们只需要用权值并查集来维护一下这些信息即可啦。

tip: 不会权值并查集的人可以来看看这篇文章哦（强行安利自己的文章）：带权并查集

对于同一个集合的点，如果没有限制，则有 $2$种选择方法，如果已经有一个点被限制了，就只有 $1$种选择方法，然后根据乘法原理把每个集合的贡献都乘起来就行啦~

时间复杂度 $\Theta(\alpha(n+m))$

实现方法：

说明：我的代码对点的编号方法：第一行依次是 $(1 \sim n)$号，第一列从 $2$开始依次是 $(n+2 \sim n+m)$号，因此代码中先将 $ans$赋值成 $-1$既可以判断这种方案是不是可行的（不可行 $ans$就是 $-1$），又可以在该方案可行的时候排除掉编号 $(n+1)$所构成的集合造成的对答案的影响。

数组 $f[i]$表示 $i$节点的祖先（根节点）

数组 $d[i]$表示 $i$节点离根节点的距离（在这里就是异或关系，相同或者相异）

数组 $g[i]$表示这个点被限定为哪种颜色（未被限定则为 $-1$）

其实我的思路是比较清奇的，首先枚举点 $(1,1)$的情况，然后将属于首行首列的点先挑出来，把它们的 $g[i]$全部先赋值为它们应该变成的值。由于仅填首行首列的点的时候是不会产生冲突的，所以我们这个时候不需要对当前状态进行判断。

接着我枚举不是首行首列的点，用权值并查集维护首行首列点的异或关系并进行判断，合并集合的时候将已经有限制的点作为根节点，这样方便进行以后的判断，而且也保证了以后不可能会再次出现新的有限制的节点（因为首行首列的点已经在上一步维护完了呀）

虽然这样做会多一个 $\Theta(klogk)$的复杂度，但同时也使代码表达更加清楚啦，反正时间妥妥够那就这样做喽。

因此我的代码的时间复杂度是：$\Theta(\alpha(n+m)+klogk)$

代码：

#include<bits/stdc++.h>
#define N 100005
#define ll long long
#define mod 1000000000
#define R register
#define fo(i, a, b) for (R ll i = (a); i <= (b); ++i)
ll n, m, k, ans[2], cnt, tmp, f[N << 1], d[N << 1], g[N << 1], x, y, now, fx, fy, dis, final;
bool flag;
struct node{
    ll x, y, c, pri;
}t[N];
inline bool cmp (node x, node y)
{
    return x.pri > y.pri;
}
inline ll idx (ll x, ll y)
{
    if (y == 1)
        return x;
    else
        return n + y;
}
inline ll find (ll x) 
{
    if (x == f[x]) return x; 
    ll t = f[x];
    f[x] = find(f[x]);
    d[x] = d[x] ^ d[t];
    return f[x];
}
inline ll pow (ll x)
{
    ll sum = 1, p = 2;
    while (x)
    {
        if (x & 1) sum = sum * p % mod;
        p = p * p % mod;
        x = x >> 1;
    }
    return sum;
}
int main()
{
    scanf("%lld %lld %lld", &n, &m, &k);
    tmp = -1;//tmp 为 (1,1) 不能选的点 
    fo (i, 1, k)
    {
        scanf("%lld %lld %lld", &t[i].x, &t[i].y, &t[i].c);
        if (t[i].x == 1 || t[i].y == 1)
        {
            t[i].pri = 1;//pri = priority  坐标有 1 的优先操作 
            cnt++;
            if (t[i].x == 1 && t[i].y == 1)
                tmp = !t[i].c;
        }
    }
    std::sort(t + 1, t + k + 1, cmp);//按优先级排序
    //这里排完序之后，[1, cnt] 为坐标里有 1 的，[cnt + 1, k] 为坐标里没 1 的 
//  fo (i, 1, k)
//      printf("%lld %lld %lld\n", t[i].x, t[i].y, t[i].c);
    ans[0] = ans[1] = -1;
    fo (l, 0, 1)
        if (tmp != l)  
        {
            flag = 1;
            memset(g, -1, sizeof(g));
            fo (i, 1, n + m) f[i] = i;
            memset(d, 0, sizeof(d));
            fo (i, 1, cnt)//处理坐标里有 1 的
            {
                now = idx(t[i].x, t[i].y);
                g[now] = t[i].c; //直接赋值成当前值 
            }
            fo (i, cnt + 1, k)//处理坐标里没 1 的 
            {
                x = t[i].x; //坐标 (x, 1) 
                y = idx(1, t[i].y); //坐标 (1, y)
                now = l ^ t[i].c ^ ((t[i].x - 1) & (t[i].y - 1) & 1);
                //(x, 1) 与 (1, y) 的关系，同为 0，异为 1
                fx = find(x);
                fy = find(y);
                if (g[fx] != -1) std::swap(fx, fy);//有限制的点优先成为根节点 
                if (fx != fy) //他们两个点还没有被相互约束的关系（不在同一个集合里）
                {
                    f[fx] = fy;
                    d[fx] = (-d[x] + now + d[y] + 2) & 1;
                    if (g[fx] != -1 && g[fy] != -1 && (g[fx] ^ g[fy]) != d[fx])
                    {//如果两个点已经固定了数值，且和它们所要遵循的约束关系不符 
                        flag = 0;
                        break;
                    }
                }
                else
                {
                    dis = d[x] ^ d[y];
                    if (dis != now)
                    {
                        flag = 0;
                        break;
                    }
                }
            }
            ans[l] = -1;//第 n+1 号节点是空的啦
            if (!flag) continue;
            fo (i, 2, n + m)//第 1 号节点也是空的啦
            {
                fx = find(i);
                if (g[fx] == -1) 
                {
                    g[fx] = 0;
                    ans[l]++;
                }
            }
        }
    fo (i, 0, 1)
        if (ans[i] != -1)
            final = (final + pow(ans[i])) % mod;
    printf("%lld", final);
}