mengbierr

一个蒟蒻的博客

12月26

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)。

细节处理很烦。

发表评论

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