問題一覧 > 通常問題

No.2164 Equal Balls

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 37
作問者 : PCTprobability / テスター : NyaanNyaan
お気に入りにしたユーザー ProblemId : 7233 / 自分の提出
問題文最終更新日: 2022-12-15 00:07:09
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
Advent Calendar Contest 2022 (順位表) の他の問題:

Problem Statement

There are $N$ red boxes and blue boxes. The $i$-th red box contains $A_i$ balls, and the $j$-th blue box contains $B_j$ balls. All balls are distinguishable from one another.

Among the ways to choose some balls from the boxes, find the number of those satisfying the following condition, and output it modulo $998244353$.

  • Suppose that $C_i$ balls are chosen from the $i$-th red box and $D_j$ balls are chosen from the $j$-th blue box. Then, for all integers $i$ satisfying $1 \le i \le N-M+1$, $\displaystyle \sum_{j=1}^{M} C_{i+j-1} = \sum_{k=1}^{M} D_{i+k-1}$ holds.

Constraints

  • All inputs are integers.
  • $1 \le N \le 2 \times 10^5$
  • $1 \le M \le \mathrm{min}(300,N)$
  • $1 \le A_i,B_i \le 300$

Input

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

Output

Output the answer on $1$ line.

Sample

Sample 1
Input
2 2
1 1
1 1
Output
6

Let $r_1$ be the ball in red box $1$, $r_2$ the ball in red box $2$, $b_1$ the ball in blue box $1$, and $b_2$ the ball in blue box $2$.

The possible ways to choose the balls are the following $6$ ways: $\{\},\{r_1,b_1\},\{r_1,b_2\},\{r_2,b_1\},\{r_2,b_2\},\{r_1,r_2,b_1,b_2\}$.

Sample 2
Input
3 2
1 2 3
4 5 6
Output
20160

Note that balls in the same box are also distinguishable.

Sample 3
Input
10 4
58 28 48 29 21 10 98 32 84 37
11 91 74 30 24 51 37 20 99 16
Output
235475848

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