## Editorial for Số hiệu tổ hợp

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const maxn=310;
base=100000000;
type bignum=array[0..14] of longint;
var n,k:longint;
c:array[0..maxn,0..maxn] of bignum;
a,re:array[0..maxn] of longint;
s,res:bignum;

procedure rf;
var i,j,l:longint; s1,t:string; code:integer;
begin
l:=length(s1);
s[0]:=(l+7) div 8;
for i:=1 to s[0]-1 do
begin
t:=copy(s1,l-i*8+1,8);
val(t,j,code);
s[i]:=j;
end;
l:=l mod 8;
if l=0 then l:=8;
t:=copy(s1,1,l);
val(t,j,code);
s[s[0]]:=j;
for i:=1 to k do read(a[i]);
end;

procedure plus(var c:bignum;a,b:bignum);
var max,i,mem:longint;
begin
if a[0]>=b[0] then max:=a[0] else max:=b[0];
mem:=0;
for i:=1 to max do
begin
c[i]:=(a[i]+b[i]+mem) mod base;
mem:=(a[i]+b[i]+mem) div base;
end;
if mem>0 then
begin
inc(max);
c[max]:=mem;
end;
c[0]:=max;
end;

function small(a,b:bignum):boolean;
var i:longint;
begin
small:=true;
if a[0]<b[0] then exit;
if a[0]>b[0] then
begin
small:=false;
exit;
end;
for i:=a[0] downto 1 do
if b[i]<a[i] then
begin
small:=false;
exit;
end
else
begin
if b[i]>a[i] then exit;
end;
end;

procedure minus(var a:bignum;b:bignum);
var i,max,mem:longint;
begin
if a[0]>=b[0] then max:=a[0] else max:=b[0];
mem:=0;
for i:=1 to max do
begin
if a[i]>=b[i]+mem then
begin
a[i]:=a[i]-b[i]-mem;
mem:=0;
end
else
begin
a[i]:=base+a[i]-b[i]-mem;
mem:=1;
end;
end;
while (a[max]=0) and (max>0) do dec(max);
a[0]:=max;
end;

procedure init;
var i,j,t:longint;
begin
fillchar(re,sizeof(re),0);
fillchar(c,sizeof(c),0);
for i:=1 to n do
begin
c[i,0,1]:=1;
c[i,i,1]:=1;
c[i,0,0]:=1;
c[i,i,0]:=1;
end;
for i:=2 to n do
begin
if i-1<=k then t:=i-1 else t:=k;
for j:=1 to t do
plus(c[i,j],c[i-1,j],c[i-1,j-1]);
end;
end;

procedure timth;
var i,j:longint; t:bignum;
begin
for i:=1 to k do
begin
for j:=re[i-1]+1 to n+i-k do
begin
t:=c[n-j,k-i];
if small(s,t) then
begin
re[i]:=j;
break;
end
else minus(s,t);
end;
end;
if re[k]=0 then re[k]:=n;
end;

procedure doith;
var i,j,t:longint;
begin
res[0]:=1; res[1]:=1;
for i:=1 to k do
for j:=a[i-1]+2 to a[i] do
plus(res,res,c[n-j+1,k-i]);
end;

procedure wf;
var i,l,j:longint; s:string;
begin
for i:=1 to k do write(re[i],' ');
writeln;
for i:=res[0] downto 1 do
begin
if i<res[0] then
begin
str(res[i],s);
l:=length(s);
for j:=l+1 to 8 do write(0);
end;
write(res[i]);
end;
end;
begin
rf;
init;
timth;
doith;
wf;
end.


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


#### Code mẫu của RR

{\$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=101;
MAXM=301;
oo=100000000;
type
bigNum=array[0..MAXN] of longint;
var
f1,f2:text;
procedure print(a:bigNum);
var
i:longint;
s:string;
begin
if a[0]=0 then begin writeln(f2,0); exit; end;
write(f2,a[MAXN-a[0]+1]);
for i:=MAXN-a[0]+2 to MAXN do
begin
str(a[i],s);
while length(s)<8 do s:='0'+s;
write(f2,s);
end;
writeln(f2);
end;
operator <(a,b:bigNum) c:boolean;
var
i:longint;
begin
if a[0]<b[0] then exit(true)
else if a[0]>b[0] then exit(false);
for i:=MAXN-a[0]+1 to MAXN do
if a[i]<b[i] then exit(true)
else if a[i]>b[i] then exit(false);
exit(false);
end;
operator +(a,b:bigNum) c:bigNum;
var
nho,i:longint;
begin
nho:=0;
fillchar(c,sizeof(c),0); c[0]:=max(a[0],b[0]);
for i:=MAXN downto MAXN-c[0]+1 do
begin
c[i]:=a[i]+b[i]+nho;
nho:=c[i] div oo;
c[i]:=c[i] mod oo;
end;
if nho>0 then
begin
inc(c[0]);
c[MAXN-c[0]+1]:=nho;
end;
end;
operator -(var a,b:bigNum) c:bigNum;
var
nho,i:longint;
begin
nho:=0;
fillchar(c,sizeof(c),0); c[0]:=a[0];
for i:=MAXN downto MAXN-c[0]+1 do
begin
c[i]:=a[i]-b[i]-nho;
if c[i]<0 then
begin
nho:=1;
c[i]:=c[i]+oo;
end
else nho:=0;
end;
while (c[0]>0) and (c[MAXN-c[0]+1]=0) do dec(c[0]);
end;
procedure trans(s:ansistring;var a:bigNum);
var
ss:ansistring;
code:integer;
begin
fillchar(a,sizeof(a),0);
while length(s)>7 do
begin
ss:=copy(s,length(s)-7,8);
delete(s,length(s)-7,8);
val(ss,a[MAXN-a[0]],code);
inc(a[0]);
end;
if length(s)>0 then
begin
val(s,a[MAXN-a[0]],code);
inc(a[0]);
end;
end;
var
xet,a:array[0..MAXM] of longint;
c:array[0..MAXM,0..MAXM] of bigNum;
tt:bigNum;
n,k:longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure inp;
var
i,j:longint;
begin
c[0,0][0]:=1; c[0,0][MAXN]:=1;
for i:=1 to MAXM do
begin
c[i,0][0]:=1; c[i,0][MAXN]:=1;
c[i,i][0]:=1; c[i,i][MAXN]:=1;
end;
for i:=1 to MAXM do
for j:=1 to i-1 do
c[i,j]:=c[i-1,j-1]+c[i-1,j];
end;
procedure solve1;
var
s:ansistring;
u,i:longint;
begin
trans(s,tt);
for i:=1 to k do
begin
u:=a[i-1]+1; while xet[u]=1 do inc(u);
while (c[n-u,k-i]<tt) do
begin
tt:=tt-c[n-u,k-i];
inc(u); while xet[u]=1 do inc(u);
end;
xet[u]:=1; a[i]:=u;
end;
for i:=1 to k do
write(f2,a[i],' ');
writeln(f2);
end;
procedure solve2;
var
i,u,count:longint;
begin
fillchar(xet,sizeof(xet),0);
fillchar(tt,sizeof(tt),0);
for i:=1 to k do read(f1,a[i]);
xet[0]:=1;
for i:=1 to k do
begin
u:=a[i-1]; while xet[u]=1 do inc(u); count:=0;
while (u<a[i]) do
begin
if xet[u]=0 then tt:=tt+c[n-u,k-i];
inc(u);
end;
xet[a[i]]:=1;
end;
print(tt+c[0,0]);
end;
begin
openF;
inp;
solve1;
solve2;
closeF;
end.