No.2164 Equal Balls
レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 :
PCTprobability
/ テスター :
NyaanNyaan
タグ : / 解いたユーザー数 35
作問者 :
PCTprobability
/ テスター :
NyaanNyaan
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。