CF997C

CF997C Sky Full of Stars

这道题的第一想法就是用总方案数减去不合法的方案,显然不合法的方案就是没有一行 / 一列 是全部相同的。

那么这就可以把行列分开讨论:

  • 没有一列合法的方案总数为:$(3^n-3)^n$
  • 至少有一行合法且没有列合法的方案总数为:$-\sum\limits_{i=1}^n(-1)^i\binom ni\left(3\times\left(3^{n-i}-1\right)^n+\left(3^i-3\right)\times3^{n(n-i)}\right)$

简单说明一下,就是枚举有几行是相同的,然后又需要分类讨论了:

  • 若:这几行的颜色都相同,那么所有列的都没有一个合法的
  • 若:这几行颜色不同,那么剩下的就可以乱选了

总结一下,答案就是:

所以预处理一下,整体时间复杂度就是 $O(n\log n)$ 的了,只可惜考场没有推出来。。。

Code