序列 - 题解

标签与难度

标签: 栈, 计数问题, 组合数学, 树形结构, 拓扑排序, 思维难度: 2100

题目大意喵~

主人你好呀，喵~ 这道题是这样的：

我们有一个长度为 $4n$ 的 01 字符串。我们需要进行 $n$ 次操作，直到把整个字符串都删光光。每次操作呢，我们都要在当前字符串里找到一个连续的子串 "0011"，然后把它删掉。

比如说，如果字符串是 "00110011"，我们可以先删掉前面的 "0011"，剩下 "0011"，再删掉它，就空啦。我们也可以先删掉后面的 "0011"，剩下 "0011"，再删掉它。

每次操作，我们都会选择一个起始位置 $i$ （从1开始计数哦）来删除 s[i...i+3]。我们要把这 $n$ 次操作所选择的起始位置 $i$ 记录下来，形成一个序列 $x_1, x_2, \dots, x_n$ 。

问题就是，总共有多少种不同的操作序列 $x$ 可以把整个字符串删空呢？答案要对 $10^9+7$ 取模哦，喵~

解题思路分析

这道题看起来是在字符串上操作，但其实核心是一个非常有趣的计数问题呢，喵！直接模拟所有可能的删除顺序肯定会超时的，所以我们需要找到一个更聪明的办法。

1. 发现嵌套结构与树

我们来观察一下删除操作的性质。在字符串 s = 00001111 中，我们唯一能做的第一步操作是删除中间的 "0011" (即原串的第3到第6个字符)，使字符串变为 "0011"。然后才能删除这个新的 "0011"。

而在 s = 00110011 中，我们可以先删除左边的 "0011"，也可以先删除右边的 "0011"。这两种选择是独立的。

这给了我们一个启发：这些 "0011" 的删除操作之间存在着依赖关系！一个 "0011" 可能“包裹”着另一个 "0011"，就像 00...[0011]...11 这样。被包裹的那个必须先被消除，外面的才能被消除。

这种嵌套的依赖关系，是不是很像一棵树（或者一个森林）的结构呀？喵~ 我们可以把每一个可以被消除的 "0011" 看作一个节点。如果节点 $A$ 对应的 "0011" 块完全包含在节点 $B$ 对应的 "0011" 块的内部，那么 $A$ 就是 $B$ 的一个孩子节点。

例如，00(0011)11 就构成了一个父子关系。00110011 则构成了两个独立的树（一个森林）。

2. 转化为拓扑排序计数

这样一来，整个问题就转化成了：我们有一个由 $n$ 个节点构成的森林，每个节点代表一次 "0011" 的删除操作。约束条件是：一个父节点必须在它的所有子节点都被删除之后才能被删除。

我们要计算的就是满足这个约束条件的操作序列有多少种。这其实就是在计算这个森林表示的偏序关系下的拓扑排序总数！

3. 组合数学大法好！

对于一个DAG（有向无环图）来说，计算拓扑排序的数量是 #P-Complete 问题，非常困难。但幸运的是，我们的图是一个森林，结构简单很多，可以用组合数学来解决，喵~

让我们先考虑一棵树 $T$ 的情况。设 $W(T)$ 是树 $T$ 的有效拓扑排序数， $|T|$ 是树 $T$ 的节点数。树根 $r$ 必须是最后一个被处理的。那么前 $|T|-1$ 个位置是留给它的子树 $C_1, C_2, \dots, C_k$ 的。我们可以从这 $|T|-1$ 个位置中，为子树 $C_1$ 分配 $|C_1|$ 个位置，有 $\binom{|T|-1}{|C_1|}$ 种方法。再为 $C_2$ 分配 $|C_2|$ 个位置，有 $\binom{|T|-1-|C_1|}{|C_2|}$ 种方法，以此类推。这其实就是一个多项式系数。所以，总的方案数递推公式是：

