解題區/解題區 - UVa

UVa 1649 - Binomial coefficients

contents

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

Problem

組合的反函數，現在給定組合數，輸出是由哪幾種組合可以配出組合數。

Sample Input

1
2
3
2
2
15

Sample Output

1
2
3
4
1
(2,1)
4
(6,2) (6,4) (15,1) (15,14)

Solution

先預見表，完成前幾項的結果。

看著巴斯卡三角形單純看 i，對於 C(n, i) 是一個嚴格遞增的函數。因此窮舉 i，針對組合數進行二分搜索。

為防止越界，在整數計算上可以利用除法進行比大小。

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
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <map> 
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 1024
const long long MAXVAL = 1e+16, MAXVAL2 = 1e+15;
long long C[MAXN][MAXN] = {};
map<long long, vector< pair<long long, long long> > > R;
int testCombination(long long n, long long m, long long Cnm) { // test C(n, m), m < 10
    long long ret = 1;
    m = min(m, n-m);
    for (long long i = 1; i <= m; i++) {
        if (Cnm * i / (n + 1 - i) / ret  < 1)
            return 1;
        ret = ret * (n + 1 - i) / i;
    }
    return ret == Cnm ? 0 : -1;
}
vector< pair<long long, long long> > invCombination(long long n) {
    vector< pair<long long, long long> > ret;
    ret = R[n];
    for (int i = 1; i < 10; i++) {
        long long l = 1, r = n, mid;
        while (l <= r) {
            mid = (l + r)/2;
            int f = testCombination(mid, i, n); // {-1, 0, 1}
            if (f == 0) {
                ret.push_back(make_pair(mid, i));
                ret.push_back(make_pair(mid, mid - i));
                break;
            }
            if (f < 0)
                l = mid + 1;
            else
                r = mid - 1;
        }
    }
    sort(ret.begin(), ret.end());
    ret.resize(unique(ret.begin(), ret.end()) - ret.begin());
    return ret;
}
int main() {
//	printf("%d\n", testCombination(5000, 2, 12497500));
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
            C[i][j] = min(C[i][j], MAXVAL);
            if (j != i && C[i][j] <= MAXVAL2)
                R[C[i][j]].push_back(make_pair(i, j));
        }
    }
//	for (int i = 0; i < 10; i++)
//		printf("%lld\n", C[MAXN-1][i]);
    int testcase;
    long long n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld", &n);
        vector< pair<long long, long long> > r = invCombination(n);
        printf("%d\n", (int) r.size());
        for (int i = 0; i < r.size(); i++)
            printf("(%lld,%lld)%c", r[i].first, r[i].second, i == r.size()-1 ? '\n' : ' ');
    }
    return 0;
}