JOI 2011 - Keycards

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Chìa khóa phòng ở khu lưu trú của cơ sở tổ chức trại xuân JOI là những tấm thẻ có đục lỗ. Có \(N\) vị trí có thể đục lỗ. Người ta đã tạo ra \(2^N\) chiếc chìa khóa khác nhau, tương ứng với tất cả các cách chọn những vị trí được đục lỗ.

Bạn nhận được một tập gồm từ \(1\) đến \(2^N\) chiếc chìa khóa để dùng trong trại xuân JOI. Khi xếp chồng các thẻ sao cho các vị trí có thể đục lỗ trùng nhau, bạn nhận thấy có đúng \(K\) vị trí mà tất cả các thẻ nhận được đều có lỗ.

Yêu cầu

Có bao nhiêu cách chọn tập chìa khóa nhận được để điều này xảy ra? Cho \(N\) và \(K\), hãy tính số cách đó lấy phần dư khi chia cho \(1\,000\,000\,007\), là một số nguyên tố.

Dữ liệu vào

Đọc từ đầu vào chuẩn một dòng chứa hai số nguyên \(N,K\), cách nhau bởi dấu cách.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số cách chọn tập chìa khóa thỏa mãn điều kiện, lấy phần dư khi chia cho \(1\,000\,000\,007\).

Ràng buộc

  • \(1\le N\le1\,000\,000\): số vị trí có thể đục lỗ.
  • \(0\le K\le N\): số vị trí mà tất cả các chìa khóa nhận được đều có lỗ.
  • Giới hạn thời gian CPU: \(1\) giây. Giới hạn bộ nhớ: \(64\) MB.

Thông tin kỹ thuật

Theo tài liệu kỹ thuật của kỳ thi gốc:

  • Chương trình phải kết thúc bình thường với mã trả về \(0\). Chỉ được tính điểm khi chương trình cho kết quả đúng, kết thúc bình thường và tuân thủ giới hạn thời gian, bộ nhớ.
  • Nếu không có quy định khác, giới hạn ngăn xếp là \(8\) MB. Cần chú ý tránh tràn ngăn xếp khi dùng đệ quy.
  • Một số bài có thể cần xử lý số nguyên vượt quá phạm vi \(32\) bit; khi đó, trong C/C++ cần dùng kiểu số nguyên \(64\) bit như long long, với định dạng %lld khi dùng scanf hoặc printf.
  • Với lượng dữ liệu vào/ra lớn, tài liệu khuyến nghị dùng scanf/printf thay cho cin/cout do tốc độ vào/ra trên hệ thống thi gốc.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(2\) bộ dữ liệu, mỗi bộ \(5\) điểm, và \(9\) bộ dữ liệu, mỗi bộ \(10\) điểm. Các tỉ lệ sau là tỉ lệ tích lũy:

  • Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(N\le10\).
  • Các bộ dữ liệu chiếm \(70\%\) tổng số điểm thỏa mãn \(N\le1000\).

Ví dụ

Ví dụ 1

Input 
3 3
Output 
1
Giải thích

Khi \(N=3\), có tất cả \(8\) chiếc chìa khóa. Ta đặt tên cho chúng theo hình dưới đây; cột bên trái mô tả các lỗ trên thẻ, cột bên phải là tên thẻ.

Thẻ không có lỗ được ký hiệu là \(\phi\); ba thẻ có một lỗ được gọi là \(A\), \(B\), \(C\); các thẻ có hai lỗ là \(AB\), \(BC\), \(AC\); thẻ có cả ba lỗ là \(ABC\).

Nếu chỉ nhận một thẻ \(ABC\), số vị trí mà tất cả các thẻ nhận được đều có lỗ là \(3\). Không có cách nhận thẻ nào khác cho đúng \(3\) vị trí như vậy. Do đó, chỉ có \(1\) cách thỏa mãn điều kiện.

Ví dụ 2

Input 
3 2
Output 
6
Giải thích

Nếu nhận hai thẻ \(\{AB,ABC\}\), có đúng \(2\) vị trí mà tất cả các thẻ nhận được đều có lỗ. Tương tự, các cách nhận \(\{AC,ABC\}\), \(\{BC,ABC\}\), \(\{AB\}\), \(\{AC\}\) và \(\{BC\}\) cũng có đúng \(2\) vị trí như vậy.

Ví dụ 3

Input 
3 1
Output 
30
Giải thích

Có \(30\) cách nhận thẻ thỏa mãn điều kiện, chẳng hạn \(\{A\}\), \(\{A,AB\}\), \(\{A,AC\}\), \(\{A,ABC\}\), \(\{A,AB,AC\}\), \(\{A,AB,ABC\}\), \(\{A,AC,ABC\}\), \(\{A,AB,AC,ABC\}\), \(\{AB,AC\}\) và \(\{AB,AC,ABC\}\).

Ví dụ 4

Input 
3 0
Output 
218

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: