201063: [AtCoder]ARC106 D - Powers

Memory Limit:1024 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

Given are integer sequence of length $N$, $A = (A_1, A_2, \cdots, A_N)$, and an integer $K$.

For each $X$ such that $1 \le X \le K$, find the following value:

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

Constraints

  • All values in input are integers.
  • $ 2 \le N \le 2 \times 10^5$
  • $ 1 \le K \le 300 $
  • $ 1 \le A_i \le 10^8 $

Input

Input is given from Standard Input in the following format:

$N$ $K$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

Print $K$ lines.

The $X$-th line should contain the value $\left(\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X \right) \bmod 998244353$.


Sample Input 1

3 3
1 2 3

Sample Output 1

12
50
216

In the $1$-st line, we should print $(1+2)^1 + (1+3)^1 + (2+3)^1 = 3 + 4 + 5 = 12$.

In the $2$-nd line, we should print $(1+2)^2 + (1+3)^2 + (2+3)^2 = 9 + 16 + 25 = 50$.

In the $3$-rd line, we should print $(1+2)^3 + (1+3)^3 + (2+3)^3 = 27 + 64 + 125 = 216$.


Sample Input 2

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

Sample Output 2

90
180
360
720
1440
2880
5760
11520
23040
46080

Sample Input 3

2 5
1234 5678

Sample Output 3

6912
47775744
805306038
64822328
838460992

Be sure to print the sum modulo $998244353$.

Input

题意翻译

给定长度为 $n$ 的序列 $a$,以及一个整数 $k$。 对于每个 $1\le x \le k$,求出如下式子的值: $$\sum_{l=1}^{n-1}\sum_{r=l+1}^n \left(a_l + a_r\right)^ x$$ 答案对 $998244353$ 取模。 $2\le n \le 2\times 10^5,\ 1 \le k \le 300, \ 1\le a_i \le 10^8$。

加入题单

算法标签: