思路与算法

排序后把每个非空集合唯一归给其最后一个最大下标。维护之前元素子集和不超过最大边长的计数；当前最大边v可形成多边形的方案=全部旧子集数减去和<=v的旧子集数。

正确性说明

选定最大边v后，多边形条件变成其余边之和>v；因其余各边<=v且均为正，符合此条件的集合自动至少有两条边。旧子集01背包恰计所有下标组合，按最后下标归类使即使有等长边也无重复。

复杂度

O(nA+n log n)时间、O(A+n)空间，A=max(a)<=5000；含DP清零、排序与所有前缀计数。

易错点

条件是严格大于，不可把和等于最大边算入；背包倒序更新，每根木棍只使用一次。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    const int P = 998244353;
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &v : a)
        cin >> v;
    sort(a.begin(), a.end());
    int A = a.back();
    vector<int> dp(A + 1);
    dp[0] = 1;
    long long total = 1, ans = 0;
    for (int v : a) {
        long long bad = 0;
        for (int j = 0; j <= v; j++)
            bad += dp[j];
        ans = (ans + total - bad) % P;
        if (ans < 0)
            ans += P;
        for (int j = A; j >= v; j--)
            dp[j] = (dp[j] + dp[j - v]) % P;
        total = 2 * total % P;
    }
    cout << ans << "\n";
}