分享一下 D题 非动态规划的解法

一、核心观察

我们首先抓住题目中数组和操作的关键特性： 初始序列是 0~n 的排列删去一个数得到的，因此任何时刻数组都恰好缺失 0~n 中的一个数，这个缺失的数就是当前数组的 mex。

在此基础上，我们可以得到核心性质：mex 经过操作后永远不会变小。具体操作对 mex 的影响分为两种：

• 若选择的元素大小在 [0, mex-1] 范围内：删除该元素后，数组会暂时缺失它， mex 会暂时变小；但操作最后会把删除后的 mex（也就是这个元素）重新加回数组，数组回到初始状态，因此 mex 保持不变。此时每一步有 mex 个可选位置。
• 若选择的元素 x > mex：删除该元素后，数组缺失 mex 和 x， mex 仍为原 mex；操作最后把原 mex 加回数组，新数组缺失的是 x，因此 mex 会变为 x（严格变大）。

二、方案数推导

设当前 mex 为 fmex，目标 mex 为 tmex，我们分两种情况讨论 t 次操作的方案数：

1. 当 fmex == tmex 时 要让 mex 始终保持 fmex，每一步都只能选择 [0, fmex-1] 中的元素，每一步有 fmex 种选择。因此 t 次操作的方案数为 。

2. 当 fmex < tmex 时 我们可以用容斥思想计算：总方案数（每一步都有 fmex 种选择，即 ）减去“一次都没选能让 mex 变大的选择”的方案数（即每一步都只在 [0, fmex-2] 中选，共 种）。因此 t 次操作的方案数为 ，其含义是“至少选择一次能让 mex 前进的元素”。

三、累计方案数与等比数列求和

题目要求对每个 x，计算 t 从 0 到 k 的方案数之和 。 结合上述推导，这个和恰好是等比数列的前 k+1 项和形式，我们可以用等比数列求和公式快速计算：

• 定义 。
• 当 x = 1 时，每一项都是 1，因此 S(x) = k + 1。
• 当 x ≠ 1 时，用公式 计算（在模意义下，除法用费马小定理求逆元实现）。

最后结合初始 mex，分情况输出每个 x 对应的累计方案数即可。（最后还有当x为2，直接套用求和公式可能会出现除0，特判一下即可）

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define lowbit(x) (x) & (-x)
typedef pair<int, int> PII;

const int mod = 1e9 + 7, MOD = 998244353;
const int N = 5e3 + 5, inf = 0x3f3f3f3f, INF = 0x3f3f3f3f3f3f3f3f;

int ksm(int d, int u, int _mod = MOD)
{
  int res = 1;
  while(u > 0)
  {
    if(u & 1) res = res * d % _mod;
    d = d * d % _mod; u >>= 1;
  }
  return res;
}
int inv(int x, int _mod = MOD)
{
  return ksm(x, _mod-2, _mod);
}

int a[N];
void solve()
{
  int n, k; cin >> n >> k;
  for(int i = 1; i <= n; ++i) cin >> a[i];
  sort(a+1, a+1+n);

  int fmex = -1;
  for(int i = 1; i <= n; ++i)
    if(a[i] != i-1)
    {
      fmex = i-1; break;
    }
  if(fmex == -1) fmex = n;

  for(int i = 0; i <= n; ++i)
  {
    if(i < fmex) cout << 0 << ' ';
    else if(i == 0)
    {
      cout << 1 << ' ';
    }
    else if(i == 1)
    {
      if(i == fmex) cout << k+1 << ' ';
      else cout << k << ' ';
    }
    else
    {
      // i == fmex: ans = i^0 + i^1 + ... + i^k;
      // i >  fmex: ans = i^0 + i^1 + ... + i^k -
      //                  (i-1)^0 - (i-1)^1 - ... - (i-1)^k;

      int ans =(ksm(i, k+1)-1+MOD)%MOD *inv((i-1+MOD)%MOD) %MOD;
      int rep;
        if(i == 2) rep = (k + 1) % MOD;
        else rep =(ksm(i-1, k+1)-1+MOD)%MOD *inv((i-2+MOD)%MOD) %MOD;
      
      if(i != fmex) ans = (ans - rep + MOD) % MOD;
      cout << ans << ' ';
    }
  }
  cout << endl;
}

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t = 1;
  cin >> t;
  while (t--){solve();}

  return 0;
}