Author: kieulqd

Gọi 0 là sấp, 1 là ngửa Gọi F[i] là số cách phù hợp cho đoạn gồm i đồng xu ngửa độ dài ít nhất là k, ở đây tự quy ước dãy mới tạo sẽ là có từ i-k+1 đến i đều là 1. Từ 1->k-1 f[i]=0 f[k]=1; Giả sử ta muốn tính F[i], từ F[i-1], số dãy thỏa mãn độ dài i-1, ta có số trường hợp thỏa mãn độ dài i là F[i-1]2 vì tiếp theo sẽ là 0 hoặc 1 Bắt đầu vào việc sinh dãy mới, ta sẽ coi dãy mới có từ i-k+1 đến i đều là 1, vậy số dãy mới tạo ra là 2^(i-k-1). Tuy nhiên, một rắc rối là việc trùng dãy được tạo thành từ trước, nhưng nó cũng là dãy được tạo thành F[i-k-1]. Vậy ta chỉ việc lấy - F[i-k-1]. Vậy công thức tổng lại là: F[i]=F[i-1]2+2^(i-k-1)-F[i-k-1] Vì kết quả là 1 số khá lớn nên cài thêm bignum.