CF1188C Array Beauty

感觉比较套路。

Solution

首先先对序列排序，可以证明排了序之后答案不会变。

首先考虑暴力点的$dp$，首先$f_{i,j,minn}$表示前$i$个，选了$j$个，当前最小值为$minn$的情况数，不做出巨大突破的话，这个复杂度大概是$O(n^2{V}^2)$或者$O(n^{2}V\log V)$，最低$O(n^{2}V)$的，喜提$0$分，没有任何前途。

考虑重新思考贡献问题，发现最大值只能是$\frac{a[n]}{k-1}$，这次我们将$=minn$的条件改变成$\ge m$，转移方程就是：
$$f[i][j]=\sum _{a[i]-a[k]\ge val,k\le i}f[k-1][j-1]$$
由于数列单增，先前缀和一下，之后双指针扫描，这部分的复杂度就能降到$O(nk)$，在乘上前面我们所枚举的复杂度，最后的复杂度就是$O(nk\times \frac{a[n]}{k-1})\approx O(nV)$，可以通过。

注：再说一下是怎么将贡献条件$=minn$变成$\ge minn$，实质上我们此时贡献的就不再是权值$\times$次数了，而只是次数了，所以对于一段最小值是$minn$的子序列，对于$\mathrm{\forall }val\le minn$都会贡献$1$次，那么同样贡献了$minn$，所以是等价的。

Code

#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0;
    bool flag = 0;
    char c = getchar();
    while (c < '0' || '9' < c) { if (c == '-') flag = 1; c = getchar(); }
    while ('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if (flag) res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
    if (res < 0) putchar('-'), res = -res;
    if (res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(const char *s) { while (*s) putchar(*s++); }
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 1005, mod = 998244353, M = 1e5 + 5;
int n, m;
int a[N], f[N][N], g[N][N], cnt[M], ans;
int main()
{
    read(n, m);
    for(int i = 1;i <= n;i ++) read(a[i]);
    sort(a + 1, a + n + 1);
    a[0] = -1e9;
    for(int val = 1;val * (m - 1) <= a[n];val ++)
    {
        f[0][0] = 1, g[0][0] = 1;
        for(int i = 1, l = 0;i <= n;i ++)
        {
            while(val <= a[i] - a[l]) l ++;
            for(int j = 0;j <= m;j ++)
            {
                if(j) f[i][j] = g[l - 1][j - 1];
                g[i][j] = (g[i - 1][j] + f[i][j]) % mod;
            }
            cnt[val] = (cnt[val] + f[i][m]) % mod;
        }
        ans = (ans + cnt[val]) % mod;
    }
    write(ans);
    return 0;
}