题解：P14360 [CSP-J 2025] 多边形 / polygon

· · 题解

树状数组做法

这 m (m \ge 3)根小木棍能拼成一个多边形当且仅当

\sum_{i=1}^{m-1}l_i > l_m

对 a 排序，令 f_s 表示当前用若干根小木棍(不是一根)能构成总长度为 s 的方案数，令 sum 为 \sum_{i=1}^n a_i 由上面的公式可知，对 a 排序后以第 i 根小木棍为多边形中的最长小木棍对答案的贡献为

\sum_{i=a_i+1}^{sum}f_i

发现 a_n \le 5000，所以实际上不用维护到 sum，只需维护到 a_n，然后对于 i > 5000 的 f_i 只需另建一个变量来记录次数即可。而对于 i \le 5000 的部分，用树状数组维护即可，具体的，每次遍历到一个 i，从大到小枚举 f_s(f_s \neq 0)，将 f_{s+a_i} 加上 f_s，再枚举 a_j(j<i)，将 f_{a_i+a_j} 加上 1。

令 a_{max} 为 a_i 中最大值，可视为与 n 同阶，则时间复杂度约为 O(n^2 \log{n} )。

AC 记录。

代码

#include <bits/stdc++.h>
#define lb(x) (x&(-x))
#define int long long
using namespace std;
inline int read()//读入优化 
{
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c))f=c=='-'?-f:f,c=getchar();
    while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
const int N=5e3+10,mod=998244353;
int n,a[N],ans;
int t[N];//树状数组
int f[N];//f_i 表示当前若干根小木棍长度和为i的方案数 
int maxn;//i>5000 的部分单独用一个变量记录
set<int>s;//实现从大到小枚举f_s,集合s中存f_s中的s 
int sum(int x)//树状数组求和
{
    int res=0;
    while(x)res=(res+t[x])%mod,x-=lb(x);
    return res;
}
void add(int x,int d)//树状数组更新
{
    while(x<=5000)t[x]=(t[x]+d)%mod,x+=lb(x);
}
signed main()
{
    n=read();
    for(int i=1; i<=n; i++)a[i]=read();
    sort(a+1,a+n+1);//对a排序
    for(int i=1; i<=n; i++)
    {
        if(i>=3)ans=((ans+sum(5000)-sum(a[i])+maxn)%mod+mod)%mod;//m>=3时加贡献
        maxn=(maxn*2)%mod;//大于5000的部分每次都会加上a_i,依旧大于5000,所以是乘2 
        for(auto j=s.end(); j!=s.begin();)
        {
            j--;
            if(*j+a[i]<=5000)f[*j+a[i]]=(f[*j+a[i]]+f[*j])%mod,add(*j+a[i],f[*j]);//从大到小枚举f_s,将f_{s+a_i}加上f_s。 
            else maxn=(maxn+f[*j])%mod;//超过5000的部分单独计算
        }
        for(auto j=s.end(); j!=s.begin();)
        {
            j--;
            if(*j+a[i]<=5000)s.insert(*j+a[i]);//s+a_i不超过5000时,f_{s+a_i}不为0,下一轮需要计算,用set存s可以去重 
        }

        for(int j=1; j<i; j++)
        {
            if(a[i]+a[j]<=5000)f[a[i]+a[j]]=(f[a[i]+a[j]]+1)%mod,add(a[i]+a[j],1),s.insert(a[i]+a[j]);//枚举a_j,将f_{a_i+a_j}加1 
            else maxn=(maxn+1)%mod;//超过5000的部分单独计算
        }
    }
    cout<<ans<<endl;//输出 
    return 0;
}