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;
}