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