CF997C Sky Full of Stars

题意：有一个 的正方形网格，用三种颜色染。

求有多少种方案使得至少一行或一列是同一种颜色。

答案对 取模，，时限 。

---

令：

• ：钦定有 行 列是同种颜色，其余任意的方案数。

• ：为恰好有 行 列是同种颜色的方案数。

答案：。

由组合意义易得 两个维度独立，施加高维二项式反演（两个维度的反演系数简单相乘） 这和容斥的结论一致。

---

接下来考虑如何快速计算 ，需要分类讨论。

• ：所有被钦定的行和列必须是同种颜色。 即：选定行列 x 钦定颜色 x 其余自由部分

• ：被钦定的行不必是同种颜色。 即：选定行 x 钦定颜色 x 其余自由部分

  （ 同理）

• ：完全自由，。

---

回忆： 根据上述讨论，分三部分求和。

• 第一部分：两个参数均不为 。

快速幂就可以 计算了。

• 第二部分：一个参数为 。

为 本质相同，只统计 的情形，然后将贡献翻倍即可。

• 第三部分：两个参数均为 。。

最终 。

总复杂度 。