P8256

Little_Cake_qwq · 2026-10-20 20:05:13 · 题解

为啥全是正着做的啊。倒着做不应该更好想吗？

如果我们考虑倒着做，那么删前缀操作就没有用了，就只有删后缀了。但是倒着做会先遇见 -，那么就需要前面的数去填了。考虑 DP，设 f_{i,j,k} 表示处理到 S_i\cdots S_n，对应到 T_j\cdots t_m，还需要补 k 个 - 的答案。

转移是简单的：

• 如果 S_i 为 -，考虑它填前缀或是后缀：f_{i,j,k}\leftarrow f_{i+1,j,k}+f_{i+1,j,k-1}；
• 否则，如果还需要填 -，就填：f_{i,j,k}\leftarrow f_{i+1,j,k+1}（注意这里需要 j\neq 1）；否则就考虑对应：f_{i,j,k}\leftarrow f_{i+1,j+1,k}。

统计答案的话，考虑到 S_i\cdots S_n 恰好对应完 T_1\cdots T_m，前面的 - 个数为 cnt，那么这 cnt 可以随便操作：答案加上 2^{cnt}\times f_{i,1,0}。

:::success[AC code]

const int N = 408;
const int p = 1e9 + 7;
int n, m;
string s, t;
int f[N][N][N];
void solve() {
    read(n), read(m);
    read(s), read(t);
    s = " " + s;
    t = " " + t;
    rep(i,1,n+1) rep(j,1,m+1) rep(k,0,n) f[i][j][k] = 0;
    f[n+1][m+1][0] = 1;
    req(i,n,1) req(j,m+1,1) rep(k,0,n-m) {
        if(s[i] == '-') {
            if(k > 0) f[i][j][k] = (f[i+1][j][k-1] + f[i+1][j][k]) % p; //
            else f[i][j][k] = f[i+1][j][k];
        }
        else {
            if(j != 1) f[i][j][k] = f[i+1][j][k+1];
            if(k == 0 && j <= m && s[i] == t[j]) f[i][j][k] = (f[i][j][k] + f[i+1][j+1][k]) % p;
        }
//      cout << i << " " << j << " " << k << ":" << f[i][j][k] << "\n";
    }
    ll ans = 0;
    ll pw = 1, cnt = 0;
    rep(i,1,n) {
        if(s[i] == '-') cnt++, pw = pw * 2 % p;
        else ans = (ans + f[i][1][0] * pw % p) % p;
    }
//  if(cnt * 2 != n - m) ans = 0; 
    cout << ans << "\n";
}
int main()
{
//  freopen("string.in", "r", stdin);
//  freopen("string.out", "w", stdout);
    int T; read(T);
    while(T--) solve();
    return 0;
}

:::