#D. ARC106D - Powers

Type: Default

3000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Score : $600$ points

Problem Statement

Given are integer sequence of length $N$ , $A = (A_{1}, A_{2}, \dots, A_{N})$ , and an integer $K$ .

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

$(L = 1 \sum N - 1 R = L + 1 \sum N (A_{L} + A_{R})^{X}) m o d 998244353$

Constraints

All values in input are integers.
$2 \leq N \leq 2 \times 1 0^{5}$
$1 \leq K \leq 300$
$1 \leq A_{i} \leq 1 0^{8}$

Input

Input is given from Standard Input in the following format:

 $N$   $K$ 
 $A_{1}$   $A_{2}$   $\dots$   $A_{N}$

Output

Print $K$ lines.

The $X$ -th line should contain the value $(L = 1 \sum N - 1 R = L + 1 \sum N (A_{L} + A_{R})^{X}) m o d 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

Sample Input 3

2 5
1234 5678

Sample Output 3

Be sure to print the sum modulo $998244353$ .

ARC106

Not Attended

Status: Done
Rule: IOI
Problem: 6
Start at: 2023-7-5 8:15
End at: 2023-7-5 10:15
Duration: 2 hour(s)
Host: 梁泽贤 (liangzexian)
Partic.: 13

#D. ARC106D - Powers

ARC106D - Powers

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

ARC106

Status

Development

Support

#D. ARC106D - Powers

ARC106D - Powers

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

ARC106

Status

Development

Support

Don't have an account?

SIGN IN