• Mảng qhđ: \(F[i, j] (k ≤ i ≤ n, 0 ≤ j ≤ 1)\): số xâu nhị phân độ dài \(i\) có tối thiểu \(k\) chữ số \(0\) liên tiếp kết thúc bằng \(bit\ j\)
• \(F[k, 0] = 1; F[k, 1] = 0\);
• \(F[i, 1] = F[i – 1, 0] + F[i – 1, 1]\);
• \(F[i, 0] = F[i – 1, 0] + F[i – 1, 1] – F[i – k, 1] + 2^{(i – k – 1)}\);

Giải thích: Tính \(F[i, 0]\).
Ta xét lần lượt các xâu độ dài \(i\) kết thúc bằng \(t\) chữ số \(0\) liên tiếp

• Với \(1 ≤ t ≤ k – 1\) ta có số xâu thỏa mãn là \(F[i – t, 1]\)
• Với \(i > t ≥ k\) ta có số xâu thỏa mãn là \(2^{(i – t – 1)}\)
• Với \(t = i\) số xâu thỏa mãn là 1

\(\Rightarrow F[i,j]=\sum^{k-1}_{t=1}F[i-t,1]+2^0+2^1+...+2^{i-k-1}+1 = \sum^{k-1}_{t=1}F[i-t,1]+2^{i-k}\)

Vậy \(F[i-1,0]=\sum^{k-1}_{t=1}F[i-t-1,1]+2^{i-k-1}\)

\(\Rightarrow F[i,0]=F[i-1,0]+F[i-1,1]-F[i – k, 1] + 2{(i – k – 1)}\)