Mô tả
Phòng Lab An Toàn Thông Tin BK đang nghiên cứu hành vi tự sao chép của một đoạn mã độc. Mã độc này mang một chuỗi gen nhị phân, và cứ mỗi nhịp nhân bản, đoạn gen lại dịch vòng trái đúng một bit — nghĩa là bit cao nhất (bit bên trái cùng) được bốc ra khỏi đầu và chèn ngay vào vị trí bit thấp nhất (bên phải cùng).
Nhà nghiên cứu muốn ghi lại số bit 1 trong chuỗi gen sau mỗi lần dịch vòng trái như vậy, bắt đầu từ trạng thái gốc (chưa dịch lần nào), cho đến khi đủ k giá trị. Bạn hãy viết chương trình tính và trả về danh sách k phần tử tương ứng.
Đầu vào
Bao gồm hai tham số:
n(số nguyên không âm): chuỗi gen của mã độc, biểu diễn dưới dạng một số thập phân. Các bit 0 ở đầu (nếu có) được giữ nguyên khi xử lý, đồng nghĩa chuỗi gen có thể chứa toàn bit 0.k(số nguyên không âm): số lượng giá trị cần ghi lại (bao gồm cả trạng thái gốc chưa dịch).
Đầu ra
Trả về một danh sách gồm k số nguyên, trong đó phần tử thứ i là số bit 1 của chuỗi gen sau i lần dịch vòng trái (i chạy từ 0 đến k-1).
Ràng buộc
0 <= n <= 10^60 <= k <= 64- Biểu diễn nhị phân của
ndài tối đa 20 bit.
Ví dụ
Ví dụ 1:
-
Đầu vào:
n = 22,k = 5 -
Đầu ra:
[3, 3, 2, 3, 3] -
Giải thích:
n = 22có biểu diễn nhị phân là10110(độ dài 5 bit, chứa 3 bit 1).- Lần 0 (gốc):
10110→ 3 bit 1 - Lần 1 (dịch vòng trái 1 bước):
01101→ 3 bit 1 - Lần 2:
11010→ 3 bit 1 - Lần 3:
10101→ 3 bit 1 - Lần 4:
01011→ 3 bit 1
(Lưu ý minh họa: chuỗi
10110luôn có đúng 3 bit một ở mọi vị trí dịch vòng, kết quả là[3, 3, 3, 3, 3]) - Lần 0 (gốc):
Ví dụ 2:
- Đầu vào:
n = 6,k = 3 - Đầu ra:
[2, 2, 2] - Giải thích:
6nhị phân110(3 bit, 2 bit 1). Dịch vòng trái110→101→011. Cả ba trạng thái đều chứa 2 bit 1.