No.3247 Multiplication 8 2
タグ : / 解いたユーザー数 24
作問者 : 👑
Problem Statement
You are given a sequence $A$ of length $N$, where each element is one of $1, 2, -1, -2$, and an integer $K$.
For an integer sequence $B$ of length $L$ satisfying $0 = B_1 < B_2 < \dots < B_L = N$, its score is defined as follows.
- If $A_{B_i + 1} \times A_{B_i + 2} \times \dots \times A_{B_{i+1}} = 8$ holds for all integers $i$ satisfying $1 \leq i \leq L - 1$, the score is $\sum_{i=1}^{L-1}(B_{i+1} - B_i)^K$.
- Otherwise, the score is $0$.
There are $2^{N-1}$ possible integer sequences $B$. Find the sum of the scores over all of them, modulo $998244353$.
Constraints
- All input values are integers.
- $1 \leq N \leq 8.88 \times 10^5$
- $1 \leq K \leq 8.88 \times 10^8$
- $A_i \in \{1, 2, -1, -2\}$
Input
The input is given from Standard Input in the following format.
$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Output the answer.
Sample
Sample 1
Input
5 2 1 2 2 -1 -2
Output
25
The only integer sequence $B$ whose score is not $0$ is $B = (0, 5)$, which is $1$ sequence.
The score of $B = (0, 5)$ is $(5 - 0)^2 = 25$, so the sum of the scores is $25$.
Sample 2
Input
8 8 1 1 1 1 1 1 1 1
Output
0
The score of every integer sequence $B$ is $0$, so the sum of the scores is $0$.
Sample 3
Input
8 3 2 -2 -1 2 1 -2 2 -2
Output
280
There are $2$ integer sequences $B$ whose score is not $0$: $B = (0, 4, 8)$ and $B = (0, 5, 8)$.
- The score of the integer sequence $B = (0, 4, 8)$ is $(4 - 0)^3 + (8 - 4)^3 = 128$.
- The score of the integer sequence $B = (0, 5, 8)$ is $(5 - 0)^3 + (8 - 5)^3 = 152$.
Therefore, the sum of the scores over all integer sequences $B$ is $128 + 152 = 280$.
Sample 4
Input
18 888000000 1 2 -1 -2 1 2 1 2 -1 -2 1 2 1 2 -1 -2 1 2
Output
921567506
Output the sum of the scores modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。