AT_agc064_d [AGC064D] Red and Blue Chips

· · 题解

高妙 counting 题/bx/bx/bx。

记原串 S 中 R 的个数为 r，B 的个数 b。\alpha^x 表示重复拼接 x 个字符 \alpha 得到的字符串，例如 A^3=AAA。

由于要求本质不同，所以先思考这样一个问题，给定一个字符串 T。如何 check 是否有一种操作方案使得最终第 N 个字符串即为 T。

把 T 翻转，显然第 1 位此时必为 B，直接扣掉，那么得到的新串 T 一定形如 A^{l_1}BA^{l_2}B\dots A^{l_m} B A^t，其中 l,t 满足 0\le l_i,t\le r,\sum l_i+t=r。

先考虑扣掉后面 A^t，显然将 T 可以拆分成 m 个形如 A^xB 的段。 发散注意力，注意到 T 合法的充要条件即能从删去末尾 B 的原串 S' 中，取出 m 个两两不交的子序列，分别为 R^{l_1}B,R^{l_2}B,\dots,R^{l_m}B，其中 m=b-1。注意这里要求的是子序列，不要求连续，也不要求这些段在原串中依次出现。没有被选中的 R，恰好对应末尾的 R^t。

接下来考虑如何 check 这个条件。直接把 l_i 从大到小排序，记为 x_1\ge x_2\ge\cdots\ge x_m。

因为子序列匹配不要求这些段在原串中依次出现，所以我们可以按任意顺序去匹配。贪心策略是：让最长的段去匹配最靠右的 B。

记 d_i 为 S' 中从右往左第 i 个 B 右侧的 R 的个数，并令 d_{m+1}=r。那么最右边的 p 个 B 及其右侧的所有 R，总共有 d_{p+1} 个。

前 p 个最长的段 x_1,\dots,x_p，再加上末尾的 t 个 R，一共需要 t+\sum_{q=1}^{p}x_q 个 R。它们必须能被最右边的 p 个 B 及其右侧的 R 容纳，因此必须有

\forall\,0\le p\le m,\qquad t+\sum_{q=1}^{p}x_q\ge d_{p+1}

于是考虑 dp 求解。从大到小枚举段长，每次确定这个长度出现了多少次。

设 f_{i,j,k} 表示已经确定了所有长度大于 i 的段，共确定了 j 段，这些段的长度之和加上末尾长度 h 为 k 的方案数。

初始时还没有确定任何一段，只需枚举末尾长度 t。由 p=0 时的限制，有：

f_{r,0,t}=1\qquad(d_1\le t\le r)

接下来处理长度 i。假设这个长度出现了 l 次，那么：

j'=j+l,\qquad k'=k+il

需要保证转移后仍然合法，故有：

\forall\,1\le q\le l,\qquad k+iq\ge d_{j+q+1}

从剩余的 m-j 个段的位置中，选出 l 个填入长度 i，因此转移系数为 \binom{m-j}{l}，那么综上可以得到转移方程：

f_{i-1,j+l,k+il} \leftarrow f_{i,j,k}\binom{m-j}{l}

答案即为：

\sum_{j=0}^{m}f_{0,j,r}

对于每个正长度 i，j 和 l 的枚举规模均为 O(\frac{r}{i})，k 的枚举规模为 O(r)，因此 dp 的时间复杂度为：

O\left(r^3\sum_{i=1}^{r}\frac{1}{i^2}\right)=O(r^3).

加上组合数预处理，总时间复杂度为 O(N^3)，空间复杂度为 O(N^2)。

:::success[Code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int mod = 998244353;
int n, f[307][307], g[307][307], C[307][307], b[307], tot = 0;
string s;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    C[0][0] = 1;
    for (int i = 1; i < 307; i++)
    {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
    cin >> n >> s;
    s = '#' + s;
    int t = 0;
    for (int i = n - 1; i >= 1; i--)
        if (s[i] == 'R')
            t++;
        else
            b[++tot] = t;
    b[tot + 1] = t;
    for (int i = b[1]; i <= t; i++)
        f[0][i] = 1;
    for (int i = t; i >= 1; i--)
    {
        memset(g, 0, sizeof(g));
        for (int j = 0; j <= min(tot, t / (i + 1)); j++)
            for (int k = 0; k <= t; k++)
                for (int l = 0; l <= min(tot - j, (t - k) / i); l++)
                {
                    int nj = j + l, nk = k + l * i;
                    if (nk < b[nj + 1])
                        break;
                    (g[nj][nk] += f[j][k] * C[tot - j][l] % mod) %= mod;
                }
        for (int j = 0; j <= tot; j++)
            for (int k = 0; k <= t; k++)
                f[j][k] = g[j][k];
    }
    int res = 0;
    for (int j = 0; j <= tot; j++)
        (res += f[j][t]) %= mod;
    cout << res;
}

:::