XorBoard

作者：冯哲

关键字：组合数

题目简述

有一个$H*W$的表格,初始时每个位置上都是$0$.

现在可以做$Rcount$次行操作,每次可以把一行的所有数都从$1$变$0$,$0$变$1$;还可以做$Ccount$次列操作,每次可以把一列的所有数都从$1$变$0$,$0$变$1$。

要求做完所有操作后$1$的个数为$S$,问方案数.

两种方案不同当且仅当至少有一行或一列被操作的次数不同.

$1 \leq H,W,Rcount,Ccount \leq 1555$

$1 \leq S \leq H*W$

解题思路

枚举最终被操作奇数次的行和列的个数$a,b$,此时$1$的个数为$a*W+b*H-a*b$.然后计算方案数,行上的方案数就是$H$个里面取$a$个的方案,再乘上将剩下的$\frac{(Rcount-a)} {2}$ 个相同的物品放进$H$个不同的位置的方案,后一部分显然就是$C(H+\frac{(N-a)}{2}-1,H-1)$,列上也是同理。

事实上,当我们枚举了$a$之后,有$b=\frac{(S-a*W)}{H-a}$,由此就不用枚举$b$了.

时间复杂度$O(N^2)$，空间复杂度$O(N^2)$.