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 fi='';
      fo='';
      maxn=10001;
      z=1000000000;
var n,re,k:longint;
    a:array[1..maxn] of longint;
    f:array[1..10,1..maxn] of longint;

procedure rf;
var i:longint;
begin
     read(n,k);
     for i:=1 to n do read(a[i]);
end;

function calc(j,x:longint):longint;
var r:longint;
begin
     r:=0;
     while x>0 do
     begin
          r:=r+f[j,x];
          if r>=z then r:=r mod z;
          x:=x-x and (-x);
     end;
     calc:=r;
end;

procedure add(j,x,t:longint);
begin
     while x<=maxn do
     begin
          f[j,x]:=f[j,x]+t;
          if f[j,x]>=z then f[j,x]:=f[j,x] mod z;
          x:=x+x and (-x);
     end;
end;

procedure pr;
var i,t,j,x:longint;
begin
     for i:=n downto 1 do
     begin
          x:=a[i];
          t:=calc(k-1,x-1);
          re:=re+t;
          if re>=z then re:=re mod z;
          for j:=k-1 downto 2 do
          begin
               t:=calc(j-1,x-1);
               if t>0 then add(j,x,t);
          end;
          add(1,x,1);
     end;
end;

procedure wf;
begin
     writeln(re);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 10000 + 5, MOD = 1000000000;
int a[N], v[N], n, k, inv[N], bit[N];

void enter() {
    scanf("%d%d",&n,&k);
    for(int i = 0; i < n; ++i)
        scanf("%d", a+i), v[i] = a[i];
}

int compress() {
    sort(v, v+n); int nVal = unique(v, v+n) - v;
    for(int i = 0; i < n; ++i)
        a[i] = lower_bound(v, v+nVal, a[i]) - v + 1;
    return nVal;
}

void add(int i, int v, int n) {
    for(; i <= n; i += i & -i) bit[i] = (bit[i] + v) % MOD;
}

int sum(int i) {
    int res = 0;
    for(; i > 0; i -= i & -i) res = (res + bit[i]) % MOD;
    return res;
}

void solve() {
    int nBIT = compress();
    for(int i = 0; i < n; ++i) inv[i] = 1;
    for(int l = 2; l <= k; ++l) {
        memset(bit, 0, sizeof bit);
        for(int i = n-1; i >= 0; --i) {
            add(a[i], inv[i], nBIT);
            inv[i] = sum(a[i] - 1);
        }
    }
    int res = 0;
    for(int i = 0; i < n; ++i) res = (res + inv[i]) % MOD;
    printf("%d\n", res);
}

int main() {
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

program kinv;
uses    math;
const   fi='';
        maxn=10005;
        maxk=11;
        base=trunc(1e9);
var     a:array[1..maxn] of longint;
        bit,f:array[0..maxk,0..maxn] of longint;
        inp:text;
        res,n,i,j,k:longint;

procedure update(i,j,v:longint);
begin
        while j<=n do
        begin
                bit[i,j]:=(bit[i,j]+v) mod base;
                j:=j + j and (-j);
        end;
end;

function get(i,j:longint):longint;
var     sum:longint;
begin
        sum:=0;
        while j>0 do
        begin
                sum:=(sum+bit[i,j]) mod base;
                j:=j-j and (-j);
        end;
        exit(sum);
end;

begin
        assign(inp,fi);reset(inp);
        readln(inp,n,k);
        for i:=1 to n do
        begin
                read(inp,a[i]);
                f[1,i]:=1;
        end;
        for i:=2 to k do
        begin
                for j:=n downto 1 do
                begin
                        f[i,j]:=get(i-1,a[j]);
                        update(i-1,a[j],f[i-1,j]);
                end;
        end;
        for j:=1 to n do res:=(res+f[k,j]) mod base;
        write(res);
end.

Code mẫu của RR

{$R+,Q+}
PROGRAM KINV;
CONST
  FINP='';
  FOUT='';
  maxn=10000;
  maxk=10;
  oo=1000000000;
VAR
  n,k:longint;
  a:array[1..maxn] of longint;
  d:array[1..maxk,1..maxn*6] of longint;
  kq:longint;
procedure readInput;
var
  f:text;
  i:longint;
begin
  assign(f,FINP); reset(f);
  readln(f,n,k);
  for i:=1 to n do
    begin
      read(f,a[i]);
      a[i]:=n-a[i]+1;
    end;
  close(f);
end;
procedure writeOutput;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
procedure update(i,l,r,j,k,s:longint);
var
  mid:longint;
begin
  if (l>k) or (r<k) then exit;
  if (l=k) and (r=k) then
    begin
      d[j,i]:=(d[j,i]+s) mod oo;
      exit;
    end;
  mid:=(l+r) div 2;
  update(i shl 1,l,mid,j,k,s);
  update(i shl 1+1,mid+1,r,j,k,s);
  d[j,i]:=(d[j,i shl 1]+d[j,i shl 1+1]) mod oo;
end;
function count(i,l,r,j,k:longint):longint;
var
  mid:longint;
begin
  if r<=k then begin count:=d[j,i]; exit; end;
  if k<l then begin count:=0; exit; end;
  mid:=(l+r) div 2;
  count:=(count(i shl 1,l,mid,j,k)+count(i shl 1+1,mid+1,r,j,k)) mod oo;
end;
procedure solve;
var
  i,j,s:longint;
begin
  for i:=1 to n do
    begin
      update(1,1,n,1,a[i],1);
      if a[i]>1 then
      for j:=2 to k do
        begin
          s:=count(1,1,n,j-1,a[i]-1);
          update(1,1,n,j,a[i],s);
          if j=k then kq:=(kq+s) mod oo;
        end;
    end;
end;
BEGIN
  readInput;
  solve;
  writeOutput;
END.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define maxn 300011
#define oo 1111111111
#define mod 1000000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i, a, b) for(int i = int(a); i <= int(b); i++)
#define FORD(i, a, b) for(int i = int(a); i >= int(b); i--)
//#include <conio.h>
//#define g 9.81

const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

long long f[10010][12] = {0};
int n, k, a[10010];

void update(int x, int i, long long add){
    while(x > 0){
        f[x][i] = (f[x][i] + add) % mod;
        x -= x & -x;
    }
}

long long get(int x, int i){
    long long ret = 0;
    while(x <= 10000){
        ret = (ret + f[x][i]) % mod;
        x += x & -x;
    }
    return ret;
}

int main(){
    //OPEN();
    scanf("%d %d", &n, &k);
    FOR(i, 1, n) scanf("%d", &a[i]);
    long long res = 0, t;
    FOR(j, 1, n){
        FOR(i, 1, k){
            if(i == 1) t = 1;
            else t = get(a[j] + 1, i - 1);
            update(a[j], i, t);
            if(i == k) res = (res + t) % mod;
        }
    }
    cout << res;
}

Code mẫu của ll931110

{$MODE DELPHI}
program KINV;
const
  input  = '';
  output = '';
  maxn = 10000;
  maxk = 10;
  base = 1000000000;
var
  b,pos,a: array[1..maxn] of integer;
  t: array[0..maxn,0..maxk] of integer;
  n,k: integer;

procedure init;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n,k);
  for i := 1 to n do
    begin
      read(f, b[i]);
      pos[i] := i;
    end;

  close(f);
