let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

SPBINARY - Xâu Nhị Phân

solution.md

Bài này ta dùng QHĐ.

Gọi \(f0[i]\) là số dãy nhị phân thỏa đề bài, có độ dài \(i\) và kết thúc bằng số 0.

Tương tự, gọi \(f1[i]\) là số dãy nhị phân thỏa đề bài, có độ dài \(i\) và kết thúc bằng số 1.

Kết quả bài toán: \(f0[n] + f1[n]\)

Trường hợp cơ bản: \(f0[0] = f1[0] = 1\).

Để tính \(f0[i]\), ta tính tổng của \(k\) trường hợp:

  • Dãy kết thúc với 1 số 0: \(f1[i-1]\)
  • Dãy kết thúc với 2 số 0: \(f1[i-2]\)
  • …
  • Dãy kết thúc với k số 0: \(f1[i-k]\)

Tương tự với \(f1[i]\).

Bài này cần cài đặt xử lý số lớn, code mẫu dùng Python cho đơn giản.

Có thể tính công thức trên trong \(O(n \times k)\), tuy nhiên để giảm số phép cộng cần thực hiện, ta lưu 2 biến tổng cộng dồn sum_f0 và sum_f1. Cập nhật sum_f0 -= f0[i-k-1] trước khi tính \(f0[i]\), sau khi tính \(f0[i]\), cập nhật lại sum_f0 += f0[i].

main.py
Open in Github • Download 
n, k = (int(x) for x in input().split())

f0 = [0 for i in range(n+1)]
f1 = [0 for i in range(n+1)]

f0[0] = 1
f1[0] = 1

sum_f0 = f0[0]
sum_f1 = f1[0]

for i in range(1, n+1):
    if i-k-1 >= 0:
        sum_f1 -= f1[i-k-1]
        sum_f0 -= f0[i-k-1]
    f0[i] = sum_f1
    f1[i] = sum_f0

    sum_f0 += f1[i]
    sum_f1 += f0[i]

print(f0[n] + f1[n])
Comments