P7419 「PMOI-2」参天大树 题解

ezuyz · 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 都为根节点时，有一种情况。

因此总递推式为：

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]);
    }
}