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

Please read the guidelines before commenting.


There are no comments at the moment.