2024年CCPC网络赛 D题个人理解
放一个传送门
https://codeforces.com/gym/105336
主要思路
两个串的长度都是100，但是根据题目给出的还原方式，最终还原出来的串长大概在 2 100 2^{100} 2100 左右，而还原的次数最多 100 次。所以我们应该把目标放在，计算每一次还原后，目标串的字串分别有多少。具体写法请看代码（个人蒟蒻代码，轻点喷）
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const ll M = 1e6 + 10;
const ll inf = 1e9 + 5;
const ll P = (ll)998244353;string s, t;int ns, nt;//s串长度，t串长度
ll dp[110][110][110];//[k][i][j] 【第k次操作】【t字串的左边界】【t字串的右边界】
ll temp[110][110];//将新加入的字母，合并到左边后的集合void solve()
{cin >> s >> t;ns = s.size();nt = t.size();s = '#' + s;t = '#' + t;for (int k = 1; k <= ns; k++){//先初始化此轮左边集合for (int i = 1; i <= nt; i++){for (int j = i; j <= nt; j++){temp[i][j] = dp[k - 1][i][j];}}//将中间字母合并到左集合后，更新此集合for (int i = 1; i <= nt; i++){if (s[k] == t[i]){temp[i][i]++;//自己单独for (int j = i + 1; j <= nt; j++){//例如：中间"a"的出现下，要新增"b"数量个"ab"给temp集合temp[i][j] += dp[k - 1][i + 1][j];temp[i][j] %= P;}}}//大集合先加上左边的和右边的分别单独贡献for (int i = 1; i <= nt; i++){for (int j = i; j <= nt; j++){dp[k][i][j] = (dp[k - 1][i][j] + temp[i][j]) % P;}}//再考虑左右搭配的贡献for (int i = 1; i <= nt; i++){for (int j = i + 1; j <= nt; j++){for (int q = i; q < j; q++){dp[k][i][j] += (dp[k - 1][i][q] * temp[q + 1][j]) % P;dp[k][i][j] %= P;}}}}cout << dp[ns][1][nt] % P << '\n';
}int main()
{std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T = 1;//cin >> T;while (T--)solve();return 0;
}