题解 [AGC055D] ABC Ultimatum

· · 题解

好妙的题……甚至妙到了不知该如何去追溯思路。所以该题目记录只能尽可能地去还原思维路径。

第一眼看到本题显然会想到 dp，然后我们会想到类似分别记录当前 A，B，C，AB，CA，BC，ABC，BCA，CAB 的数量进行线性 dp 的思路，但是这样并不好去除重复方案，若去掉则时间复杂度过高。

于是，学到的一点是，在根据题意实在无法进行 dp 时，要尽量思考出一个满足题目要求的充要条件，并对该充要条件进行 dp。

我们发现题目中要求的 n 个子序列很有特点：ABC，BCA，CAB，具体来说是关于 A，B，C 的三个轮换，这里是不是会存在一些巧妙的性质呢？答案是有的。

不妨记 x_A 表示 A 的个数，x_B 表示 B 的个数，x_C 表示 C 的个数。

具体来说，我们拿 A 举例，我们发现在 BCA 和 CAB 中，A 是一定会在 C 的后面的，即如果只有这两种子序列，对于任意前缀子串而言，x_A 一定不大于 x_C，但事实上我们还存在子序列 ABC，在该子序列中，A 是会排在 C 之前的，故我们此时有结论：

类似的，我们可以写出轮换的另外两个结论。而由于子序列个数为 n，于是此时我们得到了一个看上去并没有那么强但也还不弱的结论：

到这里我们其实已经论证了该结论的必要性，即对于满足条件的方案，一定满足该结论。但是如果满足该结论，是否就一定说明当前方案满足条件呢？

如果还能论证该结论的充分性，我们就可以顺利地将原问题转化为新的充要问题进行 dp 了。

考虑构造方案：对于第 i 个 A，我们找到第 i+B' 个 B，由于对于任意前缀 B 的个数最多比 A 多 B' 个，故第 i+B' 个 B 一定在第 i 个 A 之后；类似地，我们找到第 i+B'+C' 个 C，以及第 i+B'+C'+A' 个 A。如果下标超出 n 则对 n 取模。此时又由于 B'+C'+A'\le n，所以第 i+B'+C' 个 C 一定在第 i+B'+C'+A' 个 A 前面，同样也一定在第 i 个 A 前面。故此时对应的三个字母构成了一个前后顺序正确的环，且只会绕整个串至多一次，又由于此时这些字母一一对应，故充分性显然。

于是我们便可以对转化后的问题设计 dp 了！由于我们需要记录的信息是「前缀最大」的 x_A-x_C，x_B-x_A，x_C-x_B，所以我们还需要额外记录下当前 a,b,c 的个数，由于 a+b+c=i 的原因我们可以省去一维，故总状态数为 O(n^6)，转移为 O(1)，时间复杂度 O(n^6)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=47;
const int M=17;
const int mod=998244353;
int n,m;
char s[N];
ll dp[N][M][M][M][M][M];
int read(){
    int w=0,fh=1;
    char c=getchar();
    while (c>'9'||c<'0'){
        if (c=='-') fh=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+(c^48);
        c=getchar();
    }
    return w*fh;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    m=read(),n=m*3;
    scanf("%s",s+1);
    dp[0][0][0][0][0][0]=1;
    for (int i=0;i<n;i++){
        for (int a=0;a<=m;a++){
            for (int b=0;b<=m;b++){
                int c=i-a-b;
                if (c<0||c>m) continue;
                for (int x=0;x<=m;x++){
                    for (int y=0;y<=m;y++){
                        for (int z=0;z<=m;z++){
                            if (x+y+z>m) continue;
                            if (s[i+1]=='A'||s[i+1]=='?')
                                dp[i+1][a+1][b][max(x,a+1-c)][y][z]=(dp[i+1][a+1][b][max(x,a+1-c)][y][z]+dp[i][a][b][x][y][z])%mod;
                            if (s[i+1]=='B'||s[i+1]=='?')
                                dp[i+1][a][b+1][x][max(y,b+1-a)][z]=(dp[i+1][a][b+1][x][max(y,b+1-a)][z]+dp[i][a][b][x][y][z])%mod;
                            if (s[i+1]=='C'||s[i+1]=='?')
                                dp[i+1][a][b][x][y][max(z,c+1-b)]=(dp[i+1][a][b][x][y][max(z,c+1-b)]+dp[i][a][b][x][y][z])%mod;
                        }
                    }
                }
            }
        }
    }
    ll ans=0;
    for (int i=0;i<=m;i++)
        for (int j=0;j<=m;j++)
            for (int k=0;k<=m;k++)
                if (i+j+k<=m) ans=(ans+dp[n][m][m][i][j][k])%mod;
    cout<<ans<<'\n';
    return 0;
}