[COTS/CETS 2024] 奇偶矩阵 Solution

· · 题解

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

考虑枚举 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}。然后我们把这个序列按顺序分配给每个集合。此时可能会出现两个问题：

考虑容斥掉第一种情况后第二种方案数直接乘上 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)，做完了。