CodeForces-1337E Kaavi and Magic Spell

传送门：CodeForces-1337E

思路分析

dp[l][r]表示匹配T串[l,r]区间的方案数
S串依次插入，假如插入的是第i和字符
那么会形成区间长度为i，枚举左右端点

1. s[i]=t[l],表明s[i]可以插入到[l+1,r]的左边组成[l,r]
2. s[i]=t[r],表明s[i]可以插入到[l,r-1]的右边组成[l,r]

最后答案就是dp[1][i]$(i>=m)$的和

样例输入

abab
ba

样例输出

12

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int mod=998244353;
const int N=3333;

char s[N],t[N];
int dp[N][N];

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    cin>>s+1>>t+1;
    int n=strlen(s+1);
    int m=strlen(t+1);
    for(int i=1; i<=n; i++)    if(t[i]==s[1] || i>m) dp[i][i]=2; //第一个字符和大于m的字符放左放右都可以
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            if(s[len]==t[l] || l>m) dp[l][r]=(dp[l][r]+dp[l+1][r])%mod;
            if(s[len]==t[r] || r>m) dp[l][r]=(dp[l][r]+dp[l][r-1])%mod;
        }
    }
    int ans=0;
    for(int i=m;i<=n;i++) ans=(ans+dp[1][i])%mod;
    cout<<ans<<endl;
    






    return 0;
}