[ARC186E] Missing Subsequence 题解

Description

给定一个整数序列 \(\left(X_1, \ldots, X_M\right)\) ，其长度为 \(M\)，元素取值为 \(1, \ldots, K\)。

要求找出长度为 \(N\) 的序列 \((A_1, \ldots, A_N)\) 的数量，元素取值为 \(1, \ldots, K\)，并满足以下条件，结果取模 \(998244353\)：

• 在所有长度为 \(M\) 的序列中，唯一不能作为 \((A_1, \ldots, A_N)\) 的（不一定连续的）子序列的序列是 \((X_1, \ldots, X_M)\)。

\(2\leq M,K\leq N\leq 400,1\leq X_i\leq K\)。

Solution

不妨设 \(F(\{x_1,x_2,\ldots,x_m\})\) 表示所有满足除了 \(x\) 的长度为 \(m\) 的序列都是其子序列的序列集合。

考虑一个序列 \(a\) 什么时候可以满足条件。

设 \(i\) 为 \(x_1\) 在 \(a\) 里面第一次出现的位置，容易发现除了 \(x_1\) 的颜色都在 \(a_1,a_2,\ldots,a_{i-1}\) 出现了，且 \((a_{i+1},a_{i+2},\ldots,a_n)\in F(\{x_2,x_3,\ldots,x_m\})\)。

然后经过手玩一下会发现这个条件在 \(x_1=x_2\) 的情况下还是充分条件。

证明就考虑如果满足了这两个条件，第一位为 \(x_1\) 的子序列一定都满足条件。

否则设第一位为 \(s\)，若第二位为 \(x_1\)，则第二位匹配 \(i\)，根据第二个条件所有长度小于 \(m-1\) 的序列都出现在 \(a_{i+1}\) 之后。如果第二位不为 \(x_1\)，根据第二个条件 \(x_2,x_3,\ldots,x_m\) 也一定出现在 \(a_{i+1}\) 之后。

对于 \(x_1\neq x_2\) 的情况，设 \(j\) 为 \(x_2\) 在 \(a_1,a_2,\ldots,a_{i+1}\) 最后一个出现位置，那么还需要满足除了 \(x_1\) 的颜色都在 \(a_1,a_2,\ldots,a_{j-1}\) 出现。

下面证明一下必要性。对于一个合法的序列 \(a\)，如果存在颜色 \(c\) 使得 \(c\) 第一次出现位置在 \([j+1,i-1]\) 内，则 \(c,x_2,x_3,\ldots,x_m\) 这个序列的除了 \(c\) 的部分只能从 \(i+1\) 匹配起，而根据第二个条件这个东西一定是匹配不出来的，矛盾。

充分性证明和 \(x_1=x_2\) 的情况差不多，这里就不写了。

求方案数时设 \(f_{i,j}\) 表示长度为 \(i\) 的序列满足 \(x_j,x_{j+1},\ldots,x_m\) 的条件的数量，转移直接枚举 \(x_j\) 第一次出现的位置和 \(x_{j+1}\) 在 \(x_j\) 第一次出现之前的最后位置即可。

时间复杂度：\(O(n^2m+n^2k)\)。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 405, kMod = 998244353;

int n, m, k;
int x[kMaxN], f[kMaxN][kMaxN], coef[kMaxN], C[kMaxN][kMaxN], cnt[kMaxN][kMaxN];

constexpr int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void prework() {
  C[0][0] = 1;
  for (int i = 1; i <= 400; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= k; ++j) {
      cnt[i][j] = qpow(j, i);
      for (int s = 1; s < j; ++s) dec(cnt[i][j], 1ll * cnt[i][s] * C[j][s] % kMod);
      // std::cerr << cnt[i][j] << ' ';
    }
    // std::cerr << '\n';
  }
}

void dickdreamer() {
  std::cin >> n >> m >> k;
  for (int i = 1; i <= m; ++i) std::cin >> x[i];
  prework();
  for (int i = 1; i <= n; ++i) {
    f[m][i] = cnt[i][k - 1];
    // std::cerr << f[m][i] << ' ';
  }
  // std::cerr << '\n';
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j < i; ++j)
      inc(coef[i], 1ll * cnt[j - 1][k - 1] * qpow(k - 2, i - 1 - j) % kMod);
  }
  for (int i = m - 1; i; --i) {
    for (int j = 1; j <= n; ++j) {
      if (x[i] == x[i + 1]) {
        for (int s = 1; s <= j; ++s) {
          inc(f[i][j], 1ll * cnt[s - 1][k - 1] * f[i + 1][j - s] % kMod);
          // std::cerr << "fuck " << j << ' ' << s << ' ' << cnt[s - 1][k - 1] << ' ' << f[i + 1][j - s] << '\n';
        }
      } else {
        for (int s = 1; s <= j; ++s)
          inc(f[i][j], 1ll * coef[s] * f[i + 1][j - s] % kMod);
      }
      // std::cerr << f[i][j] << ' ';
    }
    // std::cerr << '\n';
  }
  std::cout << f[1][n] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}