trang chủ / đề bài / icpc21_reg_f

Bảng xếp hạng chung cuộc

Đề bài

Mô tả

Sau kỳ thi ICPC Quốc gia Việt Nam, ban giám khảo đề xuất cách trao k loại huy chương cho các đội như sau:

  • Thứ hạng của một đội bằng số đội có điểm cao hơn đội đó cộng 1.
  • k loại huy chương được đánh số từ 1 đến k, huy chương có chỉ số nhỏ hơn ứng với thứ hạng tốt hơn.
  • Nếu thứ hạng của một đội là r và r≤k thì đội đó nhận huy chương loại r.

Dưới đây là một ví dụ về bảng xếp hạng chung cuộc của kỳ thi ICPC Quốc gia với 3 loại huy chương (vàng, bạc, đồng). Có thể thấy có những loại huy chương không được trao cho đội nào, và có thể có nhiều hơn k đội nhận huy chương. Trong ví dụ này, số huy chương mỗi loại là 2 vàng, 0 bạc và 2 đồng, viết gọn là [2,0,2].

Hạng Đội Điểm Huy chương
1 HCMUS-RationalKittens 12 Vàng
1 PENDLE 12 Vàng
3 Vaccinated 11 Đồng
3 Meld 11 Đồng
5 HCMUS-FlamingTomatoes 10
5 HCMUS-Clique 10
5 NANO 10
5 HCMIU_ThinkingTourists 10
9 Secret 9
9 ETHEREUM 9

Cho n (số đội) và k, hãy đếm số cách phân bố huy chương có thể xảy ra.

Dữ liệu vào

Một dòng chứa hai số nguyên n và k.

Dữ liệu ra

In ra một số nguyên là số cách phân bố huy chương có thể xảy ra. Vì số này có thể rất lớn, hãy in nó theo modulo 109+7.

Ràng buộc

  • 1≤k≤n≤106.

Ví dụ

Input Output Giải thích
4 3 8 Có 8 bảng xếp hạng: [1,1,1,1], [1,1,1,4], [1,1,3,3], [1,1,3,4], [1,2,2,2], [1,2,2,4], [1,2,3,3], [1,2,3,4], lần lượt cho các phân bố [4,0,0], [3,0,0], [2,0,2], [2,0,1], [1,3,0], [1,2,0], [1,1,2], [1,1,1], đôi một khác nhau.
4 2 6 Vẫn là 8 bảng xếp hạng trên, cho các phân bố [4,0], [3,0], [2,0], [2,0], [1,3], [1,2], [1,1], [1,1]: chỉ có 6 phân bố khác nhau.

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