Để bỏ điều kiện $x_i\ge L$ đi, ta có thể làm như sau: đặt $y_i=x_i-L$, khi đó
ta có:
$$x_1+x_2+\dots+x_n=S$$
$$\Leftrightarrow (y_1+L)+(y_2+L)+\dots+(y_n+L)=S$$
$$\Leftrightarrow y_1+y_2+\dots+y_n=S-n\times L=S'$$
với $0\le y_i \le H-L$.
Vậy bây giờ ta chỉ cần tìm bộ nghiệm không âm cho $y$, mà chỉ xem xét điều kiện cận trên.
Tới đây thì ta đã có thể giải tương tự bài Phương trình bị ràng buộc 1, khác một chút là
không thể duyệt qua mọi tập con của $y$.
Gọi $f_k$ là số bộ nghiệm của $y$, trong đó có **ít nhất** $k$ số $y_i>H-L$, khi đó đáp án
cho bài toán là $f_0-f_1+f_2-\dots=\sum_{k=0}^{n} (-1)^k\times f_k$. Khi đã cố định $k$ số
không thỏa điều kiện cận trên thì coi như ta giải bài toán không hề có cận trên
đó, nhưng tổng bằng $S' - k\times(H-L+1)$. Đây là bài toán chia kẹo cơ bản,
vậy ta suy ra:
$$f_k = \binom{n}{k} \times \binom{S'-k\times(H-L+1)+n-1}{n-1} $$
Lưu ý rằng $\binom{n}{k}=0$ nếu $n<k$, kể cả khi $n<0$.
Độ phức tạp thời gian và bộ nhớ: $O(n+S)$.
Postnote: định nghĩa $f_k$ như vậy không đúng cho lắm, do trong $f_k$ thì ta có thể đếm
một bộ nghiệm nhiều lần, tuy nhiên với những bài bao hàm loại trừ thì cách tính đáp án như
vậy khá tự nhiên thôi.
tuongll
Created at
1 likes