題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC436G Linear Inequation

tags: `動態規劃(Dynamic Programming)` `數位DP(DigitDP)` `背包問題(KnapsackProblem)` `數學(Math)`

Problem Statement

題目簡述

給定長度為 $N$ 的正整數序列 $A=(A_1, \dots, A_N)$ 和一個正整數 $M$ 。
求滿足以下條件的非負整數序列 $x=(x_1, \dots, x_N)$ 的個數：

\sum_{i=1}^N A_i x_i \le M

答案對 $998244353$ 取模。

Constraints

約束條件

$1 \le N \le 100$
$1 \le A_i \le 100$
$1 \le M \le 10^{18}$

思路：二進位拆分 + 0/1 背包

這道題目的難點在於 $M$ 高達 $10^{18}$ ，直接使用背包問題（完全背包）的時間複雜度為 $\mathcal{O}(N \cdot M)$ ，無法接受。然而 $N$ 和 $A_i$ 都很小，這提示我們可以從 $A_i$ 的總和或數位 DP 的角度入手。

1. 從完全背包到多重背包的思考

原問題等價於求有多少種非負整數解。如果 $M$ 較小，這是一個標準的完全背包問題（每個物品 $A_i$ 可以被選無限次）。
完全背包可以視為一種特殊的多重背包，其中每種物品的數量上限為 $\lfloor \frac{M}{A_i} \rfloor$ 。
對於多重背包，一個經典的優化手段是二進位拆分。

2. 變數的二進位拆分

我們可以將每個未知數 $x_i$ 拆解成二進位形式：

x_i = \sum_{k=0}^{60} b_{i,k} \cdot 2^k, \quad b_{i,k} \in \{0, 1\}

將其代入原不等式：

\sum_{i=1}^N A_i \left( \sum_{k=0}^{60} b_{i,k} 2^k \right) \le M

3. 交換求和順序與 0/1 背包

交換求和順序，按 $2$ 的冪次（位數 $k$ ）分組：

\sum_{k=0}^{60} 2^k \underbrace{\left( \sum_{i=1}^N A_i b_{i,k} \right)}_{S_k} \le M

觀察括號內的 $S_k = \sum_{i=1}^N A_i b_{i,k}$ ：

對於固定的層級 $k$ ，我們需要決定每個 $x_i$ 在這一位是 0 還是 1。
每個 $A_i$ 在這一層只能被選一次（ $b_{i,k}=1$ ）或不選（ $b_{i,k}=0$ ）。
這正是一個標準的 0/1 背包問題。

因此，問題轉化為：我們從低位到高位逐層處理，每一層做一次 0/1 背包。

4. 層間的狀態傳遞與壓縮

僅僅做背包是不夠的，我們還需要滿足總和 $\le M$ 的限制。這可以通過類似「數位 DP」的進位思想來處理。

我們從低位（ $2^0$ ）開始處理。設 $dp[j]$ 表示在處理完當前層級的背包後，累積的數值（包含從更低位傳上來的進位以及當前層的選擇）為 $j$ 的方案數。

狀態定義：

$dp[j]$ ：當前層級累積數值為 $j$ 的方案數。

狀態轉移（背包階段）：

在每一層 $k$ ，我們先進行一次 0/1 背包：

dp[j] \leftarrow \sum dp[j - A_i]

這代表我們決定了當前層 $x_i$ 的取值。

狀態壓縮（進位階段）：

這是本題最關鍵的一步。假設當前層累積了數值 $j$ ，而 $M$ 在當前位的值為 $d = (M \gg k) \& 1$ 。

為了滿足不等式限制，當前層的數值 $j$ 扣除 $M$ 提供的額度 $d$ 後，剩餘的部分必須由更高位來承擔。
由於更高位的權重是當前位的 2 倍（ $2^{k+1} = 2 \cdot 2^k$ ），因此傳遞給下一層的數值 $j_{next}$ 滿足：

j \le d + 2 \cdot j_{next}

移項得：

2 \cdot j_{next} \ge j - d \implies j_{next} = \left\lceil \frac{j - d}{2} \right\rceil

為什麼需要壓縮？

如果不進行壓縮，隨著層數上升， $j$ 的範圍會越來越大。但通過除以 2 的操作，我們將狀態空間始終控制在 $\sum A_i + \frac{1}{2} \sum A_i + \frac{1}{4} \sum A_i + \cdots = 2 \sum A_i$ 的範圍內（大約 20000 左右），從而保證了複雜度。

5. 總結算法流程

初始化 $dp[0] = 1$ ，其餘為 0。
對於 $M$ $M$ 的每一個位元（從低到高）：
- 背包：遍歷每個物品 $A_i$ ，更新 $dp$ 陣列（0/1 背包）。
- 壓縮：根據 $M$ 當前位 $d$ ，計算新狀態 $j_{next} = \lceil \frac{j-d}{2} \rceil$ ，將 $dp[j]$ 累加到 $dp_{next}[j_{next}]$ 。
- 更新： $dp \leftarrow dp_{next}$ ，並將 $M$ 右移一位。
最終 $dp[0]$ 即為答案（表示所有位數處理完後，沒有溢出且滿足條件的方案數）。

參考資料

參考來源

Code

MOD = 998244353

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == N

    # S + 1/2S + 1/4S + ... = 2S
    # 狀態空間上限大約是 sum(A) 的兩倍
    MAX_W = sum(A) * 2
    
    f = [0] * (MAX_W + 1)
    f[0] = 1

    # 逐位處理
    while M > 0:
        # 1. 0/1 背包階段：決定當前位每個 x_i 是否為 1
        for x in A:
            for j in range(MAX_W, x - 1, -1):
                f[j] = (f[j] + f[j - x]) % MOD

        # 2. 壓縮階段：計算進位並壓縮狀態
        nf = [0] * (MAX_W + 1)
        d = M & 1
        for j in range(MAX_W + 1):
            # 根據不等式 j <= d + 2 * nj 推導出 nj = ceil((j - d) / 2)
            nj = (j - d + 1) >> 1
            nf[nj] = (nf[nj] + f[j]) % MOD

        f = nf
        M >>= 1
    print(f[0])

if __name__ == '__main__':
    solve()