Tổ hợp, Chỉnh hợp, Hoán vị

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Tổ hợp 100 (p) 2.0s 256M
2 Đếm tập con không lặp không thứ tự 100 (p) 1.0s 256M
3 Đếm tập con không lặp có thứ tự 100 (p) 1.0s 256M
4 #11 - Hoán vị 100 (p) 1.0s 256M
5 #11 - Chỉnh hợp 100 (p) 1.0s 256M
6 #11 - Tổ hợp 100 (p) 1.0s 256M
7 #11 - Chia kẹo Euler 100 (p) 1.0s 256M
8 #11 - Chia kẹo Euler nhưng ai cũng có kẹo 100 (p) 1.0s 256M

1. Tổ hợp

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho số nguyên tố \(p\). Với mỗi truy vấn gồm hai số \(n, k\), bạn hãy đếm xem có bao nhiêu cách chọn \(k\) quả táo từ \(n\) quả cho trước. Vì đáp số rất lớn nên bạn chỉ cần in ra đáp số \(\mod p\).

Input

  • Dòng đầu tiên chứa 2 số nguyên dương \(t, p \ (1 \leq t \leq 10^5)\), số lượng truy vấn và số nguyên tố cho trước.
  • \(t\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(n, k\).

Output

Với mỗi truy vấn, in ra một số nguyên là đáp số của truy vấn đó.

Scoring

  • Subtask \(1\) (\(25\%\) số điểm): \(n, k \leq 1000; p \leq 10^9 + 7\)
  • Subtask \(2\) (\(25\%\) số điểm): \(n, k \leq 10^5; p = 10^9 + 7\)
  • Subtask \(3\) (\(50\%\) số điểm): \(n, k \leq 10^5; p \leq 10^9 + 7\)

Example

Test 1

Input 
 4 5
4 2
3 2
3 4
7 2
Output 
1
3
0
1

2. Đếm tập con không lặp không thứ tự

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bạn được cho hai số nguyên \(n\) và \(k\).

Yêu cầu: Hãy in ra số tập con khác nhau gồm \(k\) phần tử (không được lặp) trong các số nguyên từ \(1\) đến \(n\).

Hai tập con được xem là khác nhau khi tồn tại một phần tử thuộc tập này nhưng không thuộc tập kia.

Ví dụ: \((1, 2)\) là một tập con thỏa mãn. \((1, 2, 2)\) không thỏa mãn vì \(2\) xuất hiện \(2\) lần. \((1, 2, 3)\) và \((1, 3, 2)\) là hai tập con giống nhau.

Input

  • Chứa số hai số nguyên \(n\) và \(k\) \((1 \le k \leq n \le 10^6)\).

Output

  • Chứa một số nguyên là đáp án của bài toán khi chia lấy dư cho \(10^9 + 7\).

Example

Test 1

Input 
6 2
Output 
15

3. Đếm tập con không lặp có thứ tự

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bạn được cho hai số nguyên \(n\) và \(k\).

Yêu cầu: Hãy in ra số tập con khác nhau gồm \(k\) phần tử (không được lặp) trong các số nguyên từ \(1\) đến \(n\).

Hai tập con được xem là khác nhau khi tồn tại một vị trí mà phần tử ở vị trí đó trong hai tập là khác nhau.

Ví dụ: \((1, 2, 3)\) là một tập con thỏa mãn. \((1, 2, 2)\) không thỏa mãn vì giá trị \(2\) xuất hiện \(2\) lần. \((1, 2, 3)\) và \((1, 3, 2)\) là hai tập con khác nhau.

Input

  • Chứa số hai số nguyên \(n\) và \(k\) \((1 \le k \leq n \le 10^6)\).

Output

  • Chứa một số nguyên là đáp án của bài toán khi chia lấy dư cho \(10^9 + 7\).

Example

Test 1

Input 
6 2
Output 
30

4. #11 - Hoán vị

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho tập hợp \(A\) gồm \(n\) phần tử, có bao nhiêu mảng hoán vị \(n\) phần tử của tập \(A\)?

Dữ liệu đầu vào

  • Gồm một số \(n\) duy nhất

Định dạng đầu ra

  • In ra đáp án chia lấy dư cho \(10^9+7\)

Điểm số

  • Subtask \(1\) (\(50\%\) số điểm): \(n \leq 20\)
  • Subtask \(2\) (\(25\%\) số điểm): \(n \leq 1000\)
  • Subtask \(3\) (\(25\%\) số điểm): \(n \leq 10^6\)

Ví dụ

Ví dụ 1

Đầu vào 
5
Đầu ra 
120

5. #11 - Chỉnh hợp

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho tập hợp \(A\) gồm \(n\) phần tử.
Một mảng \(B\) độ dài \(k\) được gọi là chỉnh hợp của \(A\) nếu mỗi phần tử trên \(B\) chỉ xuất hiện duy nhất một lần, và các phần tử đều xuất hiện trong \(A\).
Có bao nhiêu cách xếp mảng \(B\) khác nhau?

Dữ liệu đầu vào

  • Gồm hai số \(n\) và \(k\) \((k \leq n)\)

Định dạng đầu ra

  • In ra đáp án chia lấy dư cho \(10^9+7\)

Điểm số

  • Subtask \(1\) (\(50\%\) số điểm): \(n \leq 20\)
  • Subtask \(2\) (\(25\%\) số điểm): \(n \leq 1000\)
  • Subtask \(3\) (\(25\%\) số điểm): \(n \leq 10^6\)

Ví dụ

Ví dụ 1

Đầu vào 
5 3
Đầu ra 
60

6. #11 - Tổ hợp

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho tập hợp \(A\) gồm \(n\) phần tử.
Một tập hợp \(B\) độ dài \(k\) được gọi là tổ hợp của \(A\) nếu \(B\) là tập hợp con của \(A\).
Có bao nhiêu cách chọn tập hợp \(B\) khác nhau?

Dữ liệu đầu vào

  • Gồm hai số \(n\) và \(k\) \((k \leq n)\)

Định dạng đầu ra

  • In ra đáp án chia lấy dư cho \(10^9+7\)

Điểm số

  • Subtask \(1\) (\(50\%\) số điểm): \(n \leq 20\)
  • Subtask \(2\) (\(25\%\) số điểm): \(n \leq 1000\)
  • Subtask \(3\) (\(25\%\) số điểm): \(n \leq 10^6\)

Ví dụ

Ví dụ 1

Đầu vào 
5 3
Đầu ra 
10

7. #11 - Chia kẹo Euler

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có \(n\) chiếc kẹo, có bao nhiêu cách chia kẹo bất kỳ cho \(k\) bạn, mà có thể có bạn không nhận được kẹo?

Dữ liệu đầu vào

  • Gồm hai số \(n\) và \(k\) \((k \leq n)\)

Định dạng đầu ra

  • In ra đáp án chia lấy dư cho \(10^9+7\)

Điểm số

  • Subtask \(1\) (\(50\%\) số điểm): \(n \leq 20\)
  • Subtask \(2\) (\(25\%\) số điểm): \(n \leq 1000\)
  • Subtask \(3\) (\(25\%\) số điểm): \(n \leq 10^6\)

Ví dụ

Ví dụ 1

Đầu vào 
5 3
Đầu ra 
21

8. #11 - Chia kẹo Euler nhưng ai cũng có kẹo

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có \(n\) chiếc kẹo, có bao nhiêu cách chia kẹo bất kỳ cho \(k\) bạn, mà bạn nào cũng được nhận kẹo?

Dữ liệu đầu vào

  • Gồm hai số \(n\) và \(k\) \((k \leq n)\)

Định dạng đầu ra

  • In ra đáp án chia lấy dư cho \(10^9+7\)

Điểm số

  • Subtask \(1\) (\(50\%\) số điểm): \(n \leq 20\)
  • Subtask \(2\) (\(25\%\) số điểm): \(n \leq 1000\)
  • Subtask \(3\) (\(25\%\) số điểm): \(n \leq 10^6\)

Ví dụ

Ví dụ 1

Đầu vào 
5 3
Đầu ra 
6