• atcoder, dp

Atcoder Coddi2018 F.Square

题目描述

有一个n*n的网格，有一些位置已经填好，问有多少种填法使对于每个1<i<j<n，(i,i)到(j,j)间的网格数的和是偶数。

题解

先假设对角线下一半的数都是0，令x_i=a_{i,i}。
– 考虑每个2*2的正方形，发现a_{i,i+1}=x_i+x_{i+1}。
– 考虑每个3*3的正方形，发现a_{i,i+2}=x_{i+1}。
– 更大的正方形只能是0.(用容斥的方法可以得到上述结论)。
那我们可以逆推：
– 如果a_{i,i}填入一个数，那么x_i=a_{i,i}。
– 如果a_{i,i+1}填入一个数，那么x_i+x_{i+1}=a_{i,i+1}。
– 如果a_{i,i+2}填入一个数，那么x_{i+1}=a_{i,i+2}。
– 其他位置都是0。
所以我们只需要决定对角线的数，其他位置都是固定的。
这是个简单的dp问题。
那么如果下面不是0呢？
可以转化成0！定义a_{i,j}和a_{j,i}为对应位置，只要让对应位置的数相等就可以随意转化。
– 如果两个位置上都填了数，就把下一半的数设置成0，上一半变成它们的和。
– 如果有一个位置填了数，就把下一半设置成0，上一半变成无限制。（如果是1就相当于下面的数也填1，不影响结果）
– 如果没有位置填数，就把下一半设置成0，上一半变成无限制。并把结果*2（都是0或都是1）。

细节处理很烦。