← 返回题目列表

Codeforces · 2145/G

G. 着色成本

中文机器翻译题面 查看原题

有一张纸,分为 $$$n$$$ 行和 $$$m$$$ 列。最初,该工作表的任何单元格都没有着色。

在一项操作中,您可以选择任意列或行并为其着色(如果某些单元格之前已着色,则它们的颜色将更改为新颜色)。在第一个操作期间,单元格的颜色为$$$1$$$;在 $$$i \gt 1$$$ 操作期间,您可以选择颜色 $$$c_{i-1}$$$ 或 $$$c_{i-1} + 1$$$,其中 $$$c_{i-1}$$$ 是在操作 $$$(i-1)$$$ 期间选择的颜色。

如果满足以下条件,我们称最终着色很漂亮:

  • 每个单元格都有颜色;
  • 对于从 $$$1$$$ 到 $$$k$$$ 的每种颜色,至少有一个单元格采用该颜色着色,并且在着色中不使用其他颜色。

为了获得漂亮的最终着色,我们将其值定义为实现它所需的最少操作数。

对于从 $$$\min(n, m)$$$ 到 $$$n + m - 1$$$ 的每个 $$$i$$$,计算值为 $$$i$$$ 的漂亮颜色的数量。如果两种颜色中至少一个细胞的颜色不同,则认为这两种颜色不同。

输入

输入由一行组成,其中包含三个整数 $$$n, m, k$$$ ($$$2 \le n, m \le 2000$$$; $$$1 \le k \le n + m - 1$$$)。

输出

对于从 $$$\min(n, m)$$$ 到 $$$n + m - 1$$$ 的每个 $$$i$$$,输出一个整数 - 值为 $$$i$$$ 的漂亮颜色的数量,以 $$$998244353$$$ 为模。 数组 $$$b$$$ 的

示例

输入
复制

2 3 2

输出
复制

2 12 6 

输入
复制

2 3 3

输出
复制

0 18 36 

输入
复制

3 2 4

输出
复制

0 0 36 

输入
复制

2 2 3

输出
复制

0 8 

输入
复制

2 2 2

输出
复制

4 4 

输入
复制

2 2 1

输出
复制

1 0 

输入
复制

5 3 4

输出
复制

0 90 1500 7830 8100 

输入
复制

3 5 3

输出
复制

6 120 750 1770 930 

输入
复制

5 2 2

输出
复制

2 15 30 35 10 

输入
复制

2 5 2

输出
复制

2 15 30 35 10