trang chủ / đề bài / icpc25_reg_i

Đếm nghịch thế bất khả thi

Đề bài

Mô tả

Thầy Hành rất thích các con số. Hôm nay, trong giờ giảng thuật toán, thầy viết lên bảng một dãy số nguyên c1(0),c2(0),…,cn(0). Vì thầy Hành ghét sự lặp lại, dãy của thầy có một tính chất đặc biệt: không có giá trị nào xuất hiện trong dãy quá mười lần.

Vì bài giảng hôm nay nói về thứ tự từ điển, thầy Hành lần lượt gọi k sinh viên lên bảng. Mỗi sinh viên phải tạo một dãy số nguyên mới dựa trên dãy do sinh viên trước đó tạo ra (sinh viên đầu tiên dùng dãy của thầy Hành). Cụ thể, sinh viên thứ i (1≤i≤k) phải tạo một dãy n số nguyên c1(i),c2(i),…,cn(i) thỏa mãn các điều kiện sau:

  • c1(i),c2(i),…,cn(i) là một hoán vị của c1(i−1),c2(i−1),…,cn(i−1);
  • c1(i),c2(i),…,cn(i) lớn hơn c1(i−1),c2(i−1),…,cn(i−1) theo thứ tự từ điển;
  • c1(i),c2(i),…,cn(i) là dãy nhỏ nhất theo thứ tự từ điển trong tất cả các dãy thỏa mãn hai điều kiện trên.

Cả k sinh viên đều lên bảng và tìm ra dãy cần tìm chỉ trong vài giây, khiến thầy Hành bực mình. Có lẽ bạn đã biết, trong tiếng Việt, "hành" vừa là củ hành vừa là hành hạ. Vì vậy thầy Hành quyết định "hành" thêm một sinh viên nữa: thầy yêu cầu bạn ấy tính tổng số nghịch thế của cả k+1 dãy đang có trên bảng.

Bảng giờ đã kín số, cậu sinh viên kém may mắn nhanh chóng thấy chóng mặt. Bạn hãy giúp cậu ấy tìm kết quả.

Trong đề bài này:

  • Dãy β1,β2,…,βη là một hoán vị của dãy α1,α2,…,αη khi và chỉ khi tồn tại η số nguyên đôi một khác nhau ρ1,ρ2,…,ρη sao cho 1≤ρι≤η và βρι=αι với mọi 1≤ι≤η.
  • Dãy α nhỏ hơn dãy β theo thứ tự từ điển khi và chỉ khi một trong hai điều sau xảy ra: α là tiền tố của β và α≠β; hoặc tại vị trí đầu tiên mà α và β khác nhau, phần tử của α nhỏ hơn phần tử tương ứng của β.
  • Một nghịch thế của dãy α1,α2,…,αη là một cặp số nguyên (ι,κ) sao cho 1≤ι<κ≤η và αι>ακ.

Dữ liệu vào

Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu τ (1≤τ≤2·105). Tiếp theo là mô tả các bộ dữ liệu:

  • Dòng đầu tiên chứa hai số nguyên n và k (1≤n≤2·105; 0≤k≤2·107).
  • Dòng thứ hai chứa n số nguyên c1(0),c2(0),…,cn(0) (1≤ci(0)≤n).

Dữ liệu đảm bảo:

  • Không có giá trị nào xuất hiện trong dãy c1(0),c2(0),…,cn(0) quá mười lần.
  • k không vượt quá số hoán vị của c1(0),c2(0),…,cn(0) lớn hơn c1(0),c2(0),…,cn(0) theo thứ tự từ điển.
  • Tổng n qua tất cả các bộ dữ liệu không vượt quá 2·105.
  • Tổng k qua tất cả các bộ dữ liệu không vượt quá 2·107.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên trên một dòng: tổng số nghịch thế của cả k+1 dãy đã được tạo ra.

Ràng buộc

  • 1≤τ≤2·105.
  • 1≤n≤2·105, 0≤k≤2·107, 1≤ci(0)≤n.
  • Mỗi giá trị xuất hiện trong dãy ban đầu không quá mười lần.
  • k không vượt quá số hoán vị lớn hơn dãy ban đầu theo thứ tự từ điển.
  • Tổng n không vượt quá 2·105, tổng k không vượt quá 2·107.

Ví dụ

Input Output Giải thích
2
7 2
5 6 2 1 3 7 4
6 1
2 2 1 3 3 1
31
12
Bộ dữ liệu thứ nhất: (5,6,2,1,3,7,4) có 10 nghịch thế, (5,6,2,1,4,3,7) có 10 nghịch thế, (5,6,2,1,4,7,3) có 11 nghịch thế; tổng là 10+10+11=31. Bộ dữ liệu thứ hai: (2,2,1,3,3,1) có 6 nghịch thế, (2,2,3,1,1,3) có 6 nghịch thế; tổng là 6+6=12.
3
1 0
1
3 5
1 2 3
5 4
1 1 2 2 1
0
9
14
Ví dụ bổ sung (không có trong đề gốc). Bộ dữ liệu thứ hai đi qua cả sáu hoán vị của (1,2,3) với số nghịch thế 0,1,1,2,2,3. Bộ dữ liệu thứ ba: (1,1,2,2,1), (1,2,1,1,2), (1,2,1,2,1), (1,2,2,1,1), (2,1,1,1,2) có số nghịch thế 2,2,3,4,3.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0