W(T) = \binom{|T|-1}{|C_1|, |C_2|, \dots, |C_k|} \times \prod_{i=1}^{k} W(C_i) = \frac{(|T|-1)!}{\prod_{i=1}^{k} |C_i|!} \times \prod_{i=1}^{k} W(C_i)

这个公式还是有点复杂。我们换个角度看，定义 $f(T) = \frac{W(T)}{|T|!}$ 。代入上式化简可得一个超级优美的递推式：

f(T) = \frac{1}{|T|} \prod_{i=1}^{k} f(C_i)

对于一个叶子节点 $u$ （它没有孩子）， $|T_u|=1$ ， $f(T_u) = 1$ 。递归地展开这个公式，对于任意一个节点 $u$ ，我们有 $f(T_u) = \prod_{v \in \text{subtree}(u)} \frac{1}{|T_v|}$ ，其中 $|T_v|$ 是以 $v$ 为根的子树的节点数。

如果整个结构是一个森林，有 $m$ 棵树，根分别是 $R_1, \dots, R_m$ 。总共有 $n$ 个节点。我们可以先把这 $n$ 个操作位置分配给这 $m$ 棵树，方案数是 $\binom{n}{|R_1|, \dots, |R_m|}$ 。所以总方案数是：

\text{Total} = \frac{n!}{\prod |R_i|!} \prod W(R_i) = n! \prod f(R_i)

把 $f(R_i)$ 的展开式代入，我们发现，总方案数就是：

\text{Answer} = n! \times \prod_{u \in \text{all nodes}} \frac{1}{|\text{subtree_size}(u)|}

这里的 subtree_size(u) 是以节点 $u$ 为根的子树中的节点总数。

4. 用栈来模拟建树和计算

现在问题变成了如何找到所有的节点，并计算出它们各自的子树大小。我们不需要真的建一棵树，用一个栈就可以在一次遍历中完成所有计算，是不是很神奇，喵！

我们可以遍历字符串，用一个栈来维护当前未被匹配的字符（以及它们所代表的子树信息）。

初始化答案为 ans = n!。
我们用一个栈来存放那些未被归约的字符的原始下标。
我们还需要一个数组 subtree_size，subtree_size[i] 记录了以原始位置 i 的字符为代表的（可能是归约后的）子树大小。初始时都为0。
从左到右遍历字符串 s：
- 将当前字符的下标 i 压入栈。
- 检查栈顶的四个元素对应的原始字符是否构成 "0011"。
- 如果构成了，说明我们找到了一个新的可归约块，也就是树上的一个新节点！设这四个字符的原始下标是 $i_1, i_2, i_3, i_4$ 。
- 这个新节点的子树大小就是 1 + subtree_size[i1] + subtree_size[i2] + subtree_size[i3] + subtree_size[i4]。
- 根据我们的公式，将 ans 乘上这个子树大小的逆元。
- 然后，我们将这四个元素从栈中弹出。这个新形成的、更大的块需要一个代表。一个绝妙的技巧是，让这个块“挂”在它前面那个元素的下面。也就是，把这个新块的子树大小，加到栈顶元素所代表的子树大小上。
遍历结束后，如果栈是空的，说明整个字符串都被成功归约了，ans 就是我们的答案。如果栈不为空，说明无法删空，方案数为0。

这个栈的技巧非常优雅，它在模拟归约过程的同时，动态地计算了每个节点的子树大小，并更新了最终答案。让我们用代码来实现这个思路吧！

代码实现

