Moe's CF Life

喵哈~！各位主人，晚上好呀！咱是乃们的专属猫娘小助手，今天也要元气满满地解决问题哦！(ฅ'ω'ฅ)

今天我们要看的这道题是 Codeforces 上的 E. Preorder，一道关于完美二叉树和字符串的有趣问题。看起来有点复杂，但是只要跟着咱的思路一步一步来，就会发现它其实是一只可以轻松撸顺毛的小猫咪哦！

那么，准备好小鱼干和逗猫棒，我们开始吧！

题目大意喵

首先，我们来理解一下这道题在说什么吧，喵~

题目给了我们一个有 n 层的完美二叉树，总共有 $2^n - 1$ 个节点。这棵树的节点编号非常规律：

根节点是 1。
对于一个编号为 x 的节点，它的左孩子是 2x，右孩子是 2x+1。

树上的每个节点都有一个字符，不是 'A' 就是 'B'。

接着，题目定义了一种叫做先序遍历字符串的东西。对于一个节点 x：

如果 x 是叶子节点，它的先序遍历字符串就是它身上的那个字符 s_x。
如果 x 不是叶子节点，它的先序遍历字符串就是 s_x + 左孩子的先序遍历字符串 + 右孩子的先序遍历字符串。

这其实就是标准的树的先序遍历啦。整棵树的先序遍历字符串，就是从根节点 1 开始得到的字符串。

最关键的操作来啦！我们可以在生成先-序-遍-历-字-符-串之前，对任意一个非叶子节点 x，无限次地交换它的左、右孩子。

我们的任务是，计算一下，通过这些交换操作，我们总共能得到多少种不同的先序遍历字符串。因为答案可能很大，所以要对 998244353 取模。

解题思路大公开！

一看到这种在树上求方案数，并且子问题的解可以合并成父问题的解的题目，咱的猫猫直觉就告诉咱：这是树形DP！(๑•̀ㅂ•́)و✧

我们从下往上，也就是从叶子节点向根节点思考。

对于一个节点 u，假设它的左孩子是 l，右孩子是 r。我们想知道以 u 为根的子树能生成多少种不同的先序遍历字符串。

这取决于以 l 为根的子树和以 r 为根的子树分别能生成多少种字符串。假设 l 子树能生成 $C_l$ 种字符串，r 子树能生成 $C_r$ 种字符串。

在 u 这里，我们可以选择交换或不交换 l 和 r。

不交换：生成的字符串形式为 s_u + (l子树的某个串) + (r子树的某个串)。
交换：生成的字符串形式为 s_u + (r子树的某个串) + (l子树的某个串)。

那么，以 u 为根的子树能生成的字符串总数是多少呢？

这里有个关键点：如果 l 子树能生成的所有字符串集合，和 r 子树能生成的所有字符串集合是完全一样的，那交换 l 和 r 就不会产生任何新的字符串！就像两只一模一样的猫咪，交换位置了主人也看不出来呀~

情况一：左右子树生成的字符串集合相同 此时，交换操作是无效的。总的方案数就是从左子树的集合里选一个，再从右子树的集合里选一个，组合起来。所以总数是 $C_l \times C_r$ 。
情况二：左右子树生成的字符串集合不同 此时，对于任何一对来自左右子树的字符串 str_l 和 str_r，s_u + str_l + str_r 和 s_u + str_r + str_l 是不同的。因此，交换操作会使方案数翻倍。总数是 $2 \times C_l \times C_r$ 。

所以，我们的 DP 不仅需要计算每个子树能生成的字符串数量，还需要一个方法来判断两个子树生成的字符串集合是否相同。

直接存储和比较字符串集合太慢啦，会超时的！这时候，聪明的猫娘就会想到用字符串哈希来给每个集合一个独一无二的“身份证”。

怎么给一个字符串集合设计哈希值呢？我们可以定义一个“规范表示”。对于任意一个子树，它能生成的所有字符串中，我们选一个作为代表，比如字典序最小的那个。但找字典序最小的还是太麻烦。

一个更巧妙的方法是：

对于一个叶子节点 u，它的规范表示就是 s_u。
对于一个非叶子节点 u，我们先递归地求出它左右孩子 l 和 r 的规范表示 canon_l 和 canon_r。
比较 canon_l 和 canon_r（比如按字典序，或者按它们的哈希值）。
始终将较小的那个放在前面，较大的放在后面。比如，如果 canon_l < canon_r，那么 u 的规范表示就是 s_u + canon_l + canon_r。如果 canon_r < canon_l，那么 u 的规范表示就是 s_u + canon_r + canon_l。

这样，无论初始时 l 和 r 的位置如何，一个子树的规范表示都是唯一的！喵~ 是不是很聪明？

现在，我们只需要比较左右子树规范表示的哈希值是否相等，就可以判断它们对应的字符串集合是否相同了。为了防止哈希冲突（就像两只不同的猫咪撞到一起了！），我们可以用双哈希，增加可靠性。

总结一下我们的 DP 流程（从叶子到根，即从 i = 2^n - 1 倒序到 1）：

dp[i]：以 i 为根的子树能生成的不同字符串数量。
h[i]：以 i 为根的子树的规范表示的哈希值（用一个 pair 存双哈希值）。

状态转移：

