← 返回题目列表

AtCoder · waipc_qual_f

F. 排序因素

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

配点 : 1200 点

問題文

正整数 N,M,K 。

满足以下条件的长度 N 的非负整数序列 a=(a_1,a_2,\ldots,a_N) ,好的 称为数列。 对于

  • 0 \leq a_1 \leq a_2 \leq \cdots \leq a_N \leq M

良好的数列 对于 a ,多项式 f_a(x) 定义如下。

  • f_a(x)=(\prod_{1 \leq i \leq K} (a_i+x)) \times (\prod_{K+1 \leq i \leq N} a_i)

所有的好数列 a 关于 f_a(x) 相加得到的多项式为 g(x) 。 显然 g(x) 是 您也可以写 K 是一个 次的多项式。 每一 i (0 \leq i \leq K), 第g(x) 可以得到第 i 次的系数 g_i 该值应乘以 998244353 后求余数。

制約

  • 1 \leq K \leq N \leq 250000
  • 1 \leq M \leq 250000
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M K

出力

g_0,g_1,\ldots,g_K 该值应乘以 998244353 对其取余后的结果按此顺序输出。


入力例 1

2 2 2

出力例 1

7 12 6

所有的好数列 a 以及对应的 f_a(x) 如下。

  • a=(0,0): f_a(x)=x^2
  • a=(0,1): f_a(x)=x^2+x
  • a=(0,2): f_a(x)=x^2+2x
  • a=(1,1): f_a(x)=x^2+2x+1
  • a=(1,2): f_a(x)=x^2+3x+2
  • a=(2,2): f_a(x)=x^2+4x+4

这些 f_a(x) 全部相加后,g(x)=6x^2+12x+7 变为。


入力例 2

3 4 2

出力例 2

350 357 105

入力例 3

15 10 1

出力例 3

403118239 34849843

入力例 4

250000 250000 5

出力例 4

528068001 689977268 512161527 103797525 493357217 965257117