题解 AGC046D 【Secret Passage】

· · 题解

题意

给定 01 串 S，每次可以选择前两个字符，删除一个字符，还有一个字符插到任意位置。

求最后能得到多少种不同的字符串。

1\le |S|\le 300

题解

首先考虑每一次删除前两个的时候，保留的那个不要立刻插回去，而是当做一个自由的数。用一个三元组 (i,j,k) 表示字符串是 S[i:|S|]，j 个自由的 0 和 k 个自由的 1。

所以现在我们最多有 \mathcal O(|S|^3) 个三元组，我们想知道这些东西可以表示出多少不同的字符串。这个东西看上去不看好做。考虑下面的另一个算法：

对于一个字符串 T，从前往后枚举字符，维护 i,j,k，假设当前字符为 c，如果 c 和 S[i-1] 相等，那么让 i-1，否则如果 c=0 则 j+1，否则 k+1。每一个字符串这样扫一遍都能够得到唯一的 (i,j,k)。对于这 \mathcal O(|S|^3) 种的 (i,j,k)，我们可以算出每一种能够得到这个三元组的 T 的数量。

然后想一想不难发现，对于最后得到的三元组相同的 T，要么全部能被构造出来，要么全部不能被构造出来。然后对于一个 (i,j,k) 能够被构造出来，就相当于在第一步中存在三元组 (w,j+S[i:w-1]\text{中 0 的个数},k+S[i:w-1]\text{中 1 的个数})。要枚举 w 的原因是我们刚刚匹配的其实是整个串，但是实际上只剩下一个后缀，要用自由的 0/1 来补上。

朴素实现复杂度是四次方的，但是直接过了。

优化到三次方不难。但是我是懒狗。

代码

const int N=3e2+10;
int n;char s[N];int a[N],sum[N];
bool dp1[N][N][N];//dp1[i][j][k]表示剩下 s[i:] 有 j 个自由的 0 和 k 个自由的 1 是否可行
mint dp2[N][N][N];//dp2[i][j][k]表示从后往前撇匹配，能匹配上 s[i:]、j 个 0、k 个 1 的字符串数量
bool can[N][N][N];//can[i][j][k]表示dp2[i][j][k]能否被表示出来
signed main(){
    scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(a[i]=s[i]-'0');
    dp1[1][0][0]=1;
    for(int i=1;i<=n+1;i++)for(int j=n;~j;j--)for(int k=n-j;~k;k--)if(dp1[i][j][k]){
        //考虑消一步有那些情况
        if(i<=n-1){
            if(a[i]==0||a[i+1]==0)dp1[i+2][j+1][k]=1;
            if(a[i]==1||a[i+1]==1)dp1[i+2][j][k+1]=1;
        }
        if(i<=n){
            if(a[i]==0&&(j||k))dp1[i+1][j][k]=1;
            if(a[i]==0&&k)dp1[i+1][j+1][k-1]=1;
            if(a[i]==1&&(j||k))dp1[i+1][j][k]=1;
            if(a[i]==1&&j)dp1[i+1][j-1][k+1]=1;
        }
        if(j>=2)dp1[i][j-1][k]=1;
        if(k>=2)dp1[i][j][k-1]=1;
        if(j&&k)dp1[i][j-1][k]=1,dp1[i][j][k-1]=1;
    }
    dp2[n+1][0][0]=1;
    for(int i=n+1;i;i--)for(int j=0;j<=n;j++)for(int k=0;j+k<=n;k++)if(dp2[i][j][k].x){
        if(a[i-1]==0)dp2[i][j][k+1]+=dp2[i][j][k];
        else dp2[i][j+1][k]+=dp2[i][j][k];
        dp2[i-1][j][k]+=dp2[i][j][k];
    }
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<=n;j++)for(int k=0;j+k<=n;k++)if(dp1[i][j][k])
            for(int w=i;w>=1;w--){
                int cnt1=sum[i-1]-sum[w-1],cnt0=i-w-cnt1;
                int jj=j-cnt0,kk=k-cnt1;
                if(jj<0||kk<0)break;
                can[w][jj][kk]=1;
            }
    mint ans=0;
    for(int i=1;i<=n+1;i++)for(int j=0;j<=n;j++)for(int k=0;j+k<=n;k++)if(can[i][j][k])
        ans+=dp2[i][j][k];
    writeln(ans.x);
}