No.3247 Multiplication 8 2
タグ : / 解いたユーザー数 23
作問者 :
AngrySadEight
/ テスター :
遭難者
👑 
ygussany
問題文
各要素が $1, 2, -1, -2$ である長さ $N$ の数列 $A$ および整数 $K$ が与えられます．
また，$0 = B_1 < B_2 < \dots < B_L = N$ を満たす長さ $L$ の整数列 $B$ に対し，そのスコアを次の式で定めます．
- $1 \leq i \leq L - 1$ を満たす全ての整数 $i$ に対し，$A_{B_i + 1} \times A_{B_i + 2} \times \dots \times A_{B_{i+1}} = 8$ が成り立つ場合，$\sum_{i=1}^{L-1}(B_{i+1} - B_i)^K$．
- そうでない場合，$0$．
整数列 $B$ として考えられるものは $2^{N-1}$ 通り考えられますが，それらすべてに対するスコアの総和を $998244353$ で割った余りを求めてください．
制約
- 入力は全て整数
- $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\}$
入力
入力は以下の形式で標準入力から与えられる．
$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$
出力
答えを出力せよ．
サンプル
サンプル1
入力
5 2 1 2 2 -1 -2
出力
25
スコアが $0$ とならない整数列 $B$ は，$B = (0, 5)$ の $1$ 通りのみです．
$B = (0, 5)$ のスコアは $(5 - 0)^2 = 25$ であるため，スコアの総和は $25$ となります．
サンプル2
入力
8 8 1 1 1 1 1 1 1 1
出力
0
どの整数列 $B$ に対するスコアも $0$ であるため，スコアの総和は $0$ となります．
サンプル3
入力
8 3 2 -2 -1 2 1 -2 2 -2
出力
280
スコアが $0$ でない整数列 $B$ は，$B = (0, 4, 8)$ と $B = (0, 5, 8)$ の $2$ つです．
- 整数列 $B = (0, 4, 8)$ のスコアは，$(4 - 0)^3 + (8 - 4)^3 = 128$ です．
- 整数列 $B = (0, 5, 8)$ のスコアは，$(5 - 0)^3 + (8 - 5)^3 = 152$ です．
したがって，全ての整数列 $B$ に対するスコアの総和は $128 + 152 = 280$ となります．
サンプル4
入力
18 888000000 1 2 -1 -2 1 2 1 2 -1 -2 1 2 1 2 -1 -2 1 2
出力
921567506
スコアの総和を $998244353$ で割った余りを出力してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。