# 2024/3/30 APCS 第三場模擬賽 題解
## 轉譯 (Translation)
> 出題者：geK
> 難度：p1
> 考點：字串、迴圈
### Statement
RNA 是人體中非常重要的一部分，擁有非常多的功能，其中一種便是轉譯。
RNA 鹼基會以 $3$ 個鹼基為一單位，轉譯成對應的胺基酸，根據轉譯規則，序列從第一次遇到 AUG (起始密碼子) 開始觸發轉譯，轉譯至第一次遇到 UAA, UAG, UGA 其中一種時 (終止密碼子) 停下，接著就不再有轉譯動作。
如圖，AUG 為起始密碼子，UAA、UAG、UGA 為終止密碼子，且所有鹼基組合 (**除了終止密碼子**) 皆可生成胺基酸。
現在給定一條 $3'-DNA-5'$ 序列字串，請問在轉錄轉譯中，該 DNA 序列由左至右最多能轉譯出幾單位胺基酸？
### Input
輸入將有一個字串 $S\ (6 \le |S| \le 1000)$。
輸入保證必有起始密碼子以及終止密碼子。
### Output
輸出一個整數，代表轉譯後總共生成了多少胺基酸。
### Testcase
- Input 1
```
AUGCGGUAG
```
- Output 1
```
2
```
- Input 2
```
GAUGCCCUAAAUGUAA
```
- Output 2
```
2
```
- Input 3
```
CGGAUGAUGCGGUAAUAG
```
- Output 3
```
3
```
### Subtask
- Subtask 1 (50%) - 轉錄後第一組鹼基必為起始密碼子
- Subtask 2 (50%) - 無限制
### Note
測資一說明：
>轉譯在第 $1$ 個位置找到第一個起始密碼子 (AUG) 時觸發，接著開始三個三個一組在第 $7$ 個位置遇到第一個結尾密碼子 (UAG)，因此轉譯結束，中間總共經過了 $3$ 組 (AUG/CGG/UAG)，而因為結尾密碼子並不能夠生成胺基酸，所以總共生成了 $3-1 = 2$ 個，因此答案為 $2$。
測資二說明：
>轉譯在第 $2$ 個位置找到第一個起始密碼子 (AUG) 時觸發，接著開始三個三個一組在第 $8$ 個位置遇到第一個結尾密碼子 (UAA)，因此轉譯結束，中間總共經過了 $3$ 組 (AUG/CCC/UAA)，而因為結尾密碼子並不能夠生成胺基酸，所以總共生成了 $3-1 = 2$ 個，因此答案為 $2$。
### Solution
找到第一個 AUG 後，三個三個往下找終止密碼子，再把位置相減即可。
### Code
- subtask 1
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
string s;
cin>>s;
int n=s.size();
for(int i=3;i<n-2;i+=3){ //DNA-ATT¡ATC¡ACT RNA-UAA¡UAG¡UGA
if(s[i]=='U'){
if(s[i+1]=='A'){
if(s[i+2]=='A' || s[i+2]=='G'){
cout<<i/3;
return 0;
}
}
if(s[i+1]=='G'){
if(s[i+2]=='A'){
cout<<i/3;
return 0;
}
}
}
}
}
```
- subtask 2
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
string s;
cin>>s;
int n=s.size();
int fr=s.find("AUG");//DNA-TAC RNA-AUG
for(int i=fr+3;i<n-2;i+=3){ //DNA-ATT¡ATC¡ACT RNA-UAA¡UAG¡UGA
if(s[i]=='U'){
if(s[i+1]=='A'){
if(s[i+2]=='A' || s[i+2]=='G'){
cout<<(i-fr)/3;
return 0;
}
}
if(s[i+1]=='G'){
if(s[i+2]=='A'){
cout<<(i-fr)/3;
return 0;
}
}
}
}
}
```
- subtask 2 (Python by 橘子)
```python=
s = input()
n = len(s)
for st in range(n - 2):
if s[st:st + 3] == "AUG":
break
for i in range(st + 3, n - 2, 3):
if s[i:i + 3] in ("UAA", "UAG", "UGA"):
print((i - st) // 3)
break
```
```python!
print((lambda s:(lambda st:next((i - st) // 3 for i in range(st + 3, len(s) - 2, 3) if s[i:i + 3] in ("UAA", "UAG", "UGA")))(next(i for i in range(len(s)) if s[i:i + 3] == "AUG")))(input()))
```
## 巧克力 (Chocolate)
> 出題者：折蚌太郎
> 難度：p2
> 考點：迴圈、陣列
### Statement
有一位食品學教授正在研究巧克力，為了實驗方便，教授將一塊長度為 $N$、寬度為 $M$ 的巧克力劃分為 $N \times M$ 個小格子，就像一個二維陣列一樣，並定義每個格子的值代表舌頭接觸到該格裡的巧克力所品嘗到的味道 (從 $0$ 編號到 $R-1$ 共 $R$ 種味道)。
當巧克力吃進口中的時候，每個格子的味道不會乖乖地單獨被品嘗，而是會自然的與「周圍」融合在一起，形成那個格子的風味。如果某個格子的風味與它「周圍」的格子不同，則會讓巧克力吃起來很跳 tone。
因為味道跟風味仍然有一些小區別，所以教授專門發明了一套把味道轉換成風味值的公式，以 $C_{i,j}$ 表示位於長度 $i$、寬度 $j$ 處的味道編號，若該格的「周圍」總共有 $k$ 組相異的 $2$ 個格子 $(x,y)$，滿足 $x+y$ 後除以 $R$ 的餘數等於 $C_{i,j}$，則該格的風味值就會被加上 $k$。
因此為了避免吃到跳 tone 的巧克力，我們想知道整塊巧克力中，有**多少對**格子位在彼此「周圍」且具有相同的**風味**。對的總數稱為這塊巧克力的「均勻度」。
**注意，假如有兩個格子分別為 $x,y$，則 $(x,y)$ 跟 $(y,x)$ 屬於同一對，不能重複計算到。**
題目中提及的「周圍」，意思皆是指以該格為中心形成的 $3 \times 3$ 正方形中，除了自己以外的那 $8$ 格。一個格子的「周圍」僅限於巧克力內部，也就是說未必所有格子的「周圍」都有 $8$ 格。
### Input
第一行有 $3$ 個數字 $N, M, R\ (1 \le N \le 25, 1 \le M \le 35, \space 1 \le R \le N \times M)$
接下來有 $N$ 行，每行 $M$ 個數字
### Output
請輸出這塊巧克力的「均勻度」。
### Input Format
$N\ M\ R$
$C_{1,1} \space \space C_{1,2} \space \dots \space C_{1,M}$
$C_{2,1} \space \space C_{2,2} \space \dots \space C_{2,M}$
$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\vdots$
$C_{N,1} \space \space C_{N,2} \space \dots \space C_{N,M}$
### Output Format
$ans$
### Testcase
- Input 1
```
1 9 7
0 5 6 2 3 0 1 4 6
```
- Output 1
```
6
```
- Input 2
```
3 4 10
0 5 2 6
1 7 9 4
1 0 2 1
```
- Output 2
```
8
```
### Subtask
- Subtask 1 (50%) - $N=1$
- Subtask 2 (50%) - 無特殊限制
### Note
範例測資二說明：
首先把輸入的味道透過教授的公式轉換成風味，會得出下列這個陣列：
```
0 0 1 1
2 2 3 1
1 2 0 1
```
接著針對風味陣列計算均勻度，以下的表示法使用 `(x,y) -> z` 的形式，代表對於 $(x,y)$ 這一格，他的「周圍」有 $z$ 個格子的風味和他相同：
```
(1,1) -> 1
(1,2) -> 1
(1,3) -> 2
(1,4) -> 2
(2,1) -> 2
(2,2) -> 2
(2,3) -> 0
(2,4) -> 3
(3,1) -> 0
(3,2) -> 2
(3,3) -> 0
(3,4) -> 1
```
加總起來得到 $16$，因為不能重複計算到，所以要將結果除以 $2$，也就是 $8$。
### Solution
- Subtask 1
題目被簡化成一維陣列。會發現周圍最多只有 $2$ 格，直接算出風味值後儲存在一個新陣列中。再來對於每格的風味值，依題敘計算「均勻度」。最後輸出「均勻度」。
- Subtask 2
首先對於每格，用迴圈枚舉從它周圍 $8$ 格取出任兩格的所有組合，依題敘算出風味值後儲存在一個新陣列中。再來對於每格的風味值，用迴圈枚舉它周圍 $8$ 格，依題敘計算「均勻度」。最後輸出「均勻度」。
### Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n, m, r, ans;
const int N = 25, M = 35;
int choco[N + 1][M + 1], flavor[N + 1][M + 1];
bool inr(int i, int j) {
return 0 <= i && i < n &&
0 <= j && j < m;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> r;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> choco[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
vector<pair<int, int>> adj;
for (int ni = i - 1; ni <= i + 1; ni++)
for (int nj = j - 1; nj <= j + 1; nj++) {
if (!inr(ni, nj) || ni == i && nj == j) continue;
for (const auto &n2 : adj)
flavor[i][j] += (choco[ni][nj] + choco[n2.first][n2.second]) % r == choco[i][j];
adj.push_back({ni, nj});
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int ni = i - 1; ni <= i + 1; ni++)
for (int nj = j - 1; nj <= j + 1; nj++) {
if (!inr(ni, nj) || ni == i && nj == j) continue;
ans += flavor[i][j] == flavor[ni][nj];
}
cout << ans / 2 << '\n';
return 0;
}
```
## 礦坑 (Mine)
> 出題者：Chung
> 難度：p3
> 考點：貪心
### Statement
有一群人受困在礦坑中，大家為了優先讓老弱婦孺出去，希望能透過一些方法盡量讓老弱婦孺都排在對伍的前面。由於礦坑的坑道實在太窄，所以唯一能前進的方法就是跟前面的人擠一下 (互換位置)。
但是因為礦坑出口空間仍然有限，最多只能容納 $k$ 個人，所以也只能夠讓盡量多的老弱婦孺排到前面，但不保證所有的老弱婦孺都能到達出口。
因為無法確定礦坑會不會有進一步的崩塌，所以大家希望能夠越快越好，請問在所有能夠讓任意 $k$ 個老弱婦孺排在最前面的方案中，能夠達到的最小交換次數是多少？
定義老弱婦孺為：$65$ 歲(含)以上 or $12$ 歲(含)以下 or $35 \sim 45$ 歲女性
定義代號 F 為女性，M 為男性
### Input
輸入第一行將有兩個整數 $n,k \space (1 \leq n \leq 10^5, \space 0 \leq k \leq n)$，分別代表受困的人數和礦坑出口能夠容納的人數，**保證 $k \le$ 所有老弱婦孺的數量** 。
接下來有 $n$ 個 token 用空白隔開，每個 token 由兩個部分組成：(sex)(age)，分別代表性別與年齡。$(sex \in \{F,M\}, 0 \leq age \leq 100)$
### Output
請輸出一個整數 $ans$ 代表能夠讓任意 $k$ 個老弱婦孺都排在最前面的最小交換次數。
### Input Format
$n \space k$
$token_1 \space token_2 \space \dots \space token_n$
### Output Format
$ans$
### Testcase
- Input 1
```
3 1
F30 M70 M70
```
- Output 1
```
1
```
- Input 2
```
5 1
F40 M40 M40 F40 M40
```
- Output 2
```
0
```
### Subtask
- Subtask 1 (30%) - $n \leq 1000$
- Subtask 2 (70%) - 無其他限制
### Note
### Solution
- Subtask 1
先把輸入轉換成，符合前 $k$ 個老弱婦孺的為 O，不符合的為 X。
```
7 3
M30 F30 M65 M30 F50 F38 M12
```
以上面這個測資為例，我們可以先把序列轉換成 XXOXXOO，這樣就把題目變成，讓 O 全部都跑到最前面所需要的最小交換次數，顯然，越接近左邊的 O 推到盡量左邊 (移動到從左到右第一個 X 的位置) 一定是好的。
證明：會有可能增加交換次數的情況只有發生在當某個 O 在移動時被交換到後面，但因為在移動過程中保證不會讓某些 O 被推到後面，所以從左到右的策略不會影響到 O，只會一直將 X 往後推。
因此策略就是，先把第 $3$ 個位置的 O 移動到第 $1$ 個位置，變成 OXXXXOO，再把第 $6$ 個位置的 O 移動到第 $2$ 個位置，變成 OOXXXXO，最後把第 $7$ 個位置的 O 移動到第 $3$ 個位置，變成 OOOXXXX，即是最少的交換次數 $= 10$。
- Subtask 2
在用上面這個做法交換時可以觀察到，一個O要移到最前面所需的交換次數取決於它前面有多少X，而在做交換時不會影響更後面的O前面到隊伍開頭為止有多少X，所以只要計算每個O前面各有幾個X就可以了
### Code
- Subtask 1 (Python by 橘子)
```python=
n, k = map(int, input().split())
ans = 0
cnt = 0
status = input().split()
outs = []
for i in range(n):
s = status[i]
sex = s[0]
age = int(s[1:])
ok = (age <= 12 or age >= 65 or (sex == "F" and 35 <= age <= 45))
outs.append(ok)
ans = 0
for i in range(k):
for j in range(i,n):
if outs[j]:
break
if outs[j]:
if j>i:
outs[j] = False
outs[i] = True
ans += j-i
else:
break
print(ans)
```
- Subtask 2
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
//declare
const int maxn = 2e5+5;
int n,k;
bool ispriority[maxn];
//
signed main(){
cin>>n>>k;
for(int i=0;i<n;i++){
char c; int x; cin>>c>>x;
if((x >= 65) || (x <= 12) || (c == 'F' && 35 <= x && x <= 45)){
if(--k<0) continue;
ispriority[i] = 1;
}
}
int idx = 0, ans = 0;
for(int i=0;i<n;i++){
if(ispriority[i]){
ans += (i - idx);
idx++;
}
}
cout<<ans<<"\n";
return 0;
}
```
- Subtask 2 (Python by 橘子)
```python=
n,k = map(int,input().split())
def check(s):
sex = s[0]
age = int(s[1:])
return age<=12 or age>=65 or sex=="F" and 35<=age<=45
a = input().split()
b = [i for i in range(n) if check(a[i])][:k]
print(sum(b[i]-i for i in range(k)))
```
```python!
print((lambda n,k,a:sum([i for i in range(n) if int(a[i][1:])<=12 or int(a[i][1:])>=65 or a[i][0]=="F" and 35<=int(a[i][1:])<=45][:k])-k*(k-1)//2)(*map(int,input().split()),input().split()))
```
## 調酒專家 (Mixologist)
> 出題者：rickytsung
> 難度：p4
> 考點：DP
### Statement
小石頭的學校附近有一個酒吧。有一天，小石頭和他同學去那間酒吧約打牌，裡面有個調酒師叫做謝一。
小石頭他們打完牌後，因為小石頭打輸了，根據他們先前的規定小石頭必須接受懲罰，懲罰的內容是喝謝一的神奇調酒，因為他不能喝太多酒精飲料，他需要喝一杯不超過 $n$ 毫升的調酒，而這個酒吧裡面有 $m$ 種完全不同的酒，這些酒分別有 $a_1, a_2, a_3, ..., a_m$ 毫升，對於各種酒謝一可以選擇加任何整數毫升的酒進到一個量杯中(當然也可以不加)，然後最後把它搖一搖混合做成調酒，已知加的順序不會影響調出來的成品，不同酒之間的體積也具有加成性，現在小石頭想到一個問題，對於所有正整數 $k$ 滿足 $1 \leq k \leq n$， 他想知道總共可以調出幾種不同的 $k$ 毫升的調酒，因為答案可能會很大，請你把這個數取模 $998244353$。
註 :「 求一個整數 $X$ 模一個正整數 $Y$」代表求 「$X$ 除以 $Y$ 的餘數」，如 $5$ 模 $3 = 2$、$6$ 模 $3 = 0$、$7$ 模 $3 = 1$。在實作方面，若保證 $X$ 必為非負整數，可以用 $X\ \%\ Y$ 達成這個運算，但若 $X$ 有可能出現負數的話，請務必使用 $(X + Y)\ \%\ Y$。
### Input
輸入第一行有兩個正整數代表 $n, m$，接著有一行 $m$ 個正整數代表各種酒的量，第 $i\ (1 \leq i \leq m)$ 個數代表第 $i$ 種酒類有 $a_i\ (1 \leq a_i \leq n)$ 毫升。
### Output
輸出一行 $n$ 個數後換行，中間以空白隔開，第 $i\ (1 \leq i \leq n)$ 個數代表剛好為 $i$ 毫升的調酒的種類數模 $998244353$。
### Input Format
$N$
$a_1 \space a_2 \space \dots \space a_m$
### Output Format
$ans_1 \space\space ans_2 \space\space ans_3 \space\dots\space ans_n$
### Testcase
- Input 1
```
6 3
1 1 3
```
- Output 1
```
3 4 4 3 1 0
```
- Input 2
```
10 8
3 1 4 1 5 9 2 6
```
- Output 2
```
8 34 103 250 517 945 1563 2377 3363 4466
```
### Subtask
- Subtask 1 (50%) - $n, m \leq 100$
- Subtask 2 (50%) - $n, m \leq 2000$
### Note
對於範例測試 1，我們討論各毫升數調酒的種類數，為了方便說明，我們以數對 $(b_1, b_2, b_3)$ 表示第 $i\ (i = 1,2,3)$ 種酒最後加入的量為 $b_i$ 毫升，例如 : $(b_1, b_2, b_3) = (1,0,2)$ 代表第 $1$ 種酒加了 $1$ 毫升、第 $2$ 種酒加了 $0$ 毫升、第 $3$ 種酒加了 $2$ 毫升。
所有 $1$ 毫升的調酒可以由下列方法製成 :
$(b_1, b_2, b_3) = (0,0,1), (0,1,0), (1,0,0)$ 共 $3$ 種。
所有 $2$ 毫升的調酒可以由下列方法製成 :
$(b_1, b_2, b_3) = (0,0,2), (0,1,1), (1,0,1), (1,1,0)$ 共 $4$ 種。
所有 $3$ 毫升的調酒可以由下列方法製成 :
$(b_1, b_2, b_3) = (0,0,3), (0,1,2), (1,0,2), (1,1,1)$ 共 $4$ 種。
所有 $4$ 毫升的調酒可以由下列方法製成 :
$(b_1, b_2, b_3) = (0,1,3), (1,0,3), (1,1,2)$ 共 $3$ 種。
所有 $5$ 毫升的調酒可以由下列方法製成 :
$(b_1, b_2, b_3) = (1,1,3)$ 共 $1$ 種。
而因為調酒的總量 $a_1 + a_2 + a_3$ 只有 $5$ 毫升，所以調不出 $6$ 毫升以上的調酒，因此 $6$ 毫升以上的調酒種類數為 $0$ 。
最後其實聽說謝一的調酒蠻好喝的，只是小石頭沒喝幾杯就醉了，這個小石頭真的是太遜了。
### Solution
#### Subtask 1
因為題目說酒的添加順序沒有關聯，於是我們可以從第 $1$ 種酒照順序開始拿，可以定義 $dp_{i,j} = k$ 代表目前拿到第 $i$ 瓶酒、目前調酒杯裡有 $j$ 毫升，而要達到這個狀態的方法數為 $k$ 種，則 $dp_{m,n}$ 就是所求答案。
那 $dp$ 表格怎麼求呢 ? 先假設初始狀態 $dp_{0,0} = 1$，而第 $i$ 種酒裡面有 $a_i$ 毫升，然後我們可以列以下轉移式 :
$dp_{i,j} = dp_{i-1, j-a_i} + dp_{i-1, j-a_i+1} + dp_{i-1, j-a_i + 2} + \dots + dp_{i-1,j}$
對於一格如果直接實作可以以 $O(n)$ 的時間複雜度轉移，總共有 $mn$ 格，所以時間複雜度是 $O(n^2 \cdot m)$，可以通過 Subtask 1。
#### Subtask 2
上面提到的直接實作，時間複雜度在這會來到 $10^9$ ，沒辦法通過這個 Subtask，我們可以試著讓轉移速度變更快 ! 如果我們把 $dp_{i,j}$ 和 $dp_{i,j+1}$ 寫出來，那寫出來是這樣(假設 $dp_{i,j}$ 和 $dp_{i,j+1}$ 的轉移都是完整的) :
$dp_{i,j} = dp_{i-1, j-a_i} + (dp_{i-1, j-a_i+1} + dp_{i-1, j-a_i + 2} + \dots + dp_{i-1,j-1}+ dp_{i-1,j})$
$dp_{i,j+1} = (dp_{i-1, j-a_i+1} + dp_{i-1, j-a_i+2} + \dots + dp_{i-1,j-1}+ dp_{i-1,j}) + dp_{i-1,j+1}$
會發現其實這兩個很相似，括號裡的東西是完全一樣的，也就是只差在 $dp_{i-1, j-a_i}$ 和 $dp_{i-1,j+1}$，所以我們只要「加/減」這兩個東西就可以轉移，轉移時間可以變成 $O(1)$，這個 trick 叫做 sliding window。
#### 實作細節
1. 這裡因為答案可能很大需要求 $998244353$ 的餘數，所以每次運算後如果會超過就要記得取模以免數字變太大，另外雖然取模後會落在 $0 \sim 998244352$ 以內，但數之間在運算中間可能會超過 32 bit integer，用 64 bit 型別比較保險。
2. 針對上述的 Subtask 2 解法，要注意的要減去 $dp_{i-1, j-a_i}$ 的時候要注意它是不是不存在，也就是符不符合上述說的轉移是完整的 (可以參考下面的實作)，另外注意如果使用的不是 mint (modint) 的話，取模後的數相減後的可能是負數，後面要記得補加一個 mod 回去。
### Code
- Subtask 1
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define Chiikawa ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define ll long long int
const int maxn = 1e2+5, mod = 998244353;
ll dp[maxn][maxn];
int cap[maxn];
int main(){
Chiikawa;
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> cap[i];
}
dp[0][0] = 1;
for(int i = 1; i <= m; i++){
for(int j = 0;j <= n; j++){
for(int k = max(0, j - cap[i]); k <= j; k++){
dp[i][j] += dp[i-1][k];
dp[i][j] %= mod;
}
}
}
cout << dp[m][1];
for(int i = 2; i <= n; i++){
cout << " " << dp[m][i];
}
cout << '\n';
return 0;
}
```
- Subtask 2
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define Chiikawa ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define ll long long int
const int maxn = 2e3+5, mod = 998244353;
ll dp[maxn][maxn];
int cap[maxn];
int main(){
Chiikawa;
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> cap[i];
}
dp[0][0] = 1;
for(int i = 1; i <= m; i++){
ll now = 0;
for(int j = 0; j <= n; j++){
now = (now + dp[i-1][j]) % mod;
if(j - cap[i] - 1 >= 0){
now = (now - dp[i-1][j - cap[i] - 1] + mod) % mod;
}
dp[i][j] = (dp[i][j] + now) % mod;
}
}
cout << dp[m][1];
for(int i = 2; i <= n; i++){
cout << " " << dp[m][i];
}
cout << '\n';
return 0;
}
```
- Subtask 2 (Python by 橘子) (Judge更新後不確定有沒有問題)
```python=
mod = 998244353
n, m = map(int, input().split())
a = list(map(int, input().split()))
dp = [1] + [0] * n
dp0 = [0] * (n + 2)
for i in range(n + 1):
dp0[i + 1] = dp[i] + dp0[i]
for x in a:
for j in range(n, -1, -1):
dp[j] = (dp0[j + 1] - dp0[max(0, j - x)]) % mod
for i in range(n + 1):
dp0[i + 1] = dp[i] + dp0[i]
print(*dp[1:])
```
```python!
print(*(lambda n,m,a,mod:(lambda dp,dp0:sum(sum(dp.__setitem__(j,(dp0[j+1]-dp0[max(0,j-x)])%mod) or 0 for j in range(n,-1,-1)) or sum(dp0.__setitem__(i+1,dp[i]+dp0[i]) or 0 for i in range(n+1)) for x in a) or dp[1:])([1]+[0]*n,[0]+[1]*(n+1)))(*map(int,input().split()),list(map(int,input().split())),998244353))
```
### Extreme Version
首先，照原題目的 $O(NM)$ 做法肯定是爛的，我們可以往另個方向想:
我們令 $F_{a_i}(x) = \sum\limits_{j=0}^{a_i} x^j = 1+x+x^2+...+x^{a_i}$
如 $F_3(x) = 1+x+x^2+x^3$
$F_{a_i}(x)$ 也就是一個 deg 為 $a_i$、全部係數為 $1$ 的 $x$ 的多項式。
令多項式 $G(x) = \prod\limits_{i=1}^{m} F_{a_i}(x) = F_{a_1}(x) \cdot F_{a_2}(x) \dots F_{a_m}(x)$
也就是把題目給的 $a_i$ 所形成的 $F_{a_i}(x)$ 全部乘起來(也會是 $x$ 的多項式)。
那其實 $[x^k]G(x)$ ，也就是 $G(x)$ 的 $x^k$ 項係數就會是 $k$ 毫升調酒的種類數。
這個原理是當作每一個 $F_{a_i}(x)$ 代表有選 $0,1, ... ,a_i$ 毫升的選擇，那麼我們注意到兩個 $F(x)$ 相乘，就會等於這兩種調酒所有選擇產生的結果，次方項代表最後的總量、對應係數代表種類數(方法數)，滿足結合律。
如果我們直接做，考慮到兩個 $n$ 項多項式用國中的方法相乘是 $O(n^2)$ 的，這個東西的時間複雜度會是 $O(n^2 \cdot m)$，這看起來比 dp 還糟糕，但是我們可以優化它!
1. FFT/NTT 做乘法運算
FFT 允許我們以 $O(nlogn)$ 的時間，求出兩個 $n$ 項多項式的乘積，簡單講是我們可以用 DFT 求出這兩個多項式的點值，然後將它們的點值相乘後，再使用 IDFT 轉換回去成多項式，而 FFT 允許我們把這個操作搬到複數平面，本來的 DFT 是 $O(n^2)$ 的，但因為複數平面環的特殊性質，所以可以利用分治降到 $O(nlogn)$。
[例題. CSES-Apples and Bananas](https://cses.fi/problemset/task/2111)
[ZJ 上搬運的版本 比較不會卡常](https://zerojudge.tw/ShowProblem?problemid=h386)
NTT 是把操作搬到模上面，模跟複數平面有環的特殊性質，不過要在特定的模才能用，如果是 $998244353$ 就很好做，假設如果是 $1000000007$ 的話或是像上面的例題值比較大，就需要用多個模做 MTT，也是可以算，只是就很麻煩，常數會比較大。NTT 和 FFT 一樣是 $O(nlogn)$，不過不會卡精度。
2. ln/exp 運算
如果我們今天有個 $n$ 次多項式 $F(x)$，我們要求它的 $F^k(x)\space mod\space x^n$，根據上面的 FFT/NTT 可以用 $O(knlogn)$ 求出，我們當然可以用快速冪壓成 $O(nlognlogk)$，但有時候 $k$ 真的很大、又或著 FFT/NTT 肥肥的常數使得你被卡常，我們有沒有辦法把 $logk$ 壓掉呢?
其實是可以的，我們可以用 $ln, exp$ 運算，假設我們要算的是 $F^k(x)$，那我們可以變成 $e^{ln(F(x)^k)}$ = $e^{k \cdot ln(F(x))}$ (這裡都有取模 $x^n$)。
所以先把多項式取 $ln$ 然後對它乘 $k$ 再 exp 回來，就可以壓到 $O(nlogn)$。
[例題. ZJ-線上外賣學習](https://zerojudge.tw/ShowProblem?problemid=h999)
回到原題，為了後面的說明，我們把題目改成如下 :
這個酒吧裡面 $i\ (1\sim n)$ 毫升的酒有 $b_i$ 種，對於各種酒可以加任何整數毫升的酒進到一個量杯中，請問可以調出幾種不同的 $k$ 毫升的調酒，模 $998244353$。
我們把原題目的 $a_i$ 轉成 $b_i$。
這題的答案會是 $G(x) = \prod\limits_{i=1}^{n} F^{b_i}_{i}(x)$
$= e^{ln(\prod\limits_{i=1}^{n} (F^{b_i}_{i}(x)))}$
$= e^{\sum\limits_{i=1}^{n} ln(F^{b_i}_{i}(x))}$
$= e^{\sum\limits_{i=1}^{n} b_i \cdot ln(F_{i}(x))}$
而其中的 $F_{i}(x)$ 我們求其封閉形式
$F_{i}(x) = \sum\limits_{j=0}^{i} x^j = \frac{1-x^{i+1}}{1-x}$
而 $ln(F_{i}(x))$ 的 Maclaurin series 展開:
而因為第 $i$ 項會影響到的係數有 $n/i$ 個，總共影響到的係數數量是個調和級數，總共為 $\sum\limits_{i=1}^{n} n/i = nlnn$ 個，也就是 $O(nlnn)$ 求出取 $ln$ 的陣列，接著以 $O(nlogn)$ 求 $exp$ 回來就可以得到我們要的多項式了！
* Extreme version Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define Chisato_Takina ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int maxn = 262144; //NTT uses 2x upperbound
const int mod = 998244353;
// fps template by oi wiki
using i64 = long long;
using poly_t = int[maxn];
using poly = int *const;
int inv[maxn], rev[maxn];
int qpow(int x, int y) {
int res(1);
while (y) {
if (y & 1) res = 1ll * res * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return res;
}
void NTT(int *x, int lim, int opt) {
int i, j, k, m, gn, g, tmp;
for (i = 0; i < lim; ++i) rev[i] = (i & 1) * (lim >> 1) + (rev[i >> 1] >> 1);
for (i = 0; i < lim; ++i)
if (rev[i] < i) swap(x[i], x[rev[i]]);
for (m = 2; m <= lim; m <<= 1) {
k = m >> 1;
gn = qpow(3, (mod - 1) / m);
for (i = 0; i < lim; i += m) {
g = 1;
for (j = 0; j < k; ++j, g = 1ll * g * gn % mod) {
tmp = 1ll * x[i + j + k] * g % mod;
x[i + j + k] = (x[i + j] - tmp + mod) % mod;
x[i + j] = (x[i + j] + tmp) % mod;
}
}
}
if (opt == -1) {
reverse(x + 1, x + lim);
int inv = qpow(lim, mod - 2);
for (i = 0; i < lim; ++i) x[i] = 1ll * x[i] * inv % mod;
}
}
void derivative(const poly &h, const int n, poly &f) {
for (int i = 1; i != n; ++i) f[i - 1] = (i64)h[i] * i % mod;
f[n - 1] = 0;
}
void integrate(const poly &h, const int n, poly &f) {
for (int i = n - 1; i; --i) f[i] = (i64)h[i - 1] * inv[i] % mod;
f[0] = 0; /* C */
}
void polyinv(const poly &h, const int n, poly &f) {
/* f = 1 / h = f_0 (2 - f_0 h) */
static poly_t inv_t;
std::fill(f, f + n + n, 0);
f[0] = qpow(h[0], mod - 2);
for (int t = 2; t <= n; t <<= 1) {
const int t2 = t << 1;
std::copy(h, h + t, inv_t);
std::fill(inv_t + t, inv_t + t2, 0);
NTT(f, t2, 1);
NTT(inv_t, t2, 1);
for (int i = 0; i != t2; ++i)
f[i] = (i64)f[i] * ((2 + mod - ((i64)f[i] * inv_t[i] % mod)) % mod) % mod;
NTT(f, t2, -1);
std::fill(f + t, f + t2, 0);
}
}
void polyln(const poly &h, const int n, poly &f) {
/* f = ln h = ∫ h' / h dx */
assert(h[0] == 1);
static poly_t ln_t;
const int t = n << 1;
derivative(h, n, ln_t);
std::fill(ln_t + n, ln_t + t, 0);
polyinv(h, n, f);
NTT(ln_t, t, 1);
NTT(f, t, 1);
for (int i = 0; i != t; ++i) ln_t[i] = (i64)ln_t[i] * f[i] % mod;
NTT(ln_t, t, -1);
integrate(ln_t, n, f);
}
void polyexp(const poly &h, const int n, poly &f) {
/* f = exp(h) = f_0 (1 - ln f_0 + h) */
assert(h[0] == 0);
static poly_t exp_t;
std::fill(f, f + n + n, 0);
f[0] = 1;
for (int t = 2; t <= n; t <<= 1) {
const int t2 = t << 1;
polyln(f, t, exp_t);
exp_t[0] = (mod + ((h[0] + 1) % mod) - exp_t[0]) % mod;
for (int i = 1; i != t; ++i) exp_t[i] = (mod + h[i] - exp_t[i]) % mod;
std::fill(exp_t + t, exp_t + t2, 0);
NTT(f, t2, 1);
NTT(exp_t, t2, 1);
for (int i = 0; i != t2; ++i) f[i] = (i64)f[i] * exp_t[i] % mod;
NTT(f, t2, -1);
std::fill(f + t, f + t2, 0);
}
}
// Solution start here
int main() {
Chisato_Takina;
int n, m, sakana;
int lim = 1;
static poly_t a, b;
int arr[maxn];
for (int i = 0; i < maxn; ++i) inv[i] = qpow(i, mod - 2); //init
cin >> n >> m;
for(int i = 1; i <= m; i++){;
cin >> sakana;
arr[sakana + 1] ++;
}
while(lim <= n) lim <<= 1;
for(int i = 1; i < lim; i++){
a[i] = (a[i] + 1ll * inv[i] * m) % mod;
for(int j = 1, k = i; k < lim ; j += 1, k += i){
a[k] = (a[k] + mod - 1ll * inv[j] * arr[i]) % mod;
}
}
polyexp(a, lim, b);
for(int i = 1; i <= n; i++){
cout << b[i] << ' ';
}
return 0;
}
```
Sign in with Wallet
Connect another wallet