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.
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 readln(n,k); readln(s1); 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.
Code mẫu của ladpro98
#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 readln(f1,n,k); 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 readln(f1,s); 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.
Comments