Editorial for Educational Backtracking: Đếm dãy GCD


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.

Ta chia các phần tử của dãy ~a~ thành hai loại phần tử: loại phần tử có giá trị bị ảnh hưởng bởi ít nhất một điều kiện trong ~m~ điều kiện (gọi là loại ~1~) và loại phần tử có giá trị không bị ảnh hưởng bởi bất kỳ điều kiện nào (gọi là loại ~2~).

  • Đối với các phần tử loại ~1~, ta thấy rằng bất kỳ phần tử nào cũng chỉ có thể nhận tối đa ~\lfloor \frac{x_{max}}{v_{min}} \rfloor~ (~\lfloor \frac{12}{2} \rfloor = 6~) giá trị khác nhau. Như vậy, số lượng cấu hình chỉ chứa riêng các phần tử loại ~1~ là ~B \le 6^n~, độ phức tạp backtrack để đếm số lượng cấu hình như thế tốn tối đa ~6^n \cdot m~.

  • Đối với các phần tử loại ~2~, các phần tử có thể nhận bất kỳ giá trị thuộc ~[1, x]~ mà vẫn làm cho dãy thoả mãn, số lượng cấu hình chỉ chứa các phần tử loại ~2~ là ~x^v~ (với ~v~ là số lượng phần tử loại ~2~). Đáp án chính là ~B*x^v~.

Độ phức tạp: ~O(6^n \cdot m)~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.