题解：P14360 [CSP-J 2025] 多边形 / polygon（民间数据）
newsname
·
·
题解
今年的 T4好水呀，后悔没参加。
思路：
知识点：化归 + 截断背包。
把长度升序排好 a_1\le\dots\le a_n。任取可行方案，设其中最大棒是 a_j，可行条件
于是答案变为对每个 $j$：在 ${a_1,\dots,a_{j-1}}$ 中选若干根，其和大于 $a_j$ 的子集个数之和。注意因为都不大于 $a_j$，单根不可能大于 $a_j$，所以无需再显式排除选 $0/1$ 根。
设 $mx=\max a_i\le 5000$。用 $0/1$ 计数背包维护前缀集合的子集和分布 $f_s$（只保留 $0\le s\le mx$），以及总子集数 $tot=2^{\text{t}}$。（$t$ 为已处理根数），对于当前最大棒 $a_j$，设 $n$ 为 在所有当前能拼出的子集和里，满足 $s>a_j$ 的那些子集的数量，则所需个数为 $\text{ans}\times j=n=tot-\sum\times {s=0}^{a_j}f[s]\pmod P$。
然后把 $a_j$ 加入背包：倒序转移 $f[s+a_j]+=f[s]$（若 $s+a_j>mx$ 直接忽略，因为这些和以后对任何阈值 $a_t\le mx$ 都必然计入“大于阈值”的部分，已经通过 $tot$ 体现），并令 $tot\leftarrow 2\times tot$。
时间复杂度 $\mathcal O(n\cdot mx)$，最劣时间复杂度 $\mathcal O(n^2)$，空间复杂度 $\mathcal O(mx)$。足以通过本题。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=5005,mod=998244353;
int a[maxn],f[maxn];
int main(){
int n;
cin>>n;
int mx=0;
for(int i=1;i<=n;i++){
cin>>a[i];
mx=max(a[i],mx);
}
sort(a+1,a+n+1);
f[0]=1;
int tot=1,ans=0;
for(int i=1;i<=n;i++){
int lim=a[i],s=0;
for(int t=0;t<=lim;t++){
s+=f[t];
if(s>=mod) s-=mod;
}
int add=tot-s;
if(add<0) add+=mod;
ans+=add;
ans%=mod;
for(int t=mx;t>=0;t--){
if(f[t]){
int u=t+a[i];
if(u>mx) continue;
int v=f[t]+f[u];
v%=mod;
f[u]=v;
}
}
tot<<=1;
tot%=mod;
}
cout<<ans%mod;
return 0;
}
```