自动搬运

查看原文

来自洛谷，原作者为

	yyyyxh OI 是啥 (O_o)？

搬运于2025-08-24 23:00:13，当前版本为作者最后更新于2024-08-28 08:27:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

萌萌计数签到题！还是有有趣且直接的做法的。题解区现有做法有点麻烦了！

考虑枚举 $N$ 行中有 $a$ 行和为 $1$，$b$ 行和为 $2$；$M$ 列中有 $c$ 列和为 $1$，$d$ 列和为 $2$。

容易发现这个枚举量是 $O(\min(N,M))$ 级别的，因为我们有 $a+b=N,c+d=M,a+2b=c+2d$。

我们考虑把每一列的 $1$ 和 $2$ 的和分配到行上去，可以看作这样一个过程：有 $M$ 种颜色的小球，其中 $c$ 种颜色各有一个小球，$d$ 种颜色各有两个小球。然后你需要把这些小球划分成 $N$ 个大小不超过 $2$ 的非空集合序列，满足同一个集合的球颜色互不相同。（即集合有标号，但同一个集合内的球无标号）

那首先我们考虑把这 $c+2d$ 个球排成一个序列有多少种可能，容易发现是多重集组合数 $\frac{(c+2d)!}{2^d}$。然后我们把这个序列按顺序分配给每个集合。此时可能会出现两个问题：

• 分配出了如 $\{1,1\}$ 这样两个相同元素的集合。

• $\{1,2\}$ 和 $\{2,1\}$ 两种分配方式应该算作同一种方案。

考虑容斥掉第一种情况后第二种方案数直接乘上 $2^{-b}$ 就可以了。

那么我们钦定有 $t$ 个集合一定被分配到了相等的数，式子就是：

$$\sum_{a+b=N,c+d=M,a+2b=c+2d} {N\choose b}{M\choose d}\sum_{t=0}^{\min(b,d)} (-1)^t{b\choose t}{d\choose t}t! \frac{(c+2d-2t)!}{2^{b+d-t}} $$

复杂度 $O(\min(N,M)^2)$，做完了。