agc046D

tzc_wk · 2023-05-08 08:51:58 · 题解

思路挺自然的一道 agc。

首先发现删除完字符后的状态可以用一个三元组 (i,j,k) 表示，其中 i 表示删除完之后只剩 [i+1,n] 的后缀，j 表示可以在后面插入 j 个 0，k 表示可以在后面插入 k 个 1，显然不同的三元组能够得到的串是不同的，而一组三元组可以得到的串的个数可以 DP 求解，具体来说，倒着 DP，同时为了防止算重，我们强制要求 1 的后面只能添加 0，0 的后面只能添加 1，这样转移是 O(1) 的，具体实现见代码。

接下来考虑哪些三元组 (i,j,k) 可以得到。考虑正着 DP，那么发现每次有两种选择：

• 从 s_{i+1},s_{i+2} 中保留一个，删除一个
• 从保留的字符中拿出一个 s_{i+1}\oplus 1，插在开头，然后删除这个 s_{i+1}\oplus 1 同时保留 s_{i+1}。

转移同样可以 O(1)，总复杂度 O(n^3)。

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
void add(int &x,int v){((x+=v)>=MOD)&&(x-=MOD);}
int n,ok[305][305][305],dp[305][305][305],res;
char s[305];
int main(){
    scanf("%s",s+1);n=strlen(s+1);ok[0][0][0]=1;
    for(int i=1;i<=n;i++)for(int j=n;~j;j--)for(int k=n;~k;k--){
        ok[i][j][k]|=ok[i-1][j][k];
        ok[i][j][k]|=ok[i][j+1][k];
        ok[i][j][k]|=ok[i][j][k+1];
        if(j&&i>=2&&(s[i]=='0'||s[i-1]=='0'))ok[i][j][k]|=ok[i-2][j-1][k];
        if(k&&i>=2&&(s[i]=='1'||s[i-1]=='1'))ok[i][j][k]|=ok[i-2][j][k-1];
        if(j&&s[i]=='0')ok[i][j][k]|=ok[i-1][j-1][k+1];
        if(k&&s[i]=='1')ok[i][j][k]|=ok[i-1][j+1][k-1];
    }
    dp[n][0][0]=1;
    for(int i=n;i;i--)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++){
        add(dp[i-1][j][k],dp[i][j][k]);
        if(s[i]=='0')add(dp[i][j][k+1],dp[i][j][k]);
        if(s[i]=='1')add(dp[i][j+1][k],dp[i][j][k]);
    }
    for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)
        if(ok[i][j][k])add(res,dp[i][j][k]);
    add(res,MOD-1);printf("%d\n",res);
    return 0;
}