洛谷 P8089

考虑对于满二叉树，显然只与 \(dep\) 有关，设 \(f_{i}\) 表示深度为 \(i\) 的答案（确切的说应该是到最深深度的距离），则有 \(f_1=1,f_i=(f_{i-1}+1)^2(i\ge2)\)。

则对于完全二叉树，有一个很优秀的性质，对于一个节点，它的左子树和右子树至少有一个是满二叉树，所以可以将提前预处理的值直接返回。

那么每次走的路径是什么呢？

就是给定字符串减一的二进制表示下，取最后 \(dep\) 位，从高往低，为 \(0\) 则往左子树走，否则往右子树走。

给定的二进制串是 \(00101\)，减去 \(1\)，去掉最高位，变成 \(0100\)，那么路径就是 \(1,2,5,10,20\)，红框标出的就是预处理的可以直接返回的值，因为是满二叉树。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005, mod = 998244353;
int T;
int n, f[N], a[N];
char s[N];

int dfs(int cur) {
	if (cur == n) return 1;
	if (a[cur] == 0) return 1ll * (dfs(cur + 1) + 1) * (f[n - cur - 1] + 1) % mod;
	else return 1ll * (dfs(cur + 1) + 1) * (f[n - cur] + 1) % mod;
}

void solve() {
	scanf("%d%s", &n, s);
	int pos;
	for (int i = 0; i < n; ++i) {
		a[i] = s[i] - '0';
		if (a[i]) pos = i;
	}
	a[pos] = 0;
	for (int i = pos + 1; i < n; ++i) a[i] = 1;
	printf("%d\n", dfs(1));
}

int main() {
	for (int i = 1; i <= 1000000; ++i) f[i] = 1ll * (f[i - 1] + 1) * (f[i - 1] + 1) % mod;
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}