2322 . 拿鍋貼
TopCoder
Tags
Description
水果王國最近舉辦了一個營隊，其中一項（次要）目標就是把上次包鍋貼大賽的鍋貼吃掉。
到了午餐時間，有 $N$ 個人排成一列準備去拿鍋貼，已知活動主辦方事先指定好了排在第 $i$ 位的人可以拿 $A_i$ 個鍋貼。
但是人有時候會因為各種原因想吃更多的鍋貼或是更少的鍋貼，那麼為了讓每個人都可以拿到足夠的鍋貼，第 $i$ 個人的鍋貼數量，假設是 $X_i$，最多只能是前 $i-1$ 個人剩下的鍋貼數量 $+ A_i$，換句話說，對於所有的 $j$，$X_j \leq (\sum\limits_{i=1}^ {j-1} (A_i-X_i) )+ A_j$ 。
另外人有食量限制，主要是由以下的兩個數字 $B_i$ 跟 $C_i$ 定義，代表說 $X_i$ 要介在 $B_i$ 跟 $C_i$ 之間（含）才能吃飽又不至於吃得太撐。
現在活動主辦方很好奇，在這些限制下有多少種可能的 $X$ 序列滿足以上的條件。由於答案很大，請輸出答案 $\text{mod} \ 998244353$ 的餘數。
兩個序列 $X, Y$ 被視為不同若且唯若存在 $i$ 滿足 $X_i \neq Y_i$。
Input Format
第一行有一個整數 $N$，代表總共有幾個人。
第二行有 $N$ 個整數 $A_i$。
第三行有 $N$ 個整數 $B_i$。
第四行有 $N$ 個整數 $C_i$。
對於所有測試資料：
- $1 \leq N \leq 2000$
- $0\leq A_i\leq 5000$
- $1 \leq \sum\limits^ n_{i=1} A_i \leq 5000$
- $0 \leq B_i \leq C_i \leq 5000$
Output Format
輸出一個正整數，代表答案 $\text{mod} \ 998244353$ 的餘數
Sample Input 1
2
2 2
1 1
3 3
2 2
1 1
3 3
Sample Output 1
5
Sample Input 2
4
3 4 2 5
0 0 0 0
2000 2000 2000 2000
3 4 2 5
0 0 0 0
2000 2000 2000 2000
Sample Output 2
1333
Hints
範測一解釋：
$X = [1, 1], [1,2], [1, 3], [2, 1], [2, 2]$ 是符合條件的所有可能
$[3, 1]$ 不符合條件因為 $X_1 > A_1$
$[2, 0]$ 不符合條件因為 $X_2 < B_2$
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~15 | $N \leq 500$, $\sum\limits^ n_{i=1} A_i \leq 500$ | 32 |
| 3 | 16~27 | $B_i = 0$, $C_i = 5000$ | 29 |
| 4 | 0~38 | 無額外限制 | 39 |