Powers

AtCoder

IDarc106_d

Time3000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

3 3
1 2 3

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$.

Input #2

10 10
1 1 1 1 1 1 1 1 1 1

Output #2

Input #3

2 5
1234 5678

Output #3

6912
47775744
805306038
64822328
838460992

Be sure to print the sum modulo $998244353$.

API Response (JSON)

{
  "problem": {
    "name": "Powers",
    "description": {
      "content": "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} \\su",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc106_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given are integer sequence of length $N$, $A = (A_1, A_2, \\cdots, A_N)$, and an integer $K$.\nFor each $X$ such that $1 \\le X \\le K$, find the following value:\n$\\left(\\displaystyle \\sum_{L=1}^{N-1} \\su...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments