[ CF1391D ] D.505 思维

D.505

网上的各种状态压缩DP的方法看球不懂，在status里看了一个歪果仁的解法，惊为天人，写个题解记录一下。

首先最基本的，这题条件规定了\(n\le m\)，因为\(n\ge 4\)时，一个\(4\ast4\)的正方形有4个\(2\ast2\)的正方形，四个奇数相加必然为偶数，所以\(n\ge 4\)直接输出-1.

n=1时根据出题人要求输出0.

n=2时，我们可以发现，对于一个所有子正方形合法的矩形，它的列中‘1’的个数的奇偶序列必然是：奇偶奇偶 或 偶奇偶奇。一列的情况最多只有3种：0,1,2，这三种状态随时都可以通过只修改一次变为对立的奇偶状态，比如0可以变1成奇数。那么我们只要计算按照两种情况所需修改的最小次数即可。

n=3时，情况复杂起来了。我们记录一下每一列的前两个元素的1的个数和后两个元素的1的个数。我们可以发现，对于一个所有子正方形合法的矩形，它的列中‘1’的个数的就序列必然是：

同时我们发现 偶奇 奇偶 偶偶 奇奇 都可以只修改一次就相互转换。那么有一列完全为0怎么为偶呢？？放心，他的上一列或者下一列一定不完全为0（因为是奇），还是可以保证子正方形是合法的。

代码就不放了，非常的好写。