35. CF-Kaavi and Magic Spell

链接

这个区间dp的状态设计很巧妙。dp[i][j] 表示用 \(s\) 的长度为 \(j-i+1\) 的前缀组成 \([t_i\cdots t_j]\) 的子串方案数。

然后转移就是普通的区间dp的转移了。

初始化的时候根据题意，第一个放进去的也是算两种方法的，所以都初始化为 \(2\)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 3e3 + 5;
const ll mod = 998244353;
ll dp[maxn][maxn];
void solve() {
    string s, t;
    cin >> s >> t;
    int m = s.length(), n = t.length();
    for (int i = 0; i < n; ++i)
        dp[i][i] = 2 * (s[0] == t[i]);
    for (int i = n; i < m; ++i) dp[i][i] = 2;
    for (int len = 2; len <= m; ++len) {
        for (int i = 0; i <= m - len; ++i) {
            int j = i + len - 1;
            if (i >= n || t[i] == s[len - 1])
                (dp[i][j] += dp[i + 1][j]) %= mod;
            if (j >= n || t[j] == s[len - 1])
                (dp[i][j] += dp[i][j - 1]) %= mod;
        }
    }
    ll ans = 0;
    for (int i = n - 1; i < m; ++i)
        (ans += dp[0][i]) %= mod;
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}