我将会给你一道题，讲解这道题的最简单解法，讲解的时候应当保证你使用的不同符号使用尽可能少，以及最后给...

Question

我将会给你一道题，讲解这道题的最简单解法，讲解的时候应当保证你使用的不同符号使用尽可能少，以及最后给出本题尽可能简洁实现的完整代码（为了 OI 选手可读性，允许在不影响正确性的情况下牺牲一部分运行效率），另外还请总结所有的关键结论或关键步骤（这一点，忽略细枝末节的地方）。

Answer 1

可以用 一个二维区间 DP，时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。

关键是先把弦图变成一棵有序三叉树，再利用只有两种颜色，将三叉合并变成二叉合并。

一、把弦图变成有序三叉树

先区分两张图：题目中的图以“弦”为顶点；下面我们直接在几何图形上，把交点作为顶点，把弦分割成线段作为边。

对于一个合法方案，弦的相交图是一棵树，所以恰有 $n-1$ 对弦相交。也不可能有三条弦交于同一点，否则它们会形成三角形。

因此，分割后的几何图形：

有 $2n+(n-1)=3n-1$ 个顶点。
有 $n+2(n-1)=3n-2$ 条边，因为每个交点把两条弦各多分出一条边。
是连通的。

顶点数比边数多一，所以它仍然是一棵树。

现在，以圆周上的点 $1$ 为根。每个交点的度数为 $4$ ，去掉通向父亲的方向后，恰好有三个孩子。三个孩子按照圆周顺序排列，称为左、中、右。

删去根叶子 $1$ 及其连接边，剩下的就是一棵有序三叉树，叶子依次为：

2,3,\ldots,2n.

在每个交点处，原来的两条弦如何穿过，是确定的：

通向父亲的边与中间孩子连通，左孩子与右孩子连通。

此外，每棵子树的叶子都构成一个连续区间，这就有了区间 DP 的基础。

这个分解是可逆的：按上述规则贯通各条边，就得到叶子的配对。树上的两条贯通路径不可能相交两次，否则会产生环；它们相交恰好对应端点交错，因此改画成直弦后，相交关系不变。分解始终从根弦遇到的第一个交点开始，所以也不会重复计数。

二、利用颜色，把三叉树变成二叉树

1. 一棵子树只需要记录一个颜色

考虑三叉树中的任意一棵子树。

它只有一条边通向外面，所以恰好有一个叶子的配对尚未在子树内部完成，其余叶子都已经红蓝配对。把这个尚未配对的叶子的颜色，称为这棵子树的颜色。

将红色记为 $+1$ ，蓝色记为 $-1$ 。

于是：

红色子树的叶子之和为 $+1$ ，蓝色子树的叶子之和为 $-1$ 。

因此不需要另外开一维记录颜色，区间和已经决定了颜色。

2. 每次三叉合并，都有唯一的二叉拆法

根据交点处的连接方式：

左、右孩子必须异色；中间孩子的颜色，就是合并后子树的颜色。

例如，合并后的颜色为红色时，三个孩子的颜色只能是：

text
R R B
B R R

蓝色的情况完全对称。

注意：三个孩子中，恰好有一对相邻的同色孩子。

先合并这两个同色孩子，再与另一个孩子合并：

text
R R B  →  (R R) B
B R R  →  B (R R)

这样，一个三叉结点就被唯一地拆成了两个二叉结点。

其中，临时合并两个同色孩子得到的结点，叶子之和为 $+2$ 或 $-2$ ；原来的三叉结点，叶子之和仍为 $+1$ 或 $-1$ 。

所以问题变成了：

统计叶子依次为 $2,3,\ldots,2n$ 的有序满二叉树，要求每个结点对应的子树叶子之和，绝对值都只能是 $1$ 或 $2$ 。

这里“满二叉树”指每个非叶结点恰好有两个孩子。

3. 为什么这个限制也足够？

假设每棵子树的和都只能是 $1,-1,2,-2$ 。

如果一个结点的和为 $2$ ，那么两个孩子的和只能是：

2=1+1.

如果一个结点的和为 $1$ ，那么只能是：

1=2+(-1) \quad\text{或}\quad 1=(-1)+2.

负数的情况完全对称。

这正好对应上面的：

text
(R R) B
B (R R)

因此，将和的绝对值为 $2$ 的结点并入父亲，就能唯一恢复合法的三叉结点。

也就是说，三叉树与满足上述区间和限制的二叉树一一对应。

三、区间 DP

设：

f[l][r]

表示以区间 $[l,r]$ 为叶子的、满足上述限制的二叉树数量。

用 $p$ 表示颜色数值的前缀和，则区间和为：

p[r]-p[l-1].

初始状态

单个叶子只有一种结构：

f[i][i]=1.

转移

如果区间和的绝对值不是 $1$ 或 $2$ ，这个区间不可能成为一棵合法子树：

f[l][r]=0.

否则，枚举根结点的左右子树分界：

\boxed{ f[l][r]=\sum_{k=l}^{r-1}f[l][k]\cdot f[k+1][r] }

不需要再判断左右孩子的颜色。

因为不合法的子区间已经是 $0$ ；而只要父亲和两个孩子的区间和都属于 $1,-1,2,-2$ ，就必然符合上一节列出的合法合并方式。

最终答案

我们固定把点 $1$ 当作根，所以答案是：

\boxed{f[2][2n]}.

全部点的颜色数值之和为 $0$ ，因此区间 $[2,2n]$ 的和一定与点 $1$ 异号，最后剩下的那个未配对点恰好可以与点 $1$ 配对。

固定点 $1$ 只是为了唯一地分解方案，不需要乘或除任何系数。

共有 $O(n^2)$ 个区间，每个区间枚举 $O(n)$ 个分界，故时间复杂度为 $O(n^3)$ ，空间复杂度为 $O(n^2)$ 。

四、完整代码

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

const int MOD = 998244353;
int f[1005][1005], p[1005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    int m = 2 * n;
    s = " " + s;

    for (int i = 1; i <= m; ++i) {
        p[i] = p[i - 1] + (s[i] == 'R' ? 1 : -1);
        f[i][i] = 1;
    }

    // 固定点 1 为根，只计算区间 [2, m] 内的状态。
    for (int len = 2; len < m; ++len) {
        for (int l = 2, r = l + len - 1; r <= m; ++l, ++r) {
            int d = abs(p[r] - p[l - 1]);
            if (d == 0 || d > 2) continue;

            for (int k = l; k < r; ++k) {
                f[l][r] = (f[l][r]
                    + 1LL * f[l][k] * f[k + 1][r]) % MOD;
            }
        }
    }

    cout << f[2][m] << '\n';
    return 0;
}

关键结论总结

将实际交点作为顶点后，合法弦图仍然是一棵树。 固定点 $1$ 为根，可以得到叶子顺序固定的有序三叉树。
每棵三叉子树恰好留下一个未配对端点。 所以红蓝数量差为 $+1$ 或 $-1$ ，颜色不需要额外记录。
交点的左右孩子必须异色。 三个孩子中相邻的同色对唯一，先合并它们，就得到一一对应的二叉树；所有子树的颜色和只能为 $\pm1,\pm2$ 。
最终只需普通的区间二分转移。 区间和不满足限制就置零，否则计算 $f[l][r]=\sum f[l][k]f[k+1][r],$ 答案为 $f[2][2n]$ 。