/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
正整数 N,K および長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
\displaystyle \sum_{1\leq l\leq r\leq N} \Bigg(\sum_{l\leq i\leq r} A_i\Bigg)^K の値を 998244353 で割った余りを求めてください。
制約
- 1\leq N \leq 2\times 10^5
- 1\leq K \leq 10
- 0\leq A_i < 998244353
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
3 2 3 1 2
出力例 1
75
求める値は A_1^2+A_2^2+A_3^2+(A_1+A_2)^2+(A_2+A_3)^2+(A_1+A_2+A_3)^2=3^2+1^2+2^2+4^2+3^2+6^2=75 です。
入力例 2
1 10 0
出力例 2
0
入力例 3
10 5 91 59 85 60 57 72 12 3 27 16
出力例 3
428633385
998244353 で割った余りを求めることに注意してください。
Score : 550 points
Problem Statement
You are given positive integers N, K, and an integer sequence of length N: A = (A_1, A_2, \dots, A_N).
Find \displaystyle \sum_{1\leq l\leq r\leq N} \Bigg(\sum_{l\leq i\leq r} A_i\Bigg)^K, modulo 998244353.
Constraints
- 1\leq N \leq 2\times 10^5
- 1\leq K \leq 10
- 0 \leq A_i < 998244353
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
3 2 3 1 2
Sample Output 1
75
The value is A_1^2+A_2^2+A_3^2+(A_1+A_2)^2+(A_2+A_3)^2+(A_1+A_2+A_3)^2=3^2+1^2+2^2+4^2+3^2+6^2=75.
Sample Input 2
1 10 0
Sample Output 2
0
Sample Input 3
10 5 91 59 85 60 57 72 12 3 27 16
Sample Output 3
428633385
Be sure to find the sum modulo 998244353.