CFCF2145G.Cost of Coloring
省选/NOI-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
有一张纸被划分为 n 行 m 列。最初,这张纸的每一个格子都没有被染色。
在一次操作中,你可以任选一行或一列进行染色(若某些格子已被染色,则颜色会被改变为新的颜色)。第 1 次操作时,格子被染为颜色 1;第 i>1 次操作时,你可以选择颜色 ci−1 或 ci−1+1,其中 ci−1 表示第 i−1 次操作所选择的颜色。
我们称最终的染色方案为“美丽的”,当且仅当:
- 每一个格子都被染色;
- 对于每种颜色 1 到 k,至少有一个格子被染成该颜色,且不存在其它颜色被使用。
对于一种美丽的最终染色,我们定义其价值为达到此方案所需的最小操作次数。
请对于每一个 i 从 min(n,m) 到 n+m−1,计算“价值为 i 的美丽染色方案的数量”。如果至少有一个格子的颜色不同,则认为两个染色方案不同。
输入格式
输入包含一行,包含三个整数 n,m,k(2≤n,m≤2000;1≤k≤n+m−1)。
输出格式
对于每个 i 从 min(n,m) 到 n+m−1,输出一个整数,表示价值为 i 的美丽染色方案数量,对 998244353 取模。
输入输出样例
输入#1
2 3 2
输出#1
2 12 6