题解

思路

枚举上方恰放 $i$ 个车。上方有 $\binom bi\binom ai i!$ 种；它占用 $i$ 个共享列，下方有 $\binom d{k-i}\binom{a+c-i}{k-i}(k-i)!$ 种。

做法

预处理阶乘和逆阶乘到 $\max(a+c,b,d)$，枚举 $i=0\ldots k$ 累加上述乘积。非法组合数返回零。小棋盘可逐行做列 mask DP；$b=0$ 时直接使用矩形闭式。

复杂度

时间复杂度 $O(\max(a+c,b,d)+k)$，空间复杂度 $O(\max(a+c,b,d))$。