题目链接

题目描述

给出一个序列 $a[1…n]$ 和 $k$

求 $a$ 所有长度为 $k$ 的子序列的价值和

定义一个序列 $b[1…k]$ 的价值为 $min(abs(b_i-b_j))$，即最接近的两个数的差

$1 \le k,n \le 10^4$

简要做法

由抽屉原理，最大价值 $\le \frac{max(a_i)}{k-1}$

考虑枚举价值 $v$，统计价值等于 $v$ 的方案数

发现等于很难统计，不妨统计大于等于的方案数

$f(i,j)$ 表示前 $i$ 个数中选 $j$ 个数，$i$ 必选的方案数

$f(i,j)=f(i-1,j) + f(pos,j-1)$

$pos$ 为最后一个满足 $a_i - a_pos \geq v$ 的位置

这东西是有单调性的，双指针维护 $pos$ 即可

参考代码

#include <stdio.h>
#include <algorithm>
#include <memory.h>

int read(int x = 0, int f = 0, char ch = getchar())
{
    while ('0' > ch or ch > '9')
        f = ch == '-', ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

#define int long long

const int N = 1e4 + 5;
const int P = 998244353;

int n, k, ans;
int a[N], f[N][N];

signed main()
{
    n = read(), k = read(), f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        a[i] = read();
    std::sort(a + 1, a + 1 + n);
    for (int v = 1; v <= a[n] / (k - 1); (ans += f[n][k]) %= P, v++)
        for (int i = 1, pos = 0; i <= n; i++)
        {
            f[i][0] = 1;
            while (a[i] - a[pos + 1] >= v)
                pos++;
            for (int j = 1; j <= k; j++)
                f[i][j] = (f[i - 1][j] + f[pos][j - 1]) % P;
        }
    return printf("%lld", ans), 0;
}