【Codeforces】1671E Preorder 题解

题目大意

$n\ (1 \le n \le 18)$，定义一个树的字符编号为：该节点的字符编号 + 左子树的字符编号 + 右子树的编号（叶子节点的字符编号就是它本身的编号）。

而你可以随意交换任意个节点的左右子树。

给定一个树的初始字符编号，求一共可以产生不同的字符编号的数量（对 $998244353$ 取模）。

题目链接

思路

设 $f[x]$ 为子树 $x$ 可以产生的方案数，它的子节点编号分别为 $f[x \cdot 2],\ f[x \cdot 2 + 1]$。根据乘法原理，$f[x] = f[x \cdot 2] \cdot f[x \cdot 2 + 1]$。

那么接下来我们考虑交换这两个子树。假如两个子树不完全相同，那么

$$f[x] = 2 \cdot f[x \cdot 2] \cdot f[x \cdot 2 + 1]$$

如果交换能使方案数增加，那就意味着两个子树的构造不同。比如这两个子树 $BAB, BBA$，它们的根节点都是 $B$，子节点虽然排序不同，但由于我们可以随便交换，所以会产生重复，所以其实它们本质上构造是相同的。

那么我们如何判断是否相同？我们在递归的时候，记录 $x$ 的节点的字符编号 $s[x]$，并且，我们让编码小的那一个子树作为左子树。这样，假如两个子树的构造相同，那么它们的字符编号也会相同，这样就可以判断了。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int maxN = 1 << 18;
const long long Mod = 998244353;

int n;
string s[maxN], t;
long long f[maxN];

void dfs(int x)
{
    int l = x << 1, r = x << 1 | 1;
    if(l > n) {
        s[x] = t[x];
        f[x] = 1;
        return;
    }
    dfs(l);dfs(r);
    if(s[l] > s[r])
        swap(s[l], s[r]);
    s[x] = t[x] + s[l] + s[r];
    f[x] = f[l] * f[r] % Mod;
    if(s[l] != s[r])
        f[x] = f[x] * 2 % Mod;
}

int main()
{
    scanf("%d", &n);
    n = (1 << n) - 1;
    cin >> t;
    t = ' ' + t;
    dfs(1);
    printf("%lld\n", f[1]);
    return 0;
}