CF1188C Array Beauty 解题报告 （DP）

题目大意

链接

定义数列的美丽值为其最接近两个数的差的绝对值。

给定数列 {a_n} 和正整数 k，求该数列中所有长度为 k 的子序列的美丽值之和。因为答案比较大，输出其对 998244353 取模的结果。

题目保证 a 中元素都不超过 10⁵, n 和 k 不超过 1000 且 k 不超过 n。

分析

看到这个题除了与元素排列无关之外就没什么想法，感觉 n 和 k 这么小像个 O(n²) 的 dp 但是状态方程很难写。然后仔细再看了一下题发现切入点很可能在 a 的范围。因为一般来说 a 给这么小要么是求和避免溢出要么就是为了作遍历。但是这个题已经要取模了所以不存在求和的溢出问题，所以可以往把 a_max 放在复杂度里面的方向考虑。

之后发现如果固定美丽值为 x 那么根据抽屉原理 , 从而感觉可能可以分别计算不同的 x 然后把答案加起来因为 x 的取值范围与 k 成反比。

然而即使这样也不容易计算答案。主要的难点在于 x 本身是一个极值约束，对于数列中的一般项没有明显的限制。不过这可以通过一个常见的方法绕过：求其前（后）缀和。

定义 f(x) 为美丽值不小于 x 的长度为 k 的子序列总数。g(i, j) 为在当前 x 下前 i 项中恰好选取 j 项且选取第 i 项的子序列总数，那么有：
如果我们将 {a_n} 排序那么第二行的转移范围是单调不减的。所以在预处理 g(?, j) 的前缀和 s(j) 后可以做到均摊 O(1) 转移。这样对于任意一个 x 我们通过 g 处理出对应的 f(x) 所需的时间均为 O(nk)。因为我们关心的一共有不超过 个不同的 x, 所以总的复杂度为 O(n(a_max - a_min))。

代码

总复杂度为 O(n(a_max - a_min))

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
 
const int maxn = 1123;
const int maxa = 112345;
const int MOD = 998244353;
 
inline int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
 
inline int mul(int a, int b) {
  return ll(a) * b % MOD;
}
 
int f[maxa], a[maxn], g[maxn][maxn], s[maxn];
int n, K, ans;
 
int main() {
  scanf("%d%d", &n, &K);
  FOR(i, 1, n) scanf("%d", a + i);
  sort(a + 1, a + n + 1);
  FOR(x, 0, 1e5) if (x <= 1 || a[n] - a[1] >= x * ll(K - 1)) {
    fill(s, s + K, 0);
    int l = 0;
    FOR(i, 1, n) {
      g[i][1] = 1;
      while (l + 1 < i && a[l + 1] + x <= a[i]) {
        l++;
        FOR(j, 1, K - 1) s[j] = add(s[j], g[l][j]);
      }
      FOR(j, 2, K) g[i][j] = s[j - 1];
      f[x] = add(f[x], g[i][K]);
    }
  }
  FOR(x, 0, 1e5) ans = add(ans, mul(add(f[x], MOD - f[x + 1]), x));
  printf("%d", ans);
}