Editorial for Dãy nghịch thế độ dài K
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 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; }
Comments