[AGC064D] Red and Blue Chips 题解

Description

你有 $N$ 个字符串，初始情况下每个字符串只有一个字符，是 $\texttt{R}$ 或 $\texttt{B}$，保证第 $N$ 个字符串是 $\texttt{B}$。

你需要对每个 $i=1,2,\cdots ,n-1$ 执行以下操作：

• 选择一个整数 $j$ 使得 $i< j\le n$，且第 $j$ 个字符串的最后一个字符是 $\texttt{B}$，然后把第 $i$ 个字符串整体拼接在第 $j$ 个字符串的前面。

问最后可以得到多少种本质不同的第 $N$ 个字符串，对 $998244353$ 取模。

$2\leq N\leq 300,s_N=\texttt{B}$。

Solution

考虑怎么判断一个终止串 $t$ 是否合法。

容易发现终止串形如一棵树的后序遍历的形式，所以可以倒着为每个位置找父亲。

在找父亲的过程中把终止串挂在最后一个 B 上，设 $m$ 为原串 B 的个数，$f_i$ 表示挂在 $i$ 上的串。

设当前走到了 $i$，如果当前 $s_i$ 为 R，就选择一个 $f_j$ 满足 $f_j$ 开头为 R 并把开头的 R 删掉，表示 $i$ 的父亲为 $j$。否则就需要把某个 $f_j$ 在字符为 B 的位置分裂，并且把分裂后前面的串挂在 $i$ 上。

由于我们需要尽量让当前所有 $f_i$ 开头的 R 数量和最多，所以每次选择长度最大的极长 R 段前分裂一定最优。容易发现这么做如果存在一个时刻满足 $s_i$ 为 R 且所有 $f_i$ 的开头都不为 R，那么这个串一定不合法。

形式化的描述就是设 $a_i$ 表示初始串倒数第 $i$ 个极长 R 连续段的长度，$b_i$ 表示终止串倒数第 $i$ 个极长 R 连续段的长度。

又因为 $b_1$ 显然不能动，所以只能对 $b_2,b_3,\ldots,b_m$ 排序，排序后合法的充分必要条件为 $\forall j\in[1,m],\sum_{i=1}^{j}{a_i}\leq\sum_{i=1}^{j}{b_i}$。

方案数容易 dp 得到。

时间复杂度：$O(n^3\ln n)$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 305, kMod = 998244353;

int n, m;
int a[kMaxN], sum[kMaxN], f[kMaxN][kMaxN], fac[kMaxN], ifac[kMaxN];
std::string str;

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(int n = 300) {
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= n; ++i) {
    fac[i] = 1ll * i * fac[i - 1] % kMod;
    ifac[i] = qpow(fac[i]);
  }
}

void dickdreamer() {
  std::cin >> n >> str;
  int lst = 0;
  for (int i = 1; i <= n; ++i) {
    if (str[i - 1] == 'B') {
      a[++m] = i - lst - 1;
      lst = i;
    }
  }
  prework();
  std::reverse(a + 1, a + 1 + m);
  for (int i = 1; i <= m; ++i) sum[i] = sum[i - 1] + a[i];
  int cnt = n - m;
  for (int i = a[1]; i <= cnt; ++i) f[1][i] = fac[m - 1];
  for (int i = cnt; ~i; --i) {
    for (int j = m; j; --j) {
      for (int k = cnt; k >= sum[j]; --k) {
        for (int c = 1; c <= std::min(j, (i ? k / i : n)); ++c) {
          if (k - i * (c - 1) >= sum[j - c + 1]) inc(f[j][k], 1ll * f[j - c][k - i * c] * ifac[c] % kMod);
          else break;
        }
      }
    }
  }
  std::cout << f[m][cnt] << '\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;
}