## 調酒專家 (Mixologist)
題目 : https://apcs-simulation.com/problem/apcs0304-ex
### 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} + dp_{i-1, j-a_i+3} + \dots + 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 = 1e3+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;
}
```
### Bounus
**Bonus : 最後，有興趣的可以挑戰這題的 Extreme version ，雖然這應該超出 apcs 命題範圍很遠了。題目敘述不變，唯一改變的是 $n, m$ 的上限來到 $10^5$，那請問怎麼做呢**？
### 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 (這裡的 FFT 指的是 FDFT，快的離散傅立葉轉換, DFT) 允許我們以 $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 是把前面 FFT 的操作搬到「模一個數」的有限體上面，也有環的特殊性質，不過要在特定的模才能用，如果是 $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(1-x^k)$ ($k$ 為正整數) 的 Maclaurin series 展開:
$ln(1-x^k) = -\sum_{i=1}^{\infty} \frac{x^{ki}}{i}$
我們只要求 $n$ 以內的。
而因為 $k = i$ 會影響到的係數有 $n/i$ 個，總共影響到的係數數量是個調和級數，總共為 $\sum\limits_{i=1}^{n} n/i = n\ ln\ n$ 個，也就是 $O(n\ ln\ n)$ 求出取 $ln$ 的陣列，接著以 $O(n\ log\ n)$ 求 $exp$ 回來就可以得到我們要的多項式了！
### Code
* Extreme version
```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