Editorial for Phát giấy thi
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Đầ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{\text{TS}}{\text{MS}}\)
- Đến đây thì ta có thể duyệt một for để tính trực tiếp \(\text{TS} \text{ mod } (\text{1e9}+7)\) (chỉ có \(n\sim \text{1e5}\) phần tử). Còn ở \(\text{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}\)
Comments