题目概述

CF1499E

解题报告

这道题想法不难，但是实现的时候很注重细节。

首先我们考虑DP $f_{i,j,0/1}$ 表示第一个字符串取到了 $i$ ，第二个字符串取到了 $j$ ，且最后一个取了 $i/j$ 的方案数，那么这样我们就可以求出取 $x[1,i],y[1,j]$ 的方案数。

但是题目中要求的是所有子串，不难想到，我们将 $f_{i,j,0/1}$ 所有位置都给上初值，这样就可以求出所有第一个字符串以 $i$ 结尾，第二个字符串以 $j$ 结尾的方案数了。

但是问题就出现在这个初值上，如果生硬的将所有 $f_{i,j,0/1}$ 都赋值为 $1$ ，就会出现取了空串的问题，导致答案不对。因此，比较清晰的处理方法是再给DP添加两个维度：

$f_{i,j,0/1,0/1,0/1}$ 表示第一个字符串以 $i$ 结尾，第二个字符串以 $j$ 结尾，最后一个取了 $i/j$ ，$i$ 是否被取了，$j$ 是否被取了的方案数。

如果以 $(i,j)$ 为选取的起点，那么对应的初值就是 $f_{i,j-1,0,1,0}=f_{i-1,j,1,0,1}=1$ 。

然后做DP就行了，最后统计答案的时候只统计 $f_{i,j,0/1,1,1}$ 的状态就可以避免取到空串。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000,MOD=998244353;

int n,m,f[maxn+5][maxn+5][2][2][2],ans;char s[2][maxn+5];

#define ADD(x,y) (((x)+(y))%MOD)
inline void AMOD(int &x,int y) {if ((x+=y)>=MOD) x-=MOD;}
int main(){
    scanf("%s%s",s[0]+1,s[1]+1);n=strlen(s[0]+1);m=strlen(s[1]+1);
    for (int i=0;i<=n;i++)
        for (int j=0;j<=m;j++){
            if (i) f[i][j][0][1][0]=1;if (j) f[i][j][1][0][1]=1;
            if (i && s[0][i]!=s[0][i-1]) AMOD(f[i][j][0][1][0],f[i-1][j][0][1][0]);
            if (j && s[1][j]!=s[1][j-1]) AMOD(f[i][j][1][0][1],f[i][j-1][1][0][1]);
            if (i && s[0][i]!=s[0][i-1]) AMOD(f[i][j][0][1][1],f[i-1][j][0][1][1]);
            if (i && s[0][i]!=s[1][j]) AMOD(f[i][j][0][1][1],ADD(f[i-1][j][1][1][1],f[i-1][j][1][0][1]));
            if (j && s[1][j]!=s[0][i]) AMOD(f[i][j][1][1][1],ADD(f[i][j-1][0][1][1],f[i][j-1][0][1][0]));
            if (j && s[1][j]!=s[1][j-1]) AMOD(f[i][j][1][1][1],f[i][j-1][1][1][1]);
            AMOD(ans,ADD(f[i][j][0][1][1],f[i][j][1][1][1]));
        }
    printf("%d\n",ans);return 0;
}