【题解】P6525 「Wdoi-1」蓬莱玉枝

· · 题解

题目传送门

怀旧一下来补个题！出题人可爱喵/ka

选存在 a+b>c 的方案数等于总方案数 - 任意三项都满足 a+b\le c 的方案数。然后后面这个东西在排序之后只需要满足相邻三项成立那么所有项都成立。

所以显然先对 a_i 升序排序。

然后先考虑总方案数如何计算。对于一个最大值为 a_i 的集合来说，前 i-1 个数可选可不选，所以这个集合的期望大小是 \dfrac{i-1}{2}+1，有 2^{i-1} 种可能，所以答案就是 a_i \times 2^{i-1}(\dfrac{i-1}{2}+1)=a_i \times2^{i-2}(i+1)。

然后考虑计算不合法的方案数。

考虑枚举集合的最大值和次大值进行 dp 转移，设 f_{i,j} 表示满足最大值为 a_i，次大值 \le a_j 的所有集合大小之和，g_{i,j} 表示满足最大值为 a_i，次大值 \le a_j 的集合数量。

对于固定的 i,j，需要找到一个合法的位置 k 进行转移，合法的意义即满足 k<j 且 a_k \le a_i-a_j。

那么对于一个状态 (i,j) ，要从其前驱状态 (j,k) 转移过来，它的大小之和 = 其前驱状态大小之和 + 其前驱数量 + 2，即 f_{i,j} \leftarrow f_{j,k}+g_{j,k}+2。

转移含义：所有前驱集合 (j,k) 都新加入一个 a_i，每个集合的大小 +1，贡献的大小之和为 (f_{j,k}+g_{j,k})；然后还要新计算一个集合 \left\{a_i,a_j \right\}，多贡献的大小为 2。

同理有转移 g_{i,j} \leftarrow g_{j,k}+1。

那么如何确定 k 的位置呢？发现 k 肯定是随着 j 递增单调不增的，所以枚举 j 的同时双指针维护 k 的值即可。

根据我们设置的状态，转移结束之后还需要维护 f_{i,j} \leftarrow f_{i,j}+f_{i,j-1},g_{i,j} \leftarrow g_{i,j}+g_{i,j-1}。

实际上设置的 dp 状态就是为了维护前缀和。

时间复杂度 O(n^2)。

代码：

#include<bits/stdc++.h>
#define ll long long
#define back return
#define ri register int
#define ull unsigned ll
#define ld long double
using namespace std;
ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    back x*f;
}
const int p=20060723,N=5005;
ll n,tot,res,a[N],f[N][N],g[N][N],pw[N];
int main() 
{
    n=read();
    for(ri i=1;i<=n;i++)
        a[i]=read();
    sort(a+1,a+n+1);
    pw[0]=1;
    for(ri i=1;i<=n;i++)
        pw[i]=pw[i-1]*2%p;
    tot=a[1];
    for(ri i=2;i<=n;i++)
        tot=(tot+a[i]*pw[i-2]%p*(i+1)%p)%p;
    for(ri i=1;i<=n;i++)
    {
        res=(res+a[i])%p;
        int k=i;
        for(ri j=1;j<i;j++)
        {
            while(k>0&&a[k]>a[i]-a[j])
                k--;
            int l=min(k,j-1);
            f[i][j]=(f[j][l]+g[j][l]+2)%p,g[i][j]=(g[j][l]+1)%p;
            res=(res+a[i]*f[i][j]%p)%p;
            f[i][j]=(f[i][j]+f[i][j-1])%p,g[i][j]=(g[i][j]+g[i][j-1])%p;
        }
    }
    cout<<(tot-res+p)%p<<"\n";
    back 0;
}