自动搬运

查看原文

来自洛谷，原作者为

	ezuyz 大梦谁先觉，平生我自知~

搬运于2025-08-24 22:29:42，当前版本为作者最后更新于2021-03-07 08:20:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考虑递推

设 $f[k]$为层数为 $k$ 时的贡献， $siz$ 为上一次树的大小，即这次左子树或右子树的大小。

可以发现，随着层数的加 $1$ 至 $k$ 层，所在同一层的节点产生的贡献与左右位置无关而只与其深度有关（因为整棵树为满二叉树，所以同层的任何两个节点的位置结构相同，成为 $LCA$ 的次数也相同），因此，我们可以通过交换节点将新的满二叉树的两颗子树看作原来的 $k-1$ 层的树编号扩大了 $2$ 倍和扩大了 $2$ 倍再加 $1$，因此左子树产生的贡献为 $f[k-1]$ 的二倍，右子树产生的贡献为 $f[k-1]$ 的二倍再加上 $LCA$ 在右子树上的情况总数，即总共有 $f[k-1]*2+siz*siz$ 点贡献，这样 $LCA$ 在两颗子树上的情况（即 $i$ 和 $j$ 都同在一颗子树上）就解决了，我们考虑 $i$,$j$ 在不同的子树上和在根节点的情况，而因为以下情况产生的贡献都为 $1$，因此贡献数就等于情况数。

• 当 $i$ 和 $j$ 分别在两颗不同子树上时，一共有 $siz*siz*2$ 种情况（ $i$,$j$ 的值可互换，因此要乘 $2$）。
• 当 $i$ 和 $j$ 其中一个为根节点时，共有 $siz*2*2$ 种情况（两颗子树大小共为 $siz*2$，$i$,$j$ 的值可互换再乘 $2$）。
• 当 $i$ 和 $j$ 都为根节点时，有一种情况。

因此总递推式为：

$$f[i]=f[i-1]*2+f[i-1]*2+siz*siz+siz*siz*2+siz*2*2+1 $$

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod=998244353;
ll f[1000006];
int main()
{
	f[1]=1;
	ll siz=1;
	for(int i=2;i<=1000000;i++)
	{
		f[i]=((f[i-1]<<2)+((siz*siz)<<1)+siz*siz+(siz<<2)+1)%mod;
		siz=((siz<<1)+1)%mod;
	}
	int T;
	cin>>T;
	ll k;
	while(T--)
	{
		scanf("%lld",&k);
		printf("%lld\n",f[k]);
	}
}