【题解】Kaavi and Magic Spell 区间 dp+处理 CF1336C ——quhengyi11

传送门

题目大意

给两个串 $S$和 $T$，每次操作可以将 $S$的第一个字符移动到新字符串 $D$的最左边或者最右边，求有多少种操作序列 (序列长小于等于 $S$的长度) 使得 $T$是 $D$的一个前缀。

题解

先思考一个更简单的模型。求 $T=D$的方案数

设 $S$的长度是 $n$，$T$的长度为 $m$，则操作序列长度显然为 $m$，即 $S[1..m]$被操作 (废话)

设 $f[i][j]$表示 $T[i..j]$由 $S[1..(j-i+1)]$操作而来的方案数，显然可以写出如下转移方程

$$f[i][j] += f[i+1][j] (S[j-i+1]==T[i])$$
$$f[i][j] += f[i][j-1] (S[j-i+1]==T[j])$$

回到原题，如何处理前缀这个事情呢？

我们可以将 $T[(m+1)..n]$全部塞上通配符 $’?’$，然后略微改变一下上面的转移条件，答案即 $\sum_{i=m}^nf[1][i]$

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define mod 998244353
#define ll long long
#define F first
#define S second
#define mp(i, j) std::make_pair(i, j)
#define ls t[u][0]
#define rs t[u][1]
#define Re register
#define inf 1e9
#define upn 100000
#define pb(x) push_back(x)
#define N 3005
#define pi std::pair<int, int>
ll read ()
{
    Re char ch = getchar();
    Re ll ret = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) {ret = ret * 10 + ch - '0'; ch = getchar();}
    return ret;
}
struct edge {
    int v, w, nxt;
//    friend bool operator < (edge x, edge y) {return x.w < y.w;}
}e[N << 1];
int tot, head[N];
void addedge (int u, int v, int w) { e[++tot] = (edge) {v, w, head[u]}; head[u] = tot; }
char s[N], t[N];
ll ans, f[N][N];
int main ()
{
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    int n = strlen(s + 1), m = strlen(t + 1);
    fo (i, m + 1, n) t[i] = '?';
    fo (i, 1, n) f[i][i] = (s[1] == t[i] || i > m) ? 2 : 0;
    fo (now, 2, n)
        fo (i, 1, n)
        {
            int j = i + now - 1;
            if (j > n) break;
            if (t[i] == '?' || s[now] == t[i])
                (f[i][j] += f[i + 1][j]) %= mod;
            if (t[j] == '?' || s[now] == t[j])
                (f[i][j] += f[i][j - 1]) %= mod;
        }
    fo (i, m, n) ans = (ans + f[1][i]) % mod;
    printf("%lld", ans);
}