Loj#6728 U 群把妹王

题意：现有 个格子，每个格子皆可涂成 种颜色之一。

给定正整数集合 ，定义一个染色合法当且仅当：

• 对于任意一行，记和它图案相同的行有 个（包括自身），。

• 对于任意一列，记和它图案相同的列有 个（包括自身），。

求有多少合法的染色方案。

，，时限 。

---

记

• ：有标号集合。
• ：有标号集合，大小在 中。
• ：有标号集合，大小在 中。
• ：染色矩阵。
• ：染色矩阵，行图案重复次数在集合 中，列图案重复次数在集合 中。
• ：染色矩阵，每行互不相同，每列互不相同。

易知 其中 分别表示矩阵的长和宽，都是 EGF。

对于一个矩阵染色 （ 行 列）和两个有标号集合序列 ，定义它们的复合 为：将 中的第 行扩展为下标为 的一系列行，将 中的第 列扩展为下标为 的一系列列，得到的新的矩阵染色。例如 在此基础上，可以定义 ，即“矩阵染色类”与两个“集合类”的复合。

可以发现，将 的行扩增为一个行集合、列扩增为列集合，就能得到 ，即 类似地

接下来考虑计算，难以写出 的封闭形式，但注意到只需要 系数，提取之： 其中 这是“幂的横截”，可以用拉格朗日反演计算，需要用到复合逆，可以 牛迭求出。

然后利用 得 后半部分和式可以卷积。