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 
3
Note
  • 3 cách chia có thể là: \((1|1|3); (1|2|2); (2|1|2)\)

Bình luận


  • 2
    anhnguyenroux    10:53 p.m. 5 Tháng 6, 2020

    Ad cho em hỏi trong đề có một số test vd:
    4 3
    3 3 2
    có tổng các a[i] > m, mà đề bài nói sinh viên thứ i phải được phát không ít hơn ai tờ giấy thi, em nghĩ đáp án là 0 chứ ạ


    • 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}\)
      1 phản hồi