思路

首先，题目说：

从编号为 ii 的叶子节点到树根每一个点的点权的 &\& 值 &\& 上 i−2n−1i-2^{n-1} 为 i−2n−1i-2^{n-1}。

然后，根据按位 &\& 的性质，x&y=yx \& y = y，当且仅当：

  1. 当 yy 的第 ii 个二进制位为 11 时，xx 的第 ii 个二进制位也为 11。

  2. 当 yy 的第 ii 个二进制位为 00 时，xx 的第 ii 个二进制位任意。

  3. 2二进制下y的0位位数2^{\text{二进制下y的0位位数}} 就是 xx 的取值数量。

根据乘法原理，2所有节点0位位数的和2^{\text{所有节点0位位数的和}} 就是整棵树的取值数量。

我们现在就要求所有节点 00 位位数的和。

可以先求出每一层节点 00 位位数的和，再加起来，就是答案了。

我们先手推一个 n=4n = 4 的情况，每一个 aia_i 取最多的 00。

首先，我们知道：叶节点 ii 取值为 i−2n−1i - 2^{n - 1}；

非叶节点 ii 为了满足它的两个子节点 2i2i 和 2i+12i + 1 的要求，取值应为 a2i∣a2i+1a_{2i} | a_{2i + 1}。

对于第 n−1n - 1 层，2i−2n−12i - 2^{n - 1} 与 2i+1−2n−12i + 1 - 2{n - 1} 的最后一位一个为 00，一个为 11，或起来为 11；所以，所有第 n−1n - 1 层的节点的取值的末尾都是 11，删掉对 00 的个数没有影响。

删掉之后，第 n−1n - 1 层的 001001，011011，101101，111111 就变成了 0000，0101，1010，1111。我们发现，这不是 n−1n - 1 层二叉树的 44 个叶子节点的取值吗？

于是，我们就可以知道：nn 层二叉树所有节点 00 位位数的和 $ = $ $\sum_{i = 1}^n $ ii 层二叉树第 ii 层节点的和。

再拿 n−1n - 1 层的 0000，0101，1010，1111 举例子，可以发现：第 nn 层的 000000，001001，010010，011011，100100，101101，110110，111111 是由 0000，0101，1010，1111 分别在开头加了一个 00 和一个 11 得来的。加了一个 00，00 的个数就加了 11；加了一个 11，00 的个数没变。

设 fif_i 为 nn 层二叉树第 ii 层所有节点 00 位位数的和，sumisum_i 为 nn 层二叉树前 ii 层所有节点 00 位位数的和，可以得到递推式：

fi={0(i=1)2×fi−1+2i−2(otherwise⁡)f_i = \begin{cases}0 & (i = 1) \\ 2 \times f_{i - 1} + 2^{i - 2} & (\operatorname{otherwise}) \end{cases}

sumi=sumi−1+fisum_i = sum_{i - 1} + f_i

因为 n≤1018n \le 10^{18}，所以不难想到用矩阵快速幂优化。

目标矩阵：[fn2n−1sumn−1]\begin{bmatrix} f_n & 2^{n - 1} & sum_{n - 1}\end{bmatrix}，fn+sumn−1f_n + sum_{n - 1} 即为答案。

推导一个矩阵 MM，使得：

[fi−12i−2sumi−2]×M=[fi2i−1sumi−1]\begin{bmatrix} f_{i - 1} & 2^{i - 2} & sum_{i - 2}\end{bmatrix} \times M = \begin{bmatrix} f_{i} & 2^{i - 1} & sum_{i - 1}\end{bmatrix}

根据转移方程，可得 M=[201120001]M = \begin{bmatrix}2 & 0 & 1 \\ 1 & 2 & 0 \\ 0 & 0 & 1\end{bmatrix}。

设计初始矩阵为 [f120sum0]\begin{bmatrix} f_1 & 2^0 & sum_0\end{bmatrix}，也就是 [010]\begin{bmatrix} 0 & 1 & 0\end{bmatrix}。

目标矩阵即为 [010]×Mn−1\begin{bmatrix}0 & 1 & 0\end{bmatrix} \times M^{n - 1}。

根据欧拉定理的推论：

ab≡ab mod φ(p)(modp)a^b \equiv a^{b \bmod \varphi(p)}\pmod p

∵p\because p 为质数

∴φ(p)=p−1\therefore \varphi(p) = p - 1

然后，矩阵乘法运算的时候，将模数设为 p−1p - 1 即可。

最后求的答案为 2sumn2^{sum_n}。

代码

#include <algorithm>
#include <cstdio>
#define ll long long

using namespace std;

int mod = 998244353;
int _mod = mod - 1;
struct matrix{
	int n;
	ll val[101][101];
	void out(){
		for (int i = 1;i <= n;i ++){
			for (int j = 1;j <= n;j ++) printf("%lld ", val[i][j]);
			printf("\n");
		}
	}
	matrix operator*(matrix b){
		matrix res;
		res.n = n;
		if (n != b.n) exit(1);
		for (int i = 1;i <= n;i ++){
			for (int j = 1;j <= n;j ++){
				res.val[i][j] = 0;
				for (int k = 1;k <= n;k ++) res.val[i][j] = (res.val[i][j] + (val[i][k] * b.val[k][j]) % _mod) % _mod; 
			}
		}
		return res;
	}
}M, B, S;
matrix one(int x){
	matrix res;
	res.n = x;
	for (int i = 1;i <= x;i ++){
		for (int j = 1;j <= x;j ++) res.val[i][j] = 0;
	}
	for (int i = 1;i <= x;i ++) res.val[i][i] = 1;
	return res;
}
matrix mpow(matrix m, ll p){
	matrix ans = one(m.n), base = m;
	while (p){
		if (p & 1) ans = ans * base;
		base = base * base;
		p >>= 1;
	}
	return ans;
}
ll qpow(ll x, ll p){
	ll ans = 1, base = x;
	while (p){
		if (p & 1) ans = ans * base % mod;
		base = base * base % mod;
		p >>= 1;
	}
	return ans % mod;
}
const ll b[4][4] = {{0, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}};
const ll m[4][4] = {{0, 0, 0, 0}, {0, 2, 0, 1}, {0, 1, 2, 0}, {0, 0, 0, 1}};
ll n, po;
int main(){
	B.n = M.n = 3;
	for (int i = 1;i <= 3;i ++){
		for (int j = 1;j <= 3;j ++){
			B.val[i][j] = b[i][j];
			M.val[i][j] = m[i][j];
		}
	}
	scanf("%lld", &n);
	S = B * mpow(M, n - 1);
	printf("%lld", qpow(2, (S.val[1][1] + S.val[1][3]) % _mod));
}