「CF2145G」Cost of Coloring
有一个 n \times m 的网格图。最初,每个格点都没有颜色。
每次操作,你可以选择任意一行或一列染色。在第一次操作中,你只能选择颜色 1;在第 i(i > 1) 次操作,你可以选择颜色 c_{i - 1} 或 c_{i - 1} + 1(其中 c_{i - 1} 表示第 i - 1 次操作选择的颜色)。
如果满足以下条件,我们称最终的染色结果为优美:
- 每个单元格都被染色。
- 1 \sim k 的每个颜色都被使用(至少有一个单元格被染成该颜色)。
对于优美的最终染色,我们定义优美值为实现该染色方案最少需要的操作次数。
对于 i = \min(n, m), \dots, n + m - 1,你需要求出优美值为 i 的优美染色个数。
数据范围:2 \leq n, m \leq 2000,1 \leq k \leq n + m - 1。
时空限制:3s / 512MiB。