解題區/解題區 - UVa

UVa 12749 - John's Tree

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

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

請問最多有幾個節點。

Sample Input

1
2
3
4
3
0 1
1 2
1 5

Sample Output

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

Solution

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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("in.txt", "r+t", stdin);
//	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: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
1000
0 1
1 2
1 5
500 1
0 500
2000000000 2000000000
*/