解題區/解題區 - UVa

UVa 12866 - Combination

contents

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

Problem

Total number of odd entries in first n rows of Pascal’s triangle.

對於巴斯卡三角形找奇數的個數。

Sample Input

1
2
3
4
2 3
10 20
100 200
0 0

Sample Output

1
2
6
70

Solution

下面是巴斯卡三角形 (組合數) 前 n 行為奇數的總個數。

0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, 49, 57, 65, 81, 83, 87, 91, 99, 103, 111, 119, 135, 139, 147, 155, 171, 179, 195, 211, 243, 245, 249, 253, 261, 265, 273, 281, 297, 301, 309, 317, 333, 341, 357, 373, 405, 409, 417, 425, 441, 449, 465, 481, 513, 521

在 A006046 可以得到遞迴公式：

  • a(0) = 0
  • a(1) = 1
  • a(2k) = 3 * a(k), a(2k+1) = 2*a(k) + a(k+1)

但是在第三項中可以發現到有可能指數增加，由於會被拆分成兩項，所以這方法不太可行。

如果打印每一行的奇數個數出來，四四分組，會發現組合是以 2 的冪次增長的組合，而組合之間恰好是兩倍的關係。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1 2 2 4  ----------- sum 9
2 4 4 8  ----------- sum 27
--
2 4 4 8 
4 8 8 16 ----------- sum 81
-- prev x 2
2 4 4 8 
4 8 8 16 
4 8 8 16 
8 16 16 32 ----------- sum 273  
-- prev x 2
2 4 4 8 
4 8 8 16 
4 8 8 16 
8 16 16 32 
4 8 8 16 
8 16 16 32
...

觀察如上所述，遞推之。

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
53
54
55
56
57
58
59
60
#include <stdio.h> 
// https://oeis.org/A006046
// a(0) = 0, a(1) = 1, a(2k) = 3*a(k), a(2k+1) = 2*a(k) + a(k+1).
long long f(long long n) {
    if (n < 2)	return n;
    if (n&1) 
        return f(n/2) * 2 + f(n/2 + 1);
    else
        return f(n/2) * 3;
}
unsigned long long dp[50] = {};
unsigned long long g(long long n) {
    if (n == 0)	return 0;
    if (n == 1)	return 1;
    if (n == 2)	return 3;
    if (n == 3)	return 5;
    if (n == 4)	return 9;
    if (n == 5)	return 11;
    if (n == 6)	return 15;
    if (n == 7)	return 19;
    long long i, j;
    for (i = 1, j = 1; 8 * i < n; i <<= 1, j++);
//	printf("%lld %lld %lld %lld\n", j, n, i, n - 4 * i);
    return dp[j] + 2 * g(n - 4 * i);
}
int main() {
    dp[1] = 9, dp[2] = 27;
    for (int i = 3; i < 50; i++)
        dp[i] = dp[i - 1] * 3;
     
//	int C[105][105] = {}, totsum = 0;
//	C[0][0] = 1;
//	for (int i = 0; i < 100; i++) {
//		C[i][0] = 1;
//		int sum = 1;
//		for (int j = 1; j <= i; j++) {
//			C[i][j] = (C[i-1][j] + C[i-1][j-1])&1;
//			sum += C[i][j];
//		}
//		totsum += sum;
//		printf("%2d: %5d %5d\n", i, sum, totsum);
//	}
//	for (int i = 0; i < 50; i++) {
//		for (int j = 0; j <= i; j++)
//			printf("%d", C[i][j]);
//		puts("");
//	}
    long long L, R;
    while (scanf("%lld %lld", &L, &R) == 2) {
        if (L == 0 && R == 0)
            break;
//		printf("%lld %lld\n", f(R + 1), g(R + 1));
//		long long ret = f(R + 1) - f(L);
//		printf("%lld\n", ret);
        unsigned long long ret2 = g(R + 1) - g(L);
        printf("%llu\n", ret2);
    }
    return 0;
}