一开始死想想不出来，后来看了题解发现是容斥 + 推柿子。我对容斥还是太不熟悉了啊/kk
注意到「一行或一列是同一种颜色」的字眼，其实是容斥的标志。考虑每行每列（一共 (2n) 个元素）是同一种颜色的方案集合，那么最终答案就是这 (2n) 个集合的并的大小。考虑对琪容斥。
那么某些集合的交是「这些行 / 列都要是同一种颜色的方案集合」这种形式。那么每个交的大小要比并容易算多了，显然相等是等价关系，于是看建图之后有几个连通分量，(3) 的它次方就好了。显然可以分成两类：
-
全是行 / 全是列。那么对于 (i) 个集合的交集的大小，它们的方案数一定是 (3^{n^2-i(n-1)})。也就是说我们可以不必枚举每个 bitmask，因为只要参与交集的集合数量相同，它的值就是一样的，可以用乘法（乘个组合数即可），枚举参与交集的集合数量即可。说明容斥很可能也是有多项式复杂度的。那么这种情况对答案的贡献是
[2sum_{i=1}^n(-1)^{i+1}dbinom ni3^{n^2-i(n-1)} ]这个直接照着跑一遍就好了；
-
既有行又有列。那么考虑 (i) 行 (j) 列的方案数。显然所有这些行列所包含的格子都连成了一个连通块，所以方案数是 (3^{n^2-in-j(n-i)+1})。那么总贡献就是
[sum_{i=1}^nsum_{j=1}^n(-1)^{i+j+1}dbinom nidbinom nj3^{n^2-in-j(n-i)+1} ]这个是 (Omega!left(n^2 ight)) 的，考虑推柿子优化。首先把所有只和 (i) 相关或常数提到第一个 (sum) 后面去：
[sum_{i=1}^n(-1)^{i+1}dbinom ni3^{n^2-in+1}sum_{j=1}^n(-1)^jdbinom nj3^{-j(n-i)} ]现在要想办法把后面的 (sum) 消掉。注意到里面既有组合数又有指数，很像二项式的形式，于是考虑变形，然后二项式定理逆用：
[egin{aligned}sum_{j=1}^n(-1)^jdbinom nj3^{-j(n-i)}&=sum_{j=0}^ndbinom njleft(-3^{-(n-i)} ight)^j-1\&=sum_{j=0}^ndbinom njleft(-3^{-(n-i)} ight)^j1^{n-j}-1\&=left(-3^{-(n-i)}+1 ight)^n-1end{aligned} ]
这样就可以很愉快的线性对数了。