Hướng dẫn cho Phát giấy thi
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
- Đầ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}\)
Bình luận