CF 461D Appleman and Complicated Task解题报告

题目


给你一个n*n网格,每一格要么是0要么是1要么为空,要求你用0或1填满所有空格,使得每个格子周围的0有偶数个。

题解

首先我们观察到这样一个事实:当第一行确定后,整个网格的填法就确定了。我们以N=8为例,把这种确定方法列出来:其中,“0246”这样的数的含义为,假设第一行为a[0..7],它表示该格的值是a[0] xor a[2] xor a[4] xor a[6].



可以发现,这个形式是很规整的。都是“246”或者“1357”这种,连续的奇/偶数。

因此,我们的问题就变成了:问有多少种a的取值,满足K组形如a[1] xor a[3] xor a[5] xor a[7] = 1(或者0)这样的限制。

不妨设a的“奇/偶前缀和”为s,就是说s[6] = a[0] xor a[2] xor a[4],s[5] = a[0] xor a[3],等等。那么a[1] xor a[3] xor a[5] xor a[7] = 1这个限制就变成了s[1] xor x[9] = 1.可以发现,所有对a的“段”限制都变成了s中某两个数的限制:它们要么相等要么相反。

这就变成了一道有成熟算法的题目:让每个s[i]都对应两个元素i和i’,二者的值相反。对于s[a] xor s[b] = 0这种限制,就把a和b,a’和b’放在同一个并查集中;对于s[a] xor s[b] = 1这种限制,就把a和b’,a’和b放在同一个并查集中。如果在某个时刻,某个a和a’被并在了一起,则无解。

设最后剩下的等价类数量是cnt,可以发现,其中有4个的值是确定的:s[0]和s[1],以及它们的反。因此,答案就是2^((cnt-4)/2).

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注