Phát giấy thi

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

Small

Dạng bài

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

Giáo sư X sắp phải đi họp và ông chuẩn bị một bài tập làm văn cho sinh viên làm trong thời gian ông đi vắng. Giáo sư X có \(m\) tờ giấy thi để phát cho \(n\) sinh viên. Tùy theo trình độ viết dài, viết hỏng của từng người, ông xác định chính xác được rằng sinh viên thứ i phải được phát không ít hơn ai tờ giấy thi.

Yêu cầu : Đếm số cách phát \(m\) tờ giấy thi cho \(n\) sinh viên theo yêu cầu trên. Hai cách phát giấy thi được gọi là khác nhau nếu tồn tại một sinh viên nhận được số tờ giấy thi khác nhau trong hai cách đó.

Input

Dòng 1 chứa hai số nguyên dương \(m \leq 10^9;n \leq 10^5\)
Dòng 2 chứa 𝑛 số nguyên dương \(a_1,a_2,\ldots,a_n(∀i:ai \leq 10^9)\)

Output

Ghi ra một số nguyên duy nhất là số dư của phép chia kết quả tìm được cho \(10^9+7\).

Example

Test 1

Input

5 3 
1 1 2

Output

Note

3 cách chia có thể là: \((1|1|3); (1|2|2); (2|1|2)\)

Bình luận

14
jumptozero 6:44 a.m. 4 Tháng 6, 2020
Mình xin đóng góp lời giải bài này như sau:

Đầu tiên gọi \(x_i\) là số giấy của mỗi thí sinh được phát. Theo đề \(x_i\ge a_i(\forall i=\overline{1,n})\)
Khi đó theo đề ta có: \(x_1+x_2+...+x_n=m(1)\)

Gọi \(y_i=x_i-a_i(\forall i=\overline{1,n})\implies x_i=y_i+a_i\text{ và }y_i\ge 0\forall i=\overline{1,n}\)

Khi đó \((1)\iff y_1+y_2+...+y_n=m-\sum\limits_{i=1}^{n}a_i\)

Đặt \(S=m-\sum\limits_{i=1}^{n}a_i\implies y_1+y_2+...+y_n=S\)

Lúc này ta quy về đếm số nghiệm không âm của phương trình trên:

Gọi \(Res\) là số nghiệm của phương trình trên trình, khi đó:

Nếu \(S<0\) thì \(Res=0\). Nếu \(S>0\) thì \(Res=\binom{S+n-1}{n-1}=\frac{(S+n-1)!}{S!(n-1)!}\) (Đây là kết quả của bài toán chia kẹo Euler, các bạn có thể search trên mạng)

Tiếp theo là phần code. Ở đây ta chú ý vì \(S\) khá lớn \(S\sim 10^9\) do đó ở đây ta sẽ xử lý \(Res\) một chút để khỏi bị TLE hoặc RuntimeError như sau.

Ta có \(Res=\binom{S+n-1}{n-1}=\frac{(S+n-1)!}{S!(n-1)!}=\frac{(S+1)(S+2)...(S+n-1)}{(n-1)!}=\frac{TS}{MS}\)

Đến đây thì ta có thể duyệt một for để tính trực tiếp \(TS \text{ mod } (1e9+7)\) (chỉ có \(n\sim 1e5\) phần tử). Còn ở \(MS\) thì đã quá quen thuộc, chúng ta chỉ cần sử dụng \(\text{Inverse mod}\) là tính được ngay.
Các bạn có thể tham khảo code mình tại \(\href{https://ideone.com/9ZBp9P}{đây}\)

5

CaiWinDao 11:45 a.m. 4 Tháng 6, 2020

Cảm ơn bạn. Mình đã cập nhật vào mục editorial.

1 bình luận nữa