【题解】LuoGu7108：移花接木

最新推荐文章于 2022-03-12 16:11:12 发布

原创最新推荐文章于 2022-03-12 16:11:12 发布 · 1k 阅读

0 ·

CC 4.0 BY-SA版权

文章标签：

#题解 #LuoGu

题解同时被 2 个专栏收录

435 篇文章

订阅专栏

LuoGu

255 篇文章

订阅专栏

本文讲解了如何通过递归和接木的概念，解决不同情况下的树形结构问题，涉及砍叶、接木、接点数量计算等步骤。详细分析了当a、b、h取不同值时的具体操作和答案形式。

原题传送门
可以一个一个部分分推下来，放到联赛T1也是可以的，用时不会超过40min

$h = 0 :$ 把根的儿子都砍掉，答案为 $a$
$a = b :$ 把第 $h$ 层的所有点的儿子都砍掉，答案为 $a^{h+1}$
$a = 1 :$ 引入接木的概念，每次拿下来的一棵子树就是原树（因为是无限延展的），对于这个部分

其实就是非最后一层的点都要接上 $b - 1$ 个
最后一层的点都要砍掉儿子
然后其实可以先砍掉，再接木上去，并成一步操作
答案就是最后一层的叶子个数， $b^h$
$b = 1 :$ 直接把多的东西砍掉，每一层就一个点保留，所以每层砍掉 $a - 1$ 个，最后一层砍掉 $a$ 个，答案是 $h (a - 1) + a$
$a < b :$ 需要接木，根据上面得到的结论，可以先砍掉，再接上。每次考虑接上的时候，都存在一个地方可以断掉。所以只要考虑哪些要砍掉就行了。
考虑现在已经全部接好了，那么最后一层的所有叶子的所有儿子都要砍掉，所以答案是 $a*b^h$
$a > b :$ 还是直接砍光，每个点都要砍掉 $a - b$ 个，总共的节点数用等比数列求和求出，答案是 $\frac{(a-b)(b^h-1)}{b-1}+a*b^h$

Code：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL qy = 1000000007;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

LL ksm(LL n, LL k){
	LL s = 1;
	for (; k; k >>= 1, n = n * n % qy)
		if (k & 1) s = s * n % qy;
	return s;
}

int main(){
	int Q = read();
	while (Q--){
		LL a = read(), b = read(), h = read();
		if (h == 0) printf("%lld\n", a % qy);
		else if (a == b) printf("%lld\n", ksm(a, h + 1));
		else if (a == 1) printf("%lld\n", ksm(b, h));
		else if (b == 1) printf("%lld\n", (h * a % qy + a - h + qy) % qy);
		else if (a < b) printf("%lld\n", a * ksm(b, h) % qy);
		else printf("%lld\n", ((a - b) * (ksm(b, h) - 1 + qy) % qy * ksm(b - 1, qy - 2) % qy + a * ksm(b, h) % qy) % qy);
	}
	return 0;
}