CF1336C Kaavi and Magic Spell

题意

给一个长度为 $n$ 的字符串 $S$ 和一个长度为 $m$ 的字符串$T$ ，$1\le m\le n$，然后开始有一个空串 $A$，接下来可对 $S$ 串进行 $n4 次操作:

把S的首个字符添加到A的开头然后删掉
把S的首个字符添加到A的尾端然后删掉

问在操作过程中使得 $A$ 的前 $m$ 个字符为 $T$（也就是前缀为 $T$）的情况共有多少？

长度不同或者是操作序列中有某个地方不同可视为是不同情况。

我们先让 $T$ 的长度和 $S$ 相同，在多处来的那 $m+1,m+2,\cdots,n$ 那几位上，钦定它和 $S$ 中所有元素都“相等”，因为在这些位置上我们可以取任意值

设计状态：$f(l,r)$ 表示的是满足 $\forall l\le i\le r,S_i=T_i$ 能构造出多少操作序列

那么假设我们在删除 $S_i$ 并把它往 $A$ 里添加，此时 $A$ 中一定有了 $i-1$ 个元素

考虑 $f(l,r),r-l+1=i$ 可以由什么状态转移而来

$S_i=T_l$，则可以把 $S_i$ 添加到这个 $[l+1,r]$ 区间的前面，构成 $[l,r]$，就是 $f(l,r)+=f(l+1,r)$
$S_i=T_r$，这和上面就一样了，$f(l,r)+=f(l,r+1)$

基本已经完成了，现在考虑初始状态和答案

$f(i,i)=2[S_i=T_i]$，就是说一种方法是把 $S_1$ 从前面添加到 $A$ 的第一个元素，一种是从后面添加，虽然结果一样，但是题目要求这是两种不同方式

长度不同算不同情况，这也说明了不一定要操作 $n$ 次，只要操作 $i,m\le i\le n$ 次就行了

所以答案是 $\sum_{i=m}^{n}f(1,i)$

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<map>

#include<iomanip>

#include<cstring>

#define reg register

#define EN std::puts("")

#define LL long long

inline int read(){

	register int x=0;register int y=1;

	register char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

#define mod 998244353

char s[3006],t[3006];

int f[3006][3006];

int main(){

	std::scanf("%s",s+1);std::scanf("%s",t+1);

	int n=std::strlen(s+1),m=std::strlen(t+1);

	for(reg int i=1;i<=m;i++) f[i][i]=(s[1]==t[i])<<1;

	for(reg int i=m+1;i<=n;i++) f[i][i]=2;

	for(reg int i=2,len=2;i<=n;i++,len++){

		for(reg int l=1,r=len;r<=n;l++,r++){

			if(l>m||s[i]==t[l]) f[l][r]+=f[l+1][r],f[l][r]%=mod;

			if(r>m||s[i]==t[r]) f[l][r]+=f[l][r-1],f[l][r]%=mod;

		}

	}

	int ans=0;

	for(reg int i=m;i<=n;i++) ans=(ans+f[1][i])%mod;

	std::printf("%d",ans);

	return 0;

}