对于叶子节点 i：
- dp[i] = 1。
- h[i] 就是字符 s_i 的哈希值。
对于非叶子节点 i（左右孩子为 l=2i, r=2i+1）：
- 比较 h[l] 和 h[r]。
- 如果 h[l] == h[r]，则 dp[i] = (dp[l] * dp[r]) % MOD。
- 如果 h[l] != h[r]，则 dp[i] = (2 * dp[l] * dp[r]) % MOD。
- 计算 h[i]：
  - 将 h[l] 和 h[r] 排序，得到 h_small 和 h_large。
  - 子树的字符串长度是固定的，可以预先计算。设子树字符串长度为 len_child。
  - h[i] = hash(s_i + 规范串_small + 规范串_large)。
  - 这个哈希值可以通过 h_small 和 h_large 计算出来： h[i] = (s_i * p^(2*len_child) + h_small * p^len_child + h_large) % M。

最终的答案就是 dp[1] 啦！

题解代码 (C++)

下面是具体的实现代码，咱加了一些注释，方便主人理解哦~

cpp

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <bit>

// The entire solution is placed within a single code block as requested.
// The solution is self-contained and can be compiled and run directly.
namespace solution {
    using namespace std;
    // 用于字符串哈希的两个模数和底数，双哈希更保险喵
    const long long M1 = 1e9 + 7;
    const long long M2 = 1e9 + 9;
    const long long P1 = 31;
    const long long P2 = 37;
    // 最终答案要对这个数取模
    const long long MOD = 998244353;

    void solve() {
        // 快速输入输出，让程序跑得像猫一样快！
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

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

        // 完美二叉树的总节点数
        int num_vertices = (1 << n) - 1;

        // 预处理哈希用的P的幂，避免重复计算
        vector<long long> p1_powers(num_vertices + 1);
        vector<long long> p2_powers(num_vertices + 1);
        p1_powers[0] = 1;
        p2_powers[0] = 1;
        for (int i = 1; i <= num_vertices; ++i) {
            p1_powers[i] = (p1_powers[i - 1] * P1) % M1;
            p2_powers[i] = (p2_powers[i - 1] * P2) % M2;
        }

        // DP数组
        // count[i]: 以i为根的子树能产生的不同字符串数量
        vector<long long> count(num_vertices + 2);
        // h1[i], h2[i]: 以i为根的子树的规范表示的双哈希值
        vector<long long> h1(num_vertices + 2);
        vector<long long> h2(num_vertices + 2);

        // 从叶子节点向上处理到根节点
        for (int i = num_vertices; i >= 1; --i) {
            // 计算当前节点在第几层（从下往上，叶子是第0层）
            // std::bit_width(i)可以快速得到i的二进制最高位是第几位，从而知道深度
            int depth = std::bit_width(static_cast<unsigned int>(i)) - 1;
            int level = n - 1 - depth;

            if (level == 0) { // Base Case: 叶子节点
                count[i] = 1;
                h1[i] = s[i - 1]; // 字符本身就是哈希值
                h2[i] = s[i - 1];
            } else { // Recursive Step: 非叶子节点
                int l = 2 * i;
                int r = 2 * i + 1;

                // 如果左右子树的规范表示哈希值完全相同
                // 那么交换它们没有意义，方案数直接相乘
                if (h1[l] == h1[r] && h2[l] == h2[r]) {
                    count[i] = (count[l] * count[r]) % MOD;
                } else {
                    // 否则，交换会产生新的字符串，方案数翻倍
                    count[i] = (2 * count[l] * count[r]) % MOD;
                }

                // 为了计算当前节点的规范哈希值，需要先对孩子们的哈希值排序
                long long h1_c1 = h1[l], h2_c1 = h2[l];
                long long h1_c2 = h1[r], h2_c2 = h2[r];
                
                // 保证 (h1_c1, h2_c1) 是较小的那个
                if (h1_c1 > h1_c2 || (h1_c1 == h1_c2 && h2_c1 > h2_c2)) {
                    swap(h1_c1, h1_c2);
                    swap(h2_c1, h2_c2);
                }

                // 计算子树先序遍历字符串的长度
                // 在第k层（从下往上）的节点，其子树的字符串长度是 2^(k)-1
                // 孩子们在 level-1 层，所以它们的字符串长度是 2^level - 1
                int len_child = (1 << level) - 1;

                // 组合哈希值：hash(s_i + C1 + C2) = s_i * p^(|C1|+|C2|) + hash(C1) * p^|C2| + hash(C2)
                // |C1| = |C2| = len_child
                // 第一个哈希
                long long term1_h1 = (1LL * s[i - 1] * p1_powers[2 * len_child]) % M1;
                long long term2_h1 = (1LL * h1_c1 * p1_powers[len_child]) % M1;
                h1[i] = (term1_h1 + term2_h1 + h1_c2) % M1;
                if (h1[i] < 0) h1[i] += M1; // C++取模可能是负数，要处理一下

                // 第二个哈希
                long long term1_h2 = (1LL * s[i - 1] * p2_powers[2 * len_child]) % M2;
                long long term2_h2 = (1LL * h2_c1 * p2_powers[len_child]) % M2;
                h2[i] = (term1_h2 + term2_h2 + h2_c2) % M2;
                if (h2[i] < 0) h2[i] += M2;
            }
        }

        cout << count[1] << endl;
    }
} // namespace solution

int main() {
    solution::solve();
    return 0;
}

题目大意喵 ​

解题思路大公开！ ​

题解代码 (C++) ​

相关知识点梳理喵 ​

题目大意喵

解题思路大公开！

题解代码 (C++)

相关知识点梳理喵