CF1574E

dottle · 2021-09-21 11:51:59 · 题解

对于一种合法的染色方案，它要么是相邻列之间异色，要么是相邻行之间异色，二者至少满足其一。因此，我们考虑对方阵的染色方案计数相当于就是对第一列/行的染色方案计数。

我们先考虑相邻行异色，对于相邻列异色的情况是相似的。

那么对于每一个格子，它将限制第一行它所在列只能填特定颜色（若此格在奇数行，第一行与它同色；反之异色），这就将第一行的格子分为了三种：无限制，有颜色限制和矛盾。有限制的列我们可以不管，我们记录 cnt 代表有多少个无限制的列，lim 代表有多少个矛盾的列。若 lim\ne0，则答案为 0，否则为 2^{cnt}。我们再维护 C_{0/1,i} 代表第 i 列有多少格子限制为白/黑。若黑白都未被限制则是无限制列，都被限制则是矛盾列。在修改一个点颜色的时候维护这些信息即可。

对于相邻列异色我们也这样算。

最后，将所有格子染成黑白相间的两种方案既是相邻行异色，也是相邻列异色，会重复计算，减去即可。这个信息的维护方式与上面几乎一致，就不再赘述了。