end;

procedure swap(var x,y: integer);
var
  z: integer;
begin
  z := x;
  x := y;
  y := z;
end;

procedure quicksort;

  procedure partition(l,h: integer);
  var
    i,j,p: integer;
  begin
    if l >= h then exit;
    i := l;     j := h;     p := b[random(h - l + 1) + l];

    repeat
      while b[i] > p do inc(i);
      while b[j] < p do dec(j);

      if i <= j then
        begin
          if i < j then
            begin
              swap(b[i],b[j]);
              swap(pos[i],pos[j]);
            end;
          inc(i);
          dec(j);
        end;
    until i > j;

    partition(l,j);
    partition(i,h);
  end;

var
  i: integer;
begin
  partition(1,n);
  for i := 1 to n do a[pos[i]] := i;
end;

procedure update(x,y,z: integer);
begin
  while x <= maxn do
    begin
      t[x,y] := (t[x,y] + z) mod base;
      x := x + (x and -x);
    end;
end;

function calc(x,y: integer): integer;
var
  res: integer;
begin
  if x = 0 then exit(0);
  res := 0;
  while x > 0 do
    begin
      res := (res + t[x,y]) mod base;
      x := x - (x and -x);
    end;
  calc := res;
end;

procedure solve;
var
  i,j,tmp: integer;
begin
  fillchar(t, sizeof(t), 0);
  for i := 1 to n do
    begin
      for j := 2 to k do
        begin
          tmp := calc(a[i] - 1,j - 1);
          update(a[i],j,tmp);
        end;
      update(a[i],1,1);
    end;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, calc(n,k));
  close(f);
end;

begin
  init;
  quicksort;
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   10101
const int MOD=1e9;
int a[MAX];
int b[13][MAX];
int p[MAX];
int n,k,r;
void init(void) {
    scanf("%d",&n);
    scanf("%d",&k);
    int i,j;
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&a[i]);
        p[i]=i+(i&(-i));
    }
    for (i=1;i<=k;i=i+1)
        for (j=1;j<=n;j=j+1)
            b[i][j]=0;
    r=0;
}
void update(int t,int x,int val) {
    while ((0<x) && (x<n+1)) {
        b[t][x]=(b[t][x]+val)%MOD;
        x=p[x];
    }
}
int sum(int t,int x) {
    int s=0;
    while ((0<x) && (x<n+1)) {
        s=(s+b[t][x])%MOD;
        x=x&(x-1);
    }
    return (s);
}
void process(void) {
    int i,j;
    for (i=n;i>=1;i=i-1) {
        update(1,a[i],1);
        r=(r+sum(k-1,a[i]-1))%MOD;
        for (j=2;j<k;j=j+1) update(j,a[i],sum(j-1,a[i]-1));
    }
    printf("%d",r);
}
int main(void) {
    init();
    process();
    return 0;
}