多边形 (CSP-J 2025)

首先，潜在方案数一共 $2^n$ ，而 $n \leq 5000$ , $a[i] \leq 5000$ ，所以枚举肯定是不行的。我们应该寻找 $\mathcal{O}(n^2)$ 或者 $\mathcal{O}(n^2\log n)$ 的算法。

我们把 $a[i]$ 从小到大排序，应该会让问题方便一些。

然后，观察条件 $\sum{l[i]} > 2\cdot\max{l[i]}$ ，一个角度是我们固定住最大的 $l[i]$ ，计算所有以 $i$ 为最长木棍的方案中，不符合要求的方案数量，也就是：

$dp[i]$ = 木棍之和小于等于 $l[i]$ 的方案总数

我们可以证明，这就是所有以 $i$ 为最长木棍，且不可行的方案的数量，全部不可行的方案加起来，再用 $2^n$ 减去就是答案。

怎么计算 $dp[i]$ 呢？因为 $a[i] < 5000$ ，所以我们只需要计算 $dp[0]..dp[5000]$ :

$dp[i] = \sum(dp[i-a[j]])$ , $j = 1..n$ , $a[j] \leq i$

注意这个题没有说木棍的长度是互不相同的，所以在统计总方案数的时候，需要处理相同长度木棍的情况。下面代码中cnt[]就是用来保证重复数字的不合法情况只被计算一次。

另外一个基础知识是模运算，需要会做模的加法和减法，减法之前需要记得加模数，防止出现负数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int a[5005];
int dp[5005];
int dp2[5005];
int cnt[5005];
const int MOD = 998244353;
int ans;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a+n);
    for (int i = 0; i <= 5000; i++) dp[i] = 1;      // empty set for all lengths
    for (int j = 0; j < n; j++) {                   // all sticks
        memcpy(dp2, dp, sizeof(dp));                // not including l[j]
        for (int i = a[j]; i <= 5000; i++) {
            dp2[i] = (dp2[i] + dp[i-a[j]]) % MOD;   // including l[i]
        }
        swap(dp, dp2);
    }
 
    ans = 1; 
    for (int i = 0; i < n; i++)
        ans = (ans * 2) % MOD;                      // 2^n, 因为n小就不用快速幂了
    for (int i = 0; i < n; i++) {                   // stick i is max length
        cnt[a[i]]++;
        ans = (ans + MOD - dp[a[i]] + cnt[a[i]]) % MOD;     // remove all invalid cases
                                                    // +cnt[a[i]]: invalid cases do not include l[i] itself
    }
    ans = (ans + MOD - 1) % MOD;                    // -1: remove empty set
 
    printf("%d\n", ans);
    return 0;
}