题解：AT_ndpc2026_c 文字列

· · 题解

题意概述：

给你三个由小写字母构成的字符串 s_1,s_2,s_3\left(1\le\left|s_1\right|,\left|s_2\right|,\left|s_3\right|\le10\right)，求长度为 n\left(1\le n\le 10^3\right) 的字符串 t 的数量模 998244353，满足 s_1,s_2,s_3 都不会出现在 t 的 子序列 中。子序列是指从原串中删除若干个字符（可以为零）后，保持原顺序得到的新字符串。

不难发现，这几个串串的长度都挺小，于是直接暴力 dp。

设 f_{i,a,b,c} 表示字符串 t 已经有了 i 个字符，第 i 个字符已经与 s_1 匹配了 a 个字符，与 s_2 匹配了 b 个字符，与 s_3 匹配了 c 个字符，的方案数。这里的 t 第 i 个字符与 s_1 匹配了 a 个字符，指 s_1 的前 a 个字符出现在 t 的前 i 个字符子序列中。

一下简称 t 的第 i 个字符为 t_i，s_1 的第 a+1 个字符为 s_{1,a+1}，s_2 的第 b+1 个字符为 s_{2,b+1}，s_3 的第 c+1 个字符为 s_{3,c+1}。

那么由 f_{i,a,b,c} 向下的转移方程很好写了，我是直接八种情况无脑分讨了：

f_{i+1,a+1,b,c}\leftarrow f_{i+1,a+1,b,c}+f_{i,a,b,c} f_{i+1,a,b+1,c}\leftarrow f_{i+1,a,b+1,c}+f_{i,a,b,c} f_{i+1,a,b,c+1}\leftarrow f_{i+1,a,b,c+1}+f_{i,a,b,c} f_{i+1,a+1,b+1,c}\leftarrow f_{i+1,a+1,b+1,c}+f_{i,a,b,c} f_{i+1,a+1,b,c+1}\leftarrow f_{i+1,a+1,b,c+1}+f_{i,a,b,c} f_{i+1,a,b+1,c+1}\leftarrow f_{i+1,a,b+1,c+1}+f_{i,a,b,c} f_{i+1,a+1,b+1,c+1}\leftarrow f_{i+1,a+1,b+1,c+1}+f_{i,a,b,c}

为了不能完整匹配到，最终答案应为 \sum\limits_{a=0}^{\left|s_1\right|-1}\sum\limits_{b=0}^{\left|s_2\right|-1}\sum\limits_{c=0}^{\left|s_3\right|-1}f_{n,a,b,c}。

代码如下：

const int N=1001,M=11,mod=998244353;
int n,cnt,l[4];
char s[4][M];
long long ans,f[N][M][M][M];
int main()
{
    n=read();
    for(int i=1;i<=3;i++) scanf("%s",s[i]+1),l[i]=strlen(s[i]+1);
    f[0][0][0][0]=1;
    for(int i=0;i<n;i++)
    {
        for(int a=0;a<l[1];a++)
        {
            for(int b=0;b<l[2];b++)
            {
                for(int c=0;c<l[3];c++)
                {
                    //不匹配s1,s2,s3
                    cnt=1;
                    if(s[1][a+1]!=s[2][b+1]) cnt++;
                    if(s[1][a+1]!=s[3][c+1]&&s[2][b+1]!=s[3][c+1]) cnt++;
                    f[i+1][a][b][c]=(f[i+1][a][b][c]+f[i][a][b][c]*(26-cnt))%mod;
                    //匹配s1，不匹配s2,s3
                    if(s[1][a+1]!=s[2][b+1]&&s[1][a+1]!=s[3][c+1])
                        f[i+1][a+1][b][c]=(f[i+1][a+1][b][c]+f[i][a][b][c])%mod;
                    //匹配s2，不匹配s1,s3
                    if(s[2][b+1]!=s[1][a+1]&&s[2][b+1]!=s[3][c+1])
                        f[i+1][a][b+1][c]=(f[i+1][a][b+1][c]+f[i][a][b][c])%mod;
                    //匹配s3，不匹配s1,s2
                    if(s[3][c+1]!=s[1][a+1]&&s[3][c+1]!=s[2][b+1])
                        f[i+1][a][b][c+1]=(f[i+1][a][b][c+1]+f[i][a][b][c])%mod;
                    //匹配s1,s2，不匹配s3
                    if(s[1][a+1]==s[2][b+1]&&s[1][a+1]!=s[3][c+1])
                        f[i+1][a+1][b+1][c]=(f[i+1][a+1][b+1][c]+f[i][a][b][c])%mod;
                    //匹配s1,s3，不匹配s2
                    if(s[1][a+1]==s[3][c+1]&&s[1][a+1]!=s[2][b+1])
                        f[i+1][a+1][b][c+1]=(f[i+1][a+1][b][c+1]+f[i][a][b][c])%mod;
                    //匹配s2,s3，不匹配s1
                    if(s[2][b+1]==s[3][c+1]&&s[2][b+1]!=s[1][a+1])
                        f[i+1][a][b+1][c+1]=(f[i+1][a][b+1][c+1]+f[i][a][b][c])%mod;
                    //匹配s1,s2,s3
                    if(s[1][a+1]==s[2][b+1]&&s[2][b+1]==s[3][c+1])
                        f[i+1][a+1][b+1][c+1]=(f[i+1][a+1][b+1][c+1]+f[i][a][b][c])%mod;
                }
            }
        }
    }
    for(int a=0;a<l[1];a++)
        for(int b=0;b<l[2];b++)
            for(int c=0;c<l[3];c++)
                ans=(ans+f[n][a][b][c])%mod;
    print(ans);
    return 0;
}