[CF1499E] Chaotic Merge

[CF1499E] Chaotic Merge - dp

Description

给定两个仅由小写字母组成的字符串 (x) 和 (y)。如果一个序列仅包含 (|x|) 个 (0) 和 (|y|) 个 (1)，则称这个序列为合并序列。若一个字符串任意两个相邻位置上的字符都不同，则我们称该字符串是混乱的。定义 (f(l_1,r_1,l_2,r_2)) 表示能从 (x) 的子串 (x[l_1,r_1]) 和 (y) 的子串 (y[l_2,r_2]) 生成混乱的字符串的不同的合并序列的数量，要求子串非空。求 (sum limits_{1 le l_1 le r_1 le |x| , 1 le l_2 le r_2 le |y|} f(l_1, r_1, l_2, r_2))

Solution

先不考虑选子串，先考虑整个串，设 (f[i][j][0/1]) 表示取了 (x[1..i], y[1..j]) 进行合并，最后一个字符是 (x[i]) 还是 (y[j])，此时的方案数是多少

现在把子串的问题带进来，右端点实际上已经包含在我们的状态中了，所以我们实际需要考虑的是左端点

考虑在先前的版本上做点修改，状态设计不变，对每个状态，额外引入一个从这里开始一个新的串（即一边长度为 (1)）的方案数

细节需要调教一下

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1005;
const int mod = 998244353;

int f[N][N][2], fx[N], fy[N], n, m;

string x, y;

signed main()
{
    ios::sync_with_stdio(false);
    cin >> x >> y;
    x = " " + x;
    y = " " + y;
    string &a = x;
    string &b = y;

    n = x.length() - 1;
    m = y.length() - 1;

    int ans = 0;

    for (int i = 1; i <= n; i++)
    {
        if (a[i] != a[i - 1])
            f[i][0][0] = f[i - 1][0][0] + 1;
        else
            f[i][0][0] = 1;
    }

    for (int j = 1; j <= m; j++)
    {
        if (b[j] != b[j - 1])
            f[0][j][1] = f[0][j - 1][1] + 1;
        else
            f[0][j][1] = 1;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i > 1 && a[i] != a[i - 1])
                f[i][j][0] += f[i - 1][j][0];
            if (i > 1 && a[i] != b[j])
                f[i][j][0] += f[i - 1][j][1];
            if (j > 1 && a[i] != b[j])
                f[i][j][1] += f[i][j - 1][0];
            if (j > 1 && b[j] != b[j - 1])
                f[i][j][1] += f[i][j - 1][1];
            if (a[i] != b[j])
            {
                f[i][j][0] += f[0][j][1];
                f[i][j][1] += f[i][0][0];
            }
            f[i][j][0] %= mod;
            f[i][j][1] %= mod;
            ans += f[i][j][0];
            ans += f[i][j][1];
            ans %= mod;
        }
    }
    cout << ans << endl;
}