这道题有点坑人啊~
首先，它需要取模，模数是100000000；(窝在这里死了好久好久，看了别人的代码才发现这一点)
然后我发现题解中没有序列自动机的方法，于是就来一发
首先，虽然序列自动机在定义上与后缀自动机、回文自动机等听起来比较高大上的算法同属于自动机的范畴，但它仅仅是个**普及-**算法
为何？因为你不学都有可能会(逃)
自动机，就是把一个字符串通过某种关系构成一幅有向无环图，这样可以方便我们进行图上dp
序列自动机的构造方法：
设一个字符集S，nxt[i][j]表示第i个位置往后第一个j元素出现的位置；
这个nxt数组可以O(n)的求出来，可以自行验证；
for(int i=n-1;i>=0;--i){ for(int j=1;j<=26;++j) nxt[i][j]=nxt[i+1][j]; nxt[i][s[i+1]-'a'+1]=i+1; }
她能干什么事情呢？(应用)
1.判断是否是原字符串的子序列
当我们构造出nxt数组之后，可以贪心的寻找子序列；
2.求一个序列的子序列个数；(可以限定序列的长度)
我们在DAG上跑拓扑DP，f[v][j]表示从1~v寻找j个元素的方案数；
显然的：f[v][j]+=f[u][j-1];
#include <bits/stdc++.h>
#define inc(i,a,b) for(register int i=a;i<=b;i++)
#define dec(i,a,b) for(register int i=a;i>=b;i--)
using namespace std;
char s[3010];
int nxt[3010][40];
int n,m;
long long f[3010][3010];
int rudu[3010];
const int p=998244353;
queue<int> qwq;
void tp()
{
qwq.push(0);
f[0][0]=1;
while(qwq.size()){
int u=qwq.front();
qwq.pop();
inc(i,0,25){
if(!nxt[u][i]) continue;
inc(j,0,u) f[nxt[u][i]][j+1]=(f[nxt[u][i]][j+1]+f[u][j])%p;
--rudu[nxt[u][i]];
if(rudu[nxt[u][i]]==0) qwq.push(nxt[u][i]);
}
}
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);cin>>m;
dec(i,n-1,0){
inc(j,0,25) nxt[i][j]=nxt[i+1][j];
nxt[i][s[i+1]-'a']=i+1;
inc(j,0,25) if(nxt[i][j]!=0) rudu[nxt[i][j]]++;
}
tp();
long long ans=0;
inc(i,1,n) ans=(ans+f[i][m])%p;
cout<<ans%p;
}
/*
addeade
3
aa
1
*/
#### 3.求两串的公共子序列个数(就是这道题)
#include <bits/stdc++.h>
#define inc(i,a,b) for(register int i=a;i<=b;i++)
#define dec(i,a,b) for(register int i=a;i>=b;i--)
using namespace std;
char a[160],b[160],c[160];
int nxta[160][30],nxtb[160][30],nxtc[160][30];
long long f[160][160][160];
const int mod=100000000;
long long dfs(int x,int y,int z)
{
if(f[x][y][z]) return f[x][y][z];
inc(i,0,26){
if(nxta[x][i]&&nxtb[y][i]&&nxtc[z][i]){
f[x][y][z]=(f[x][y][z]+dfs(nxta[x][i],nxtb[y][i],nxtc[z][i]))%mod;
}
}
if(x||y||z) ++f[x][y][z];
return f[x][y][z]%mod;
}
int main()
{
int x,y,z;
int n;
cin>>n;
scanf("%s %s %s",a+1,b+1,c+1);
x=strlen(a+1); y=strlen(b+1); z=strlen(c+1);
dec(i,x-1,0){
inc(j,0,25) nxta[i][j]=nxta[i+1][j];
nxta[i][a[i+1]-'a']=i+1;
}
dec(i,y-1,0){
inc(j,0,25) nxtb[i][j]=nxtb[i+1][j];
nxtb[i][b[i+1]-'a']=i+1;
}
dec(i,z-1,0){
inc(j,0,25) nxtc[i][j]=nxtc[i+1][j];
nxtc[i][c[i+1]-'a']=i+1;
}
cout<<dfs(0,0,0)%mod;
}
4.求字符串的回文子序列个数
首先原串与反串都建一遍；
就相当于从左右端点向中间跑自动机；
显然：x+y<=n+1才会合法；
但要注意，我们只能统计偶数长度的字符串，而不能统计奇数个数的字符串；
因为我们永远都是两个两个地串；
long long Dfs(int x,int y){
if(f[x][y]) return f[x][y];
for(int i=1;i<=a;++i)
if(nxt1[x][i]&&nxt2[y][i]){
if(nxt1[x][i]+nxt2[y][i]>n+1) continue;
if(nxt1[x][i]+nxt2[y][i]<n+1) f[x][y]++;
f[x][y]=(f[x][y]+Dfs(nxt1[x][i],nxt2[y][i]))%mod;
}
return ++f[x][y];
}