cpp

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= 1000000007;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 1000000007;
        base = (base * base) % 1000000007;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, 1000000007 - 2);
}

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    // 如果 n=0，空串只有一种方案（什么都不做）
    if (n == 0) {
        cout << 1 << endl;
        return;
    }

    // 1. 预计算 n!
    long long ans = 1;
    for (int i = 1; i <= n; ++i) {
        ans = (ans * i) % 1000000007;
    }

    // `active_indices` 模拟栈，存放未被归约的字符的原始下标
    vector<int> active_indices;
    // `subtree_nodes[i]` 存储以原串第 i 个字符为代表的子树的节点数
    vector<long long> subtree_nodes(4 * n, 0);

    for (int i = 0; i < 4 * n; ++i) {
        active_indices.push_back(i);

        // 循环检查，因为一次归约后可能触发新的归约
        while (active_indices.size() >= 4) {
            int size = active_indices.size();
            // 获取栈顶四个元素的原始下标
            int idx1 = active_indices[size - 4];
            int idx2 = active_indices[size - 3];
            int idx3 = active_indices[size - 2];
            int idx4 = active_indices[size - 1];

            // 检查是否构成 "0011"
            if (s[idx1] == '0' && s[idx2] == '0' && s[idx3] == '1' && s[idx4] == '1') {
                // 2. 计算新节点的子树大小
                long long current_subtree_size = 1; // 1是为自己这个新节点
                current_subtree_size += subtree_nodes[idx1];
                current_subtree_size += subtree_nodes[idx2];
                current_subtree_size += subtree_nodes[idx3];
                current_subtree_size += subtree_nodes[idx4];
                
                // 3. 更新答案，乘以 1 / |T_u|
                ans = (ans * modInverse(current_subtree_size)) % 1000000007;

                // 4. "弹出"这四个元素
                active_indices.pop_back();
                active_indices.pop_back();
                active_indices.pop_back();
                active_indices.pop_back();

                // 5. 将归约后的新块"合并"到它前面的元素上
                // 注意：这里需要检查栈是否为空，因为最外层的块归约后栈就空了
                if (!active_indices.empty()) {
                    int parent_proxy_idx = active_indices.back();
                    subtree_nodes[parent_proxy_idx] += current_subtree_size;
                }
            } else {
                // 如果栈顶不是 "0011"，就停止归约，继续遍历字符串
                break;
            }
        }
    }

    // 6. 最终检查
    if (active_indices.empty()) {
        cout << ans << endl;
    } else {
        // 如果栈不为空，说明字符串无法被完全归约
        cout << 0 << endl;
    }
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 。我们对长度为 $4n$ 的字符串进行一次遍历。在循环内部，虽然有一个 while 循环，但每次 while 循环都会使得栈的大小减小3。每个字符最多被压入栈一次，并作为归约的一部分被弹出一次。因此，总的操作次数与字符串长度成线性关系，总时间复杂度为 $O(4n)$ ，即 $O(n)$ 。
空间复杂度: $O(N)$ 。我们使用了 active_indices 向量作为栈，它在最坏情况下可能存储所有 $4n$ 个字符的下标。subtree_nodes 数组的大小也是 $4n$ 。所以，额外空间复杂度是 $O(4n)$ ，即 $O(n)$ 。

知识点总结

这道题真是一次有趣的冒险，喵！我们从一个字符串操作问题出发，一步步把它变成了：

抽象建模: 将删除操作的依赖关系建模为森林结构，这是解题的关键一步。
问题转化: 把求解不同操作序列数量的问题，转化为计算森林的拓扑排序数量。
组合计数: 利用组合数学推导出了一个优美的公式 $\text{Answer} = n! \times \prod_{u} \frac{1}{|\text{subtree\_size}(u)|}$ ，避免了复杂的动态规划。
栈的应用: 使用栈这种数据结构，非常巧妙地在一次遍历中模拟了树的构建、子树大小的计算和最终答案的累积，而无需真正地建立树的邻接表表示。

希望这篇题解能帮助到你，喵~ 如果还有不懂的地方，随时可以再来问我哦！一起加油，攻克更多的算法难题吧！

序列 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

1. 发现嵌套结构与树 ​

2. 转化为拓扑排序计数 ​

3. 组合数学大法好！ ​

4. 用栈来模拟建树和计算 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​