感觉比较套路。
Solution
首先先对序列排序，可以证明排了序之后答案不会变。
首先考虑暴力点的$dp$，首先$f_{i,j,minn}$表示前$i$个，选了$j$个，当前最小值为$minn$的情况数，不做出巨大突破的话，这个复杂度大概是$O(n^2V^2)$或者$O(n^2V\log V)$，最低$O(n^2V)$的，喜提$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$的子序列，对于$\forall val \le minn$都会贡献$1$次，那么同样贡献了$minn$，所以是等价的。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #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;
}
|