题解：P14360 [CSP-J 2025] 多边形 / polygon（目前仅有本题有民间数据）
Terminal_P
·
·
题解
给出 n 根小木棍的长度，从中任选若干根，求其拼成多边形的方案数。
***
正难则反。考虑从中任选若干根，不能拼成多边形的方案数。
考虑动态规划。先给小木棍长度升序排序。令 $F_i(x)$ 为只考虑前 $i$ 根木棍，其长度和恰好为 $x$ 的方案数。显然 $F_i(x) = F_{i - 1}(x- A_i) + C_i(x)$，其中 $C_i(x)$ 表示前 $i$ 根木棍中长度恰为 $x$ 的个数。
最终答案即为 $2^n - 1 - n - \binom{n}{2} - \sum\limits_{1 \le i \le n}\sum\limits_{1 \le x \le A_i}F_i(x)$。
时间复杂度 $O(nV)$，空间复杂度 $O(n)$。
:::success[代码]
```cpp
const i64 p = 998244353;
inline i64 mod(i64 x) { return (x % p + p) % p; }
inline i64 qpow(i64 a, i64 b) {
i64 ret = 1;
while (b) {
if (b & 1) ret = mod(ret * a);
a = mod(a * a);
b >>= 1;
}
return ret;
}
void solve(i32 _) {
i32 n;
i64 ans = 0;
std::cin >> n;
std::vector<i32> a(n + 2, 0);
for (i32 i = 1; i <= n; i++) std::cin >> a[i];
std::sort(a.begin() + 1, a.begin() + n + 1);
i32 V = a[n];
std::vector<std::vector<i64>> f(2, std::vector<i64>(V + 2, 0));
for (i32 i = 1; i <= n; i++) {
for (i32 j = 1; j <= a[i]; j++) ans = mod(ans + f[1][j]);
for (i32 j = V - a[i]; j >= 0; j--)
f[1][j + a[i]] = mod(f[1][j + a[i]] + f[1][j] + f[0][j]);
f[0][a[i]]++;
}
std::cout << mod(qpow(2, n) - 1 - n - mod(n * (n - 1) * qpow(2, p - 2)) - ans)
<< endl;
return void();
}
```
:::