2025 CSP-J2 T4 多边形 / polygon 题解
chenyuan3
·
·
题解
（J 组题解链接：T1、T2、T3、T4、视频题解、游记）
注：本题解非常抽象。
答案与顺序无关，所以先排序。（赛后补题时忘记排序导致 100pts 变成 32pts）
$$
\begin{align}
\sum_{j=1}^{i-1}p_j\ge2\\
\sum_{j=1}^{i-1}a_jp_j>a_i\\
\sum_{j=1}^{i-1}[p_j=0\lor p_j=1]=i-1
\end{align}
$$
的个数。[^1]其中：
$$
[q]=\left\{\begin{align*}
1&&q\ 为真\\
0&&q\ 为假\\
\end{align*}\right.
$$
考虑和以及 $a_i\le5000$ 的限制条件，容易想到**背包求方案数**（别问我怎么想到的，赛时就是这么想到的），但是由于 $O(n\sum_{i=1}^na_i)$ 会 TLE，所以赛时痛失 20pts，与 AK 失之交臂。
~~根据题解~~，我们可以**考虑问题的反方向，即不满足条件的有哪些**。令枚举到 $i$ 时的和为 $j$ 的方案数为 $f_j$（参考上一段），总方案数为 $2^i$，不合法的方案数为 $\sum_{j=1}^{a_{i+1}}f_j$，两者做差即可。这样，需要使用到的 $j$ 的最大值不超过 $\max_{i=1}^na_i$，总时间复杂度为 $O(n\max_{i=1}^na_i)$，可以 AC。
:::success[代码]
``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 5010, mod = 998244353;
ll n, a[maxn], f[maxn], ans;
ll qp(ll a, ll b = mod - 2, ll p = mod)
{
ll ans = 1;
while (b)
{
if (b & 1)
{
ans = ans * a % p;
}
a = a * a % p;
b >>= 1;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (ll i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
f[0] = 1;
for (ll i = 1; i <= n; i++)
{
for (ll j = maxn - 1; j >= a[i]; j--)
{
(f[j] += f[j - a[i]]) %= mod;
}
ll sum = 0;
if (i > 1 && i < n)
{
(ans += qp(2, i)) %= mod;
for (ll j = 0; j <= a[i + 1]; j++)
{
(ans += mod - f[j]) %= mod;
}
}
}
cout << ans;
return 0;
}
```
:::
:::success[视频题解]
:::
[^1]: 意思是前面 $i-1$ 个数可以选（$p_j=1$）或不选（$p_j=0$），但是至少选两个，且选的和大于 $a_i$。原条件两边同时减去 $a_i$ 可得。