I - Flip Cards [TGC Edition]

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

配点:300300

問題文

11 から NN までの番号がついた NN 枚のカードが一列に並んでいて,カード ii とカード i+1i+1 とが隣り合っています.(1i<N\scriptsize 1 \leq i < N)
カード ii の表に整数 AiA_i が,裏に整数 BiB_i が書かれています.
また,はじめ全てのカードは表向きです.

MojaMoja 君は次の条件をいずれも満たすようにカードを裏返します:

  • 表を向いたカードが 11 枚より多く連続しない.
  • 裏を向いたカードが KK 枚より多く連続しない.

このとき,NN 枚のカードの向いている面に書かれた整数の総和を,その裏返し方のスコアとします.
条件を満たすような全ての裏返し方におけるスコアの総和を求めてください.

ただし,答えは非常に大きくなる場合があるため,998244353998244353 で割ったあまりを答えてください.

制約

  • 1Φ1031 \leq \Phi \leq 10^3
  • 1N,K1 \leq N, K
  • ϕΦϕ(N),ϕΦϕ(K)103\sum_{\phi} \Phi_{\phi}(N), \sum_{\phi} \Phi_{\phi}(K) \leq 10^3
  • 0Ai,Bi<230(1iN)0 \leq A_i, B_i < 2^{30} \scriptsize \; (1 \leq i \leq N)
  • 入力はすべて整数

入力

各テストケースの入力は,それぞれ以下の形式で与えられる:

NKN \enspace K
A1A2ANA_1 \enspace A_2 \enspace \ldots A_N
B1B2BNB_1 \enspace B_2 \enspace \ldots B_N

出力

答えを出力せよ.

サンプル

入力例1
1
5 2
3 4 5 7 5
2 3 1 4 2
出力例1
120

カードの表を +,裏を - として表すと,ありうるカードの裏返し方は + - - + -+ - + - -+ - + - +- - + - -- - + - +- + - - +- + - + -77 通りです.
これらのスコアはそれぞれ 16,17,20,16,19,16,1616, 17, 20, 16, 19, 16, 16 ですから,これらの総和である 120120 (を 998244353998244353 で割ったあまり) を答えればよいです.


入力例2
3
5 1
1 2 3 4 5
5 4 3 2 1
5 100
1 2 3 4 5
1 2 3 4 5
5 3
0 0 0 0 0
0 0 0 0 0
出力例2
30
195
0

Submit


Go (1.21)