【Codeforces Round #635 (Div. 2) E】Kaavi and Magic Spell

题目链接

点我呀

翻译

给你一个长度为n(N <= 3000)的字符串S。

一个长度为m(m<=n)的字符串T。

字符串是一个magic string当且仅当这个字符串有前缀T。

(这两个字符串都只有小写字母)

对于S, 可以把它的第一个字符删掉然后加到一开始为空串的字符串A的最前面。

也可以加到A的最后面。

可以最多操作n次。

请你求出来这样的操作序列(可以不用n次机会全操作完), 使得最后生成的A是一个magic string;

题解

tip: 观察题目, 发现要取模, 所以十有八九是计数类题目, 而计数类题目要么是排列组合, 要么

就是用DP搞, 这题的数据范围很小, 才3000, 够你开一个二维数组了, 所以得到启发, 肯定是个DP了。

设dp[i][j]表示生成字符串T(较小的那个字符串)的i到j这一段的方案数。

这里仍然有个trick, 就是把T这个字符串看成是和字符串S的长度相同的, 长度都为n, 在m+1之后可以理解为, 随便加什么

字符都能满足(也即没有限制要和T的哪个相同了)。

那么最后的答案就是 \(dp[1][m]+dp[1][m+1]+...+dp[n]\) 了。

区间DP, 从长度1开始做, 长度1对应的为dp[i][i], 也就是生成字符串t中的第i个字符的方案数。

则有初值, 对于 \(1 <= i <=m\), 若 \(s[1] == t[i]\), 那么 $dp[i][i] = 2 $(题目中有说, 只有一个字符的话, 加到左边或右边都可以)。

对于 \(m+1 <= i <= n\), 因为没有限制, 所以对于第1个元素, 不管它是啥, 加左边或加右边都行, 即 \(dp[i][i] = 2\)。

然后枚举字符串s的下一个字符, 即枚举idxs, 然后恰巧, 这个idxs也能当做我们的区间的长度(用来顺序枚举)。所以, 紧接着, 继续

枚举长度为idxs的区间(i, j)即可, 进行区间dp。

若i已经大于m了(这时不管s[idxs]是啥都能满足), 或者 \(s[idxs]==t[i]\), 则 \(dp[i][j]+=dp[i+1][j]\), 表示将s[idxs]放在左边。

若j已经大于m了, 或者 \(s[idxs]==t[j]\), 则 \(dp[i][j]+=dp[i][j-1]\), 表示将s[idxs]放在右边。

最后累加dp[1][m..n]即可。

代码

#include<bits/stdc++.h>
#define ll long long
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
using namespace std;

const int N = 3e3;
const int MOD = 998244353;

int n,m;
int dp[N+10][N+10];
char s[N+10],t[N+10];

int main(){
    #ifdef LOCAL_DEFINE
        freopen("D:\\rush.txt","r",stdin);
    #endif
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> (s+1);
    cin >> (t+1);
    n = strlen(s+1);m = strlen(t+1);
    rep1(i,1,m){
        if (s[1] == t[i]){
            dp[i][i] = 2;
        }
    }
    rep1(i,m+1,n){
        dp[i][i] = 2;
    }
    rep1(idxs,2,n){
        rep1(i,1,n){
            int j = i + idxs - 1;
            if (j > n) continue;
            if (i > m || s[idxs] == t[i]){
                dp[i][j] = (dp[i][j] + dp[i+1][j])%MOD;
            }
            if (j > m || s[idxs] == t[j]){
                dp[i][j] = (dp[i][j] + dp[i][j-1])%MOD;
            }
        }
    }
    int ans = 0;
    rep1(i,m,n){
        ans = (ans + dp[1][i])%MOD;
    }
    cout << ans << endl;
    return 0;
}