← 返回题目列表

AtCoder · arc106_d

D. 权力

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

分数: 600 点

问题陈述

给定长度的整数序列 N, A = (A_1, A_2, \cdots, A_N),和一个整数 K.

对于每个 X 这样 1 \le X \le K,找到以下值:

\left(\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X\right) \bmod 998244353

约束

  • 输入中的所有值都是整数。
  • 2 \le N \le 2 \times 10^5
  • 1 \le K \le 300
  • 1 \le A_i \le 10^8

输入

输入由标准输入按以下格式给出:

N K
A_1 A_2 \cdots A_N

输出

打印 K 行。

的 X- 第行应包含该值 \left(\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X \right) \bmod 998244353.


示例输入 1

3 3
1 2 3

示例输出 1

12
50
216

在 1-st 行,我们应该打印 (1+2)^1 + (1+3)^1 + (2+3)^1 = 3 + 4 + 5 = 12.

在 2-nd 行,我们应该打印 (1+2)^2 + (1+3)^2 + (2+3)^2 = 9 + 16 + 25 = 50.

在 3-rd 行,我们应该打印 (1+2)^3 + (1+3)^3 + (2+3)^3 = 27 + 64 + 125 = 216.


示例输入 2

10 10
1 1 1 1 1 1 1 1 1 1

示例输出 2

90
180
360
720
1440
2880
5760
11520
23040
46080

示例输入 3

2 5
1234 5678

示例输出 3

6912
47775744
805306038
64822328
838460992

请务必打印模数总和 998244353.