NOIP2024集训Day37 DP

NOIP2024集训Day37 DP

A. [CQOI2011] 放棋子

设 \(f_{i, j, k}\) 表示前 \(k\) 种棋子放了任意 \(i\) 行、\(j\) 列。决策是：在哪些位置填同种颜色的棋子。

于是美剧上一个状态的 \(i, j\)（表示为 \(l, r\)），上一状态 \(k_1 = k - 1\)。

设 \(g_{i, j, k}\) 表示 \(k\) 个同种颜色的棋子放了任意 \(i\) 行、\(j\) 列的方案数，则 \(f_{i, j, k} = f_{i, j, k} + f_{l, r, k - 1} \times g_{i, j, k} \times \dbinom{n - l}{i - l}\times \dbinom{m - r}{i - r}\)。

\(\dbinom{n - l}{i - l}\) 表示在空着的 \(n - l\) 行中选出 \(i - l\) 行放棋子。\(\dbinom{m - r}{i - r}\) 同理。

怎么求 \(g_{i, j, k}\)?

直接求不行，那就换一种思路——容斥，用所有方案减去不合法的方案（即有行列没有填，或者可以理解为合法的局部方案）。

\(g_{i, j} = \dbinom{i \times j}{k} - g_{l, r} \times \dbinom{i}{l} \times \dbinom{j}{r}\)。

依式转移即可。

由于只要放完棋子而不一定要摆满行列，则 \(ans = \sum\limits_{i = 1}^{m} \sum\limits_{j = 1}^{n} f_{i, j, c}\)。

注意：

• 允许一种颜色的棋子只放行、不放列的情况。
• 注意 \(\dbinom{n}{m}\) 中 \(n\ge m\)。