P7108 【移花接木】题解

AsunderSquall · 2020-11-28 19:36:57 · 题解

刚推出式子时不知道为什么被卡常了，非常自闭 link

声明1：下文由于本人菜，分不清“结点”和“节点”，请忽略。

update:修改了一个笔误。

题意

有一个高度无限的有根满 a 叉树，你每次操作可以选择一棵子树全部删除，或者选择一棵子树，拼到另一个结点下面，问至少需要几次操作可以把这棵树变成高度为h的满b叉树。
（题意中有描述的不到位的地方，仅供回忆题目，具体见原题目

题解

声明2：下文所说的“删除结点”为删除结点及其子树。

也就是说删得只剩根节点，输出 a 即可

如图为 a=5,b=?,h=0 的情况，删去黑色节点。
if (h==0) cout<<(a);

只需要将多余的子树删去即可
设根为第0层，那么要保留到第 h 层，h+1 层的所有结点都要删去，而第 h+1 层有 a^{h+1} 个结点

如图为a=3,b=3,h=1 的情况，删去黑色节点。
if (a==b) cout<<(ksm(a,h+1,mod));

原始的树为一条链
那么我们可以把满 b 叉树分成若干条从上到下链，使数量最少，链的条数就是答案。
设k层的满t叉树的链的条数为 f(k,t)。
我们考虑使一棵满 t 叉树分成的链最少，根节点一定在某条链中，那我们任取一个儿子 u，把经过u的链拼上一条 root\to u 的边。
那么有 f(k,t)=t\cdot f(k-1,t) 又有 f(0,t)=1，所以 f(k,t)=t^k。 以a=1,b=2,h=3为例

对于根的每个儿子，都可以分成 f(2,2) 条链，总共 2f(2,2) 条链

考虑根，只要连到一条经过儿子的链上就行了

if (a==1) cout<<(ksm(b,h,mod));

要把树删得只剩一条链
那么第 0,1,\cdots h-1 层都有多余的 a-1 个结点，而第 h 层则有 a 个，将他们删除即可。

如图为 a=3,b=1,h=2 的情况，删去黑色节点。
if (b==1) cout<<(((a-1)*h+a)%mod);

我感觉后面的点都没什么用……其实只要把这个式子搞出来后面就一样了。。。

分为 a<b 和 a>b 两种情况讨论（因为本人很菜）

我们要把满a叉树补成满 b 叉树
那么我们分为两个步骤

• 把前面h层补成满b叉树
• 删去第h+1层多余的结点

对于第一步，我们考虑一层一层拖子树。
先把第1层补完，拖来了 b-a 棵子树。
这个时候第2层就有 b\cdot(b-a) 棵子树要拖。

第h层有 b^{h-1}(b-a) 棵子树要拖。
那么我们只需要将他们加起来 (b-a)\sum_{i=0}^{h-1}b^i。
对于第二步，第 h 层有 b^h 个结点，那么第 h+1 层有 a b^h 棵子树，将他们全部删去。
所以答案为 \sum_{i=0}^{h-1}b^i+ab^h。

真 的 吗 ？

显然，如果我们将本来第二步中应该删去的子树给拖走，那么就省去了删除这个结点这一步骤。
所以答案为 \max(ab^h,(b-a)\sum_{i=0}^{h-1}b^i)=ab^h

这样说可能有点模糊，我们来举个例子。
Example:a=2,b=3,h=2 （深度 >3 的节点不画出）。
下面的图的标号和上面 出现什么标什么 的标号不太一样，对于标号为 i 的节点，我们给它的左儿子和右儿子分别标号为 2i 和 2i+1 。

比如说第一层，如果我们随便拖一个下面的节点过来，这样是可行的，但是不够优秀。

我们知道，到时候我们肯定要把 8 这个节点从 4 的儿子中移除，所以我们如果把 8 拖过来，就可以减少操作次数。

同理，要使 2 的儿子数目变成 3，我们把 9 号节点拖过去。

然后 10\to3,11\to 8

最后把底部的所有节点全部删去

同样分为两个步骤

• 把前面h层删成满b叉树
• 删去第h+1层多余的结点

对于第一步，我们考虑一层一层删子树，答案与 a<b 的情况类似，为 (b-a)\sum_{i=0}^{h-1}b^i
对于第二步，为 ab^n，那么答案就为 (b-a)\sum_{i=0}^{h-1}b^i+ab^h

如图为 a=3,b=2,h=2 的情况，删去黑色节点

事实上我并不理解为什么到了这一步还推不出正确答案（似乎也没有被卡到这一档部分分的人）。

显然\sum_{i=0}^{h-1}b^i可以快速计算。

这个应该小学就会了吧。。。
同时这个也可以解释为什么 \max\{ab^h,(b-a)\sum_{i=0}^{h-1}b^i\}=ab^h
注意 b=1 的时候有除以 0 的情况，要特判。

代码

真的很短，为什么不去自己写呢？

#include<bits/stdc++.h>
#define int long long
#define rd(x) x=read()
using namespace std;
const int mod=1e9+7;
inline int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int ksm(int x,int y,int z){int ret=1;while (y){if (y&1) ret=(ret*x)%z;x=(x*x)%z;y>>=1;}return ret;}
int INV(int x){return ksm(x,mod-2,mod);}
int a,b,h;
int T;
signed main()
{
    rd(T);
    while (T--)
    {
        rd(a);rd(b);rd(h);
        if (b==1) cout<<(((a-1)*h+a)%mod);else
        if (a<=b) cout<<ksm(b,h,mod)*a%mod;
        else cout<<(a*ksm(b,h,mod)%mod+(ksm(b,h,mod)-1)*(a-b)%mod*INV(b-1)%mod)%mod;
        putchar('\n');
    }
}