GZY的博客

CF1499E Chaotic Merge 题解

 题解  887  

定义 $dp(i,j,0)$ 表示：生成出的混乱的字符串中，$x$ 串和 $y$ 串都出现过字符，且最后一个来自 $x$ 串的字符是 $x_i$，最后一个来自 $y$ 串的字符是 $y_j$，并且这个混乱的字符串最后一个字符来自 $x$ 串的混乱字符串数量。

定义 $dp(i,j,1)$ 表示：（前面同上）……并且这个混乱的字符串最后一个字符来自 $y$ 串的混乱字符串数量。 $$ ans=\sum_{i=1}^n\sum_{j=1}^mdp(i,j,0)+dp(i,j,1) $$ 考虑 $dp(i,j,0)$ 的转移，$dp(i,j,1)$ 同理。

当前状态是 $dp(i,j,0)$，这代表着合并字符串最后一个字符一定是 $x_i$，去掉 $x_i$ 之后，若还有来自 $x$ 串的字符，则最大的一定是 $x_{i-1}$，所以 $dp(i,j,0)$ 一定会从 $dp(i-1,j,0)$ 或 $dp(i-1,j,1)$ 转移。

来自考虑生成串前一个字符是什么：

  • 如果前一个字符也来自 $x$ 串，则生成串前一个字符一定是 $x_{i-1}$；

    为了保证混乱，只有在 $x_{i}\neq x_{i-1}$ 进行转移，$dp(i,j,0)\gets dp(i,j,0)+dp(i-1,j,0)$。

  • 如果前一个字符来自 $y$ 串，则生成串前一个字符一定是 $y_{j}$；

    为了保证混乱，只有在 $x_i\neq y_j$ 进行转移，$dp(i,j,0)\gets dp(i,j,0)+dp(i-1,j,1)$

只有这些情况吗？考虑 $dp(i,j,0)$ 去掉 $x_i$ 之后，没有来自 $x$ 的字符了，即 $x_i$ 是生成串中唯一来自 $x$ 的字符，删掉则生成串只由 $y$ 组成了，注意到 $dp$ 的定义中，不允许生成串由单独 $x$ 或 $y$ 组成，所以这种情况无法通过 $dp$ 数组推得。

考虑预处理 （方式自己想后面再将）：

  • $fx(i)$ 表示生成串只由 $x$ 串组成，且后一个字符是 $x_i$ ，生成的混乱字符串数量。

  • $fy(i)$ 表示生成串只由 $y$ 串组成，且后一个字符是 $y_i$ ，生成的混乱字符串数量。

我们可以通过他俩来求得上面 $dp(i,j,0)$ 转移中少考虑的情况：

如果 $x_i\neq y_j$ ，则 $dp(i,j,0)\gets dp(i,j,0)+fy(j)$，代表着 $dp(i,j,0)$ 中只有最后一个字符来自 $x$ 串的情况。

关于预处理 $fx(i)$：

  • 如果 $x_i\neq x_{i-1}$，则所有 $fx(i-1)$ 的串都可以加上 $x_i$，当然也可以只由 $x_i$ 一个字符组成， $fx(i)\gets fx(i-1)+1$；
  • 如果 $x_i= x_{i-1}$，则生成串只能有 $x_i$ 一个字符，再往前多选一个都不行， $fx(i)\gets 1$；

$fy$ 同理。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include<bits/stdc++.h>
using namespace std;
const int N=1010,p=998244353;
int dp[N][N][2],n,m,fx[N],fy[N],ans;
char x[N],y[N];
int main(){
    cin>>(x+1)>>(y+1);
    int n=strlen(x+1),m=strlen(y+1);
    for(int i=1;i<=n;i++) (x[i]!=x[i-1])?fx[i]=fx[i-1]+1:fx[i]=1;
    for(int i=1;i<=m;i++) (y[i]!=y[i-1])?fy[i]=fy[i-1]+1:fy[i]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            //求dp[i][j][0]
            if(x[i]!=y[j])dp[i][j][0]+=fy[j],dp[i][j][0]%=p;

            if(x[i-1]!=x[i]) dp[i][j][0]+=dp[i-1][j][0],dp[i][j][0]%=p;
            if(y[j]!=x[i]) dp[i][j][0]+=dp[i-1][j][1],dp[i][j][0]%=p;

            //求dp[i][j][1]
            if(x[i]!=y[j]) dp[i][j][1]+=fx[i],dp[i][j][1]%=p;
            
            if(x[i]!=y[j]) dp[i][j][1]+=dp[i][j-1][0],dp[i][j][1]%=p;
            if(y[j-1]!=y[j]) dp[i][j][1]+=dp[i][j-1][1],dp[i][j][1]%=p;
            
            ans+=(dp[i][j][0]+dp[i][j][1])%p;ans%=p;
        }
    }
    cout<<ans<<'\n';
}