問題一覧 > 通常問題

No.3247 Multiplication 8 2

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 24
作問者 : 👑 AngrySadEight / テスター : 👑 qand ygussany
お気に入りにしたユーザー ProblemId : 12407 / 自分の提出
問題文最終更新日: 2025-08-18 00:59:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 479 AngrySadEightお誕生日コンテスト2025 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。