题目链接：Codeforces 1189F

我们定义一个序列 $b_{1}, b_{2}, \dots, b_{n} (n > 1)$ 的「美丽值」为 $\min_{1 \le i < j \le n} \lvert b_{i} - b_{j} \rvert$。

我们给定一个序列 $a_{1}, a_{2}, \dots, a_{n}$ 个一个数字 $k$。请计算出所有长度恰好为 $k$ 的子序列的「美丽值」之和，答案对 $998244353$ 取模。

数据范围：$2 \le k \le n \le 1000$，$0 \le a_{i} \le 10 ^ {5}$。

Solution

首先把 $a$ 数组排序，显然不会影响答案。

直接计算看起来很困难？我们改成枚举「美丽值」统计其数量。貌似还是没法计数？那我们再放松一下条件：统计「美丽值」不小于某个数 $x$ 的子序列数量。

这样一来我们就可以计数了。设计状态 $f(i, j)$ 表示当前子序列长度为 $i$，子序列以第 $j$ 个数结尾，「美丽值」不小于 $x$ 的方案数。

转移方程非常简单：$f(i, j) = \sum f(i - 1, k) (a_{j} - a_{k} \ge x)$，可以直接前缀和优化做到 $\mathcal O(nk)$ 的复杂度。

通过鸽巢原理，我们可以得到 $x$ 的最大值为 $\left \lfloor \frac{\max \{ a_{i} \} }{k - 1} \right \rfloor$，于是总复杂度为 $\mathcal O(nk \cdot \frac{\max \{ a_{i} \} }{k - 1}) = \mathcal O(n \cdot \max \{ a_{i} \} )$。

时间复杂度：$\mathcal O(n \cdot \max \{ a_{i} \} )$。

Code

#include <cstdio>
#include <algorithm>

const int N = 1e3 + 5;
const int MOD = 998244353;

int n, k, a[N], p[N], f[N][N], sum[N][N];

void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
int solve(int x) {
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= n; j++) {
            f[i][j] = sum[i][j] = 0;
        }
    }
    for (int i = 1, j = 0; i <= n; i++) {
        for (; a[i] - a[j + 1] >= x; j++);
        p[i] = j;
    }
    f[0][0] = 1;
    std::fill(sum[0], sum[0] + n + 1, 1);
    for (int i = 1; i <= k; i++) {
        for (int j = i; j <= n; j++) {
            f[i][j] = sum[i - 1][p[j]];
            sum[i][j] = f[i][j];
        }
        for (int j = i; j <= n; j++) {
            add(sum[i][j], sum[i][j - 1]);
        }
    }
    return sum[k][n];
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    std::sort(a + 1, a + n + 1);
    int ans = 0;
    for (int t = a[n], i = 1; i * (k - 1) <= t; i++) add(ans, solve(i));
    printf("%d\n", ans);
    return 0;
}