/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ N の整数列 A = (A_1, A_2, \cdots, A_N) と整数 K が与えられます。
1 \le X \le K を満たす整数 X それぞれについて、以下の値を求めてください。
\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 行目には、(1+2)^1 + (1+3)^1 + (2+3)^1 = 3 + 4 + 5 = 12 を出力します。
2 行目には、(1+2)^2 + (1+3)^2 + (2+3)^2 = 9 + 16 + 25 = 50 を出力します。
3 行目には、(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
\bmod 998244353 での値を出力してください。
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.