Editorial for Xâu nhị phân
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.
Nếu gọi \(F[i][x]\) là số dãy nhị phân độ dài \(i\) và kết thúc là \(x\). Ta có công thức QHĐ:
\(F[i][x] = F[i-1][1 - x] + \sum F[j][x]\ \forall i - j \le k, j < i\).
Từ công thức trên ta thấy rằng chỉ cần 1 mảng 1 chiều \(F[i]\) là đủ :
\(F[i] = F[i-1] + \sum F[j] \ \forall i - j <= k\).
Nhưng độ phức tạp của thuật toán là \(O(n * k)\).
Ta đặt \(s = \sum F[j][x]\ \forall i - j \le k, j < i\)
khi chuyển từ \(i \rightarrow i+1\) thì \(s = s + F[i] - F[i-k]\).
Độ phức tạp thuật toán là \(O(n)\).
Nguồn: https://cowboycoder.tech/
Comments