Hướng dẫn giải của Số hiệu tổ hợp
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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.
Bình luận