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

🔗 🟡 P14360 [CSP-J 2025] 多边形

Problem Statement

題目簡述

給定 $n$ 根木棍的長度 $a_1, \dots, a_n$ ，求有多少種選擇木棍的方案（以下標集合區分），使得選出的木棍能拼成一個多邊形。能拼成多邊形的條件：選出至少 $3$ 根木棍，且所有木棍的長度和大於最大長度的兩倍。

Constraints

約束條件

$3 \leq n \leq 5\,000$
$1 \leq a_i \leq 5\,000$
答案對 $998\,244\,353$ 取模

思路：排序 + 背包 DP + 正難則反

固定最大值，轉化多邊形條件

由於多邊形條件只與木棍長度有關，與原本順序無關，對於這種順序無關的子集計數問題，常見的做法是先排序，再按照大小枚舉。

由於多邊形條件 $\sum > 2 \max$ ，最大值的選擇會決定整個集合的合法性。也就是說，若固定某個木棍為最大值，則只要檢查其餘木棍的和是否大於這個最大值，就能判斷整個集合是否合法。

因此可以排序後，再從小到大枚舉集合中的最大值 $a_i$ 。

關鍵觀察

排序後，若固定 $a_i$ 作為最大值，則它一定被選入集合。此時多邊形條件 $\sum > 2 \max$ 可以改寫成「其餘木棍長度和大於 $a_i$ 」。

S_{\text{rest}} + a_i > 2a_i \;\Longleftrightarrow\; S_{\text{rest}} > a_i

其中 $S_{\text{rest}}$ 為其餘所選木棍的長度和。

問題轉化

於是問題變成：在 $a_1 \sim a_{i-1}$ 中選若至少 $2$ 根，使它們的和大於 $a_i$ 。

由於選 $0$ 根或 $1$ 根的和必然不超過 $a_i$ ，會自然落入不合法方案，因此不需要考慮「至少選 $2$ 根」的限制，直接計算所有子集的和即可。

背包計數，正難則反

接著考慮如何計數。不等式較難直接處理，常見作法是轉換成等式後累加。但由於不等式是「和大於 $a_i$ 」，若直接處理「和大於 $a_i$ 」，和值上界會到 $\sum a_i$ ，狀態數過多。

更方便的做法是用背包 DP 記錄「和恰好為 $j$ 」的方案數，再反過來扣掉不合法方案。

令 $f[i][j]$ 表示只考慮前 $i$ 根木棍，選若干根後長度和恰好為 $j$ 的方案數。

正難則反

固定最大值 $a_i$ 時，前 $i-1$ 根木棍的任意子集共有 $2^{i-1}$ 種。只要減去和小於等於 $a_i$ 的不合法方案，即可得到合法方案數：

\text{ans} \mathrel{+}= 2^{i-1} - \sum_{j=0}^{a_i} f[i-1][j]

由於 $a_i \le 5000$ ，只需要維護 $0 \sim \max a_i$ 的和值，狀態規模從 $O(\sum a_i)$ 壓到 $O(\max a_i)$ 。

統計完以 $a_i$ 為最大值的方案後，再把 $a_i$ 加入背包，供後續更大的最大值使用。完整轉移為：

f[i][j] = f[i-1][j] + f[i-1][j-a_i]

初始 $f[0][0] = 1$ ，表示什麼都不選的空集。

注意到第 $i$ 層只會用到第 $i-1$ 層，因此可以把第一維滾動掉，改成一維陣列。此時更新要倒序，避免同一根木棍被重複選：

f[j] \leftarrow f[j] + f[j - a_i] \quad (\text{倒序})

滾動後初始狀態對應為 $f[0] = 1$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot \max a_i)$
空間複雜度： $\mathcal{O}(\max a_i)$

Code

MOD = 998244353


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

    mx = A[-1]  # 最大值，決定 DP 陣列大小
    f = [1] + [0] * mx  # f[j] = 和恰好為 j 的子集數
    ans = 0
    for i, x in enumerate(A, start=1):
        if i >= 3:  # 至少需要 3 根木棍
            ans += 1 << (i - 1)  # 前 i-1 根的所有子集
            ans %= MOD
            for j in range(x + 1):  # 減去其餘和 ≤ x 的不合法方案
                ans -= f[j]
                ans %= MOD
        for j in range(mx, x - 1, -1):  # 0/1 背包，倒序更新
            f[j] += f[j - x]
            f[j] %= MOD
    print(ans)


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @4AUB. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.