首页 > itarticle > uva 12749 – john’s tree

uva 12749 – john’s tree

admin 11月 11, 2020 0

contents

Problem

目標生成一個有根樹，每個節點的 degree 最多為 V，並且樹深度恰好為 D。

請問最多有幾個節點。

Sample Input

Sample Output

1
2
3

Case 1: 1
Case 2: 3
Case 3: 6

Solution

很明顯是一個等比級數的計算，中間牽涉到除法，利用費馬小定理找到乘法反元素，藉此完成除法。

特別記住，V 只得是 degree 而搜尋樹的分支數，因此 degree 會包含跟父親的連接。特別小心 V = 1 的情況，要不兩個點要不一個點，而 V = 2 則會退化擇一條鍊，在等比級數上的計算會有瑕疵。

#include <stdio.h>
#include <assert.h>
const long long mod = 1000000007LL;
long long mul(long long a, long long b) {
	long long ret = 0;
	for( ; b != 0 ; b>>=1, (a<<=1)%=mod)
		if(b&1)
			(ret += a) %= mod;
	return ret;
}
long long mpow(long long x, long long y, long long mod) {
	long long ret = 1;
	while (y) {
		if (y&1)
			ret = (ret * x)%mod;
		y >>= 1LL, x = (x * x)%mod;
	}
	return ret;
}
int main() {
//	freopen("out.txt", "w+t", stdout); 
	int testcase, cases = 0;
	long long D, V;
	scanf("%d", &testcase);
	while (scanf("%lld %lld", &D, &V) == 2) {
		assert(D >= 0 && V > 0 && D <= 2e+9 && V <= 2e+9);
		long long ret = 0;
		if (D == 0)			ret = 1;
		else if (D == 1)	ret = (V + 1)%mod;
		else if (V == 1)	ret = -1;
		else if (V == 2)	ret = (1 + D * 2)%mod;
		else {
			ret = mpow(V - 1, D, mod) - 1 + mod;
			ret = ret * mpow(V - 2, mod - 2, mod) %mod;
			ret = ret * V %mod;
			ret = (ret + 1 + mod)%mod;
			assert(ret >= 0);
		}
		printf("Case %d: %lldn", ++cases, ret);
	}
	return 0;
}
/*
1000
0 1
1 2
1 5
500 1
0 500
2000000000 2000000000
*/