T và H là 1 đôi bạn chơi rất thân cùng nhau vào tuyển quốc gia. Thay vì tập trung vào đội tuyển, 2 bạn lại duo rank game rác LQ "thắng bại tại nạp tiền". Sau khi tạch giải quốc gia, nhận ra LQ quá trash, H đã nghe theo tiếng gọi của đấu trường công lý như đàn anh đz, ngầu lòi của mình.
Ngoài tài năng làm nền cho highlight của đối thủ trong mỗi game đấu, T còn có những bài toán giúp làm giảm đi trí thông minh của người chơi. Sau 6996 lần thua H, hôm nay T đã chuẩn bị n viên sỏi để thách đấu với H, bài toán là tìm số cách bỏ ra m viên để còn lại đúng c phần. Trong khi T lọ mọ ngồi đếm, H chưa đến 1s đã có thể tìm ra. Các bạn hãy cùng thử giải bài toán này nhé.
Dòng đầu tiên ở mỗi file input chứa T - số bộ test. Mỗi bộ test có format như sau:
1 dòng duy nhất chứa 3 số nguyên N, M, C.
1 dòng duy nhất chứa kết quả bài toán
1 ≤ T ≤ 100000.
1 ≤ M ≤ N, 0 ≤ C ≤ N - M.
20% số test ứng với N ≤ 15
30% số test ứng với N ≤ 30, T ≤ 100
20% số test ứng với N ≤ 1000
30% số test ứng với N ≤ 100000
3 5 2 3 3 1 2 4 3 1
1 1 4
Giải thích test 1: {2, 4}
Giải thích test 2: {2}
Giải thích test 3: {2, 3, 4}, {1, 3, 4}, {1, 2, 4}, {1, 2, 3}
B là một anh chàng chuyên tin đz, ngầu lòi. Anh chàng coder của chúng ta hiện đang crush một cô nàng chuyên Nga xinh xắn, hiền lành, C. Nhưng do khoảng cách địa lý giữa hai tòa nhà A1 và A2 nên B không thể nhìn thấy C mỗi giờ ra chơi.
Nhưng dựa vào tài năng "Hắc cơ" của mình, anh đã hack được camera của trường chỉ dựa vào chiếc điện thoại của mình. Nhưng anh không ngờ rằng ông mặt nhăn bảo vệ trường thật ra chính là trùm cuối trong đường dây gian lận thi cử.
Ông đã thiết kế mạng lưới camera rất tinh vi, là một mạng liên thông có N - 1 đường kết nối, không có chu trình và một số camera cần có mật khẩu mới có thể truy cập. Tất nhiên B vẫn phá được mật khẩu nhưng sẽ bị mất 1 năng lượng pin điện thoại. Bạn hãy giúp B đếm số cách sử dụng đúng K năng lượng để truy cập các camera để anh có thể triệt phá đường dây và chinh phục crush của mình nhé.
Dòng đầu tiên chứa 2 số nguyên N, K lần lượt là số camera và số năng lượng pin.
Dòng thứ hai chứa N số nguyên là 0 / 1 biểu thị camera thứ i có mật khẩu hay không.
N - 1 dòng tiếp theo chứa 2 số nguyên u, v biểu thị có đường kết nối giữa camera u và camera v.
In ra một dòng duy nhất là kết quả bài toán.
1 ≤ N ≤ 50000.
1 ≤ K ≤ 100.
20% số test với N ≤ 25.
30% số test với N ≤ 1000.
20% số test với K ≤ 10.
5 2 0 1 0 1 1 1 2 1 3 1 4 2 5
5
3 1 1 0 1 1 2 1 3
3
3 0 1 1 0 1 2 2 3
1
Giải thích test 1: {1, 2, 3}, {2, 5}, {1, 3, 4}, {1, 2, 5}, {1, 2, 4}.
Giải thích test 2: {1}, {3}, {1, 2}.
Giải thích test 3: {}. (tập rỗng)
Đằng sau sự thành công của Bitcoin, không thể không kể đến công nghệ Blockchain. Blockchain hoạt động dựa trên các khối liên kết với nhau tạo thành một chuỗi. Điều đặc biệt ở đây chính là blockchain có độ bảo mật rất cao, không thể thay đổi.
Hacker b21 đã gây chấn động toàn cầu khi đã tìm ra cách hack được Blockchain. Anh đã mã hóa toàn bộ các block trở thành một số N. Số N này phải thỏa mãn điều kiện sau:
- Là một số tự nhiên.
- Chia hết cho x.
- thuộc khoảng [A, B].
- UCLN của chữ số thứ i tính từ phải qua trái và i phải bằng 1. (Ví dụ: 321 không thỏa mãn vì UCLN(1, 1) = 1, UCLN(2, 2) = 2, UCLN(3, 3) = 3 nhưng 231 thỏa mãn vì UCLN(1, 1) = 1, UCLN(3, 2) = 1, UCLN(2, 3) = 1) .
- Bao gồm các chữ số cho trước
Các bạn hãy giúp b21 tìm ra số lượng các số như thế nhé.
Dòng đầu tiên chứa ba số nguyên A, B, X.
Dòng thứ hai có xâu S chứa các chữ số 0..9 theo thứ tự tăng dần là các số có trong N
Chứa duy nhất 1 số nguyên là phần dư của phép chia kết quả bài toán cho 109 + 7
B ≤ A
10% số test ứng với A, B, X ≤ 103
30% số test ứng với A, B ≤ 106, X ≤ 105
30% số test ứng với A, B, X ≤ 1011
30% số test ứng với A, B ≤ 10100, X ≤ 105
1 20 2 1234789
6
1 20 3 0123678
4
Giải thích test 1: 2, 4, 8, 12, 14, 18
Giải thích test 2: 3, 6, 12, 18