問題一覧 > 通常問題

No.2164 Equal Balls

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : 👑 PCTprobabilityPCTprobability / テスター : NyaanNyaanNyaanNyaan
1 ProblemId : 7233 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-15 00:07:09

問題文

$N$ 個の赤い箱と青い箱があり、$i$ 個目の赤い箱には $A_i$ 個のボールが、$j$ 個目の青い箱には $B_j$ 個のボールが入っています。すべてのボール同士は区別可能です。　

箱からいくつかのボールを選ぶ方法の内、以下の条件が成り立つようなものの個数を $998244353$ で割った余りを出力してください。

  • $i$ 個目の赤い箱から $C_i$ 個、$j$ 個目の青い箱から $D_j$ 個のボールを選んだとすると、$1 \le i \le N-M+1$ を満たす全ての整数 $i$ に対して $\displaystyle \sum_{j=1}^{M} C_{i+j-1} = \sum_{k=1}^{M} D_{i+k-1}$ が成り立つ。

制約

  • 入力は全て整数である。
  • $1 \le N \le 2 \times 10^5$
  • $1 \le M \le \mathrm{min}(300,N)$
  • $1 \le A_i,B_i \le 300$

入力

$N\ M$
$A_1\ A_2\ \dots\ A_N$
$B_1\ B_2\ \dots\ B_N$

出力

答えを $1$ 行に出力してください。

サンプル

サンプル1
入力
2 2
1 1
1 1
出力
6

赤い箱 $1$ のボールを $r_1$、赤い箱 $2$ のボールを $r_2$、青い箱 $1$ のボールを $b_1$、青い箱 $2$ のボールを $b_2$ とします。

ボールの選び方としてあり得るのは $\{\},\{r_1,b_1\},\{r_1,b_2\},\{r_2,b_1\},\{r_2,b_2\},\{r_1,r_2,b_1,b_2\}$ の $6$ 通りです。

サンプル2
入力
3 2
1 2 3
4 5 6
出力
20160

同じ箱に入っているボールも区別可能であることに注意してください。

サンプル3
入力
10 4
58 28 48 29 21 10 98 32 84 37
11 91 74 30 24 51 37 20 99 16
出力
235475848

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。