A summation problem
Tag(s):

## Fast Fourier transform, Hard, Linear Algebra, Mathematics, fft

Problem
Editorial
Analytics

You are given an array $A$ of integers of size $N$ , and one more integer $K$. Now, we define $K$ distinct functions, $f_i(l,r), 1 \le i \le K$. All functions have the domain equal to the set of all ordered pairs of integers $\{ (x,y) : \hspace{0.2cm} x \le y$ and $1 \le x,y \le N \}$

$f_i(l,r) =( \sum_{j=l}^{r} a[j] )^{i}$.

Now you need to find and print for for each of the $K$ functions, the sum of function values of all elements in its domain. As the answer could be rather large, you need to find and print it Modulo $998244353$, a widely used prime.

Input Format :

The first line contains $2$ space separated integers $N$ and $K$. The next line contains $N$ space separated integers, denoting the given array.

Output Format:

Print $K$ space separated integers, where the $i^{th}$ integer is the answer for the $i^{th}$ function described above.

Constraints :

$1 \le N \cdot K \le 2 \cdot 10^6$

$1 \le N,K \le 10^6$, this ensures the input/output size remains resonable.

$0 \le A[i] < 998244353$

SAMPLE INPUT
3 2
1 2 3
SAMPLE OUTPUT
20 84
Explanation

Here, $f_1(1,1)=1,f_1(1,2)=3,f_1(1,3)=6,f_1(2,2)=2,f_1(2,3)=5,f_1(3,3)=3$, so answer = $1+3+6+2+5+3=20$

Similarily,

$f_2(1,1)=1,f_2(1,2)=9,f_2(1,3)=36,f_2(2,2)=4,f_2(2,3)=25,f_2(3,3)=9$, so answer = $1+9+36+4+25+9 = 84$

Time Limit: 2.5 sec(s) for each input file.
Memory Limit: 1024 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

HourStorm #8

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Greedy Algorithms
• Algorithms > Dynamic Programming

?