CF1237F 题解

传送门

题意

给你一个 \(n \times m\) 的棋盘，上面已经放了 \(k\) 个 \(1 \times 2\) 的骨牌。

对于一个骨牌的每个格子，不能有其他骨牌的格子与它在同一行、同一列。

你可以在剩下的格子里放骨牌。

问这个棋盘有多少种放骨牌的方案。对 \(998244353\) 取模。

\(1 \le n,m \le 3600,0 \le k \le 2400\)

题解

对于两个同种骨牌（不妨设占 \(1\) 行 \(2\) 列），交换它们的 \(x\) 坐标，结果仍成立。这种性质启发我们将行列分开分析。

设有 \(i\) 个 \(1 \times 2\) 骨牌，\(j\) 个 \(2 \times 1\) 骨牌。则答案为 \(f(i,j) \times g(j,i) \times i! \times j!\)，其中 \(f(i,j)\) 表示只考虑行的限制，放 \(i\) 个 \(1 \times 1\)，\(j\) 个 \(2 \times 1\) 的方案。\(g\) 同理。

求 \(f\)。发现再加一维限制，\(f(k,i,j)\) 表示前 \(k\) 行，\(i\) 个 \(1\)，\(j\) 个 \(2\)，即可轻松转移。但复杂度 \(O(n^3)\)。因为 \(i\) 只占 \(1\)，不难想到只算 \(j\)，最后用组合数算答案。\(f(i,j)\) 表示前 \(i\) 行，\(j\) 个 \(2\)。则上面的 \(f(i,j)\) 为 \(f(n,j) \times \binom{cn-2j}{i}\)，其中 \(cn\) 表示有多少行可以放。于是实现 \(O(n^2)\)。