All Tracks Math Problem

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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HourStorm #8

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?