SHTH - Số hiệu tổ hợp

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int BASE = 100000000;
const int LEN = 8;
const int N = 303;
using namespace std;

typedef VI big;

big to_big(int v) {return big(1, v);}
bool operator < (big &a, big &b) {
    if (SZ(a) != SZ(b)) return SZ(a) < SZ(b);
    REPD(i, SZ(a) - 1, 0) if (a[i] != b[i]) return a[i] < b[i];
    return 0;
}

void fix(big &a) {
    a.PB(0);
    FOR(i, 0, SZ(a) - 1) {
        a[i + 1] += a[i] / BASE; a[i] %= BASE;
        if (a[i] < 0) {a[i] += BASE; a[i + 1]--;}
    }
    while (SZ(a) > 1 && a.back() == 0) a.pop_back();
}

void operator += (big &a, big &b) {
    a.resize(max(SZ(a), SZ(b)));
    FOR(i, 0, SZ(b)) a[i] += b[i];
    fix(a);
}
void operator -= (big &a, big &b)
    {FOR(i, 0, SZ(b)) a[i] -= b[i]; fix(a);}

big operator + (big a, big b) {a += b; return a;}
big operator - (big a, big &b) {a -= b; return a;}

istream& operator >> (istream& cin, big &a) {
    string s; cin >> s;
    a.clear(); a.resize(SZ(s) / LEN + 1);
    FOR(i, 0, SZ(s)) {
        int x = (SZ(s) - 1 - i) / LEN;
        a[x] = a[x] * 10 + s[i] - '0';
    }
    return fix(a), cin;
}

ostream& operator << (ostream& cout, const big &a) {
    printf("%d", a.back());
    REPD(i, SZ(a) - 2, 0) printf("%08d", a[i]);
    return cout;
}

big f[N][N];
int cfg[N], ans[N];
int n, k;
big kth;

int cnt, x[N];
void naive(int i) {
    if (i > k) {
        cout << ++cnt << ' ';
        REP(i, 1, k) cout << x[i] << ' '; cout << endl;
        return;
    }
    REP(j, x[i - 1] + 1, n) {
        x[i] = j;
        naive(i + 1);
    }
    x[i] = 0;
}

int main() {
    cin >> n >> k; cin >> kth;
    REP(i, 1, k) cin >> cfg[i];

    REP(i, 1, n) f[k][i] = to_big(1);
    REPD(i, k - 1, 0) REPD(j, n, 1)
        f[i][j] = f[i + 1][j + 1] + f[i][j + 1];

    //kth configuration
    REP(i, 1, k) {
        REP(j, ans[i - 1] + 1, n)
        if (f[i][j] < kth) kth -= f[i][j];
        else {
            ans[i] = j;
            break;
        }
    }
    REP(i, 1, k) cout << ans[i] << ' ';
    cout << endl;

    //id of cfg[]

    big id;
    REP(i, 1, k) FOR(j, cfg[i - 1] + 1, cfg[i])
    id += f[i][j];
    cout << id + to_big(1) << endl;

    //naive(1);
    return 0;
}

Download