Bài tập | NEU OJ

Thanh ghi dịch phản hồi tuyến tính (LFSR — Linear Feedback Shift Register) kiểu Fibonacci độ dài $L$ bit là một trong những thành phần cơ bản nhất của mã dòng (stream cipher).

Trạng thái của thanh ghi được biểu diễn bằng $L$ bit, đánh số vị trí $1, 2, \ldots, L$ từ trái sang phải trong chuỗi seed cho trước (vị trí 1 là bit "đầu ra", vị trí $L$ là bit "cuối" của thanh ghi).

Đa thức phản hồi được cho bởi một tập hợp $k$ vị trí tap (mỗi tap là một chỉ số từ $1$ đến $L$ ).

Tại mỗi bước dịch:

Bit đầu ra của bước này chính là bit đang ở vị trí 1 của trạng thái hiện tại.
Bit phản hồi mới $f$ = XOR (cộng modulo 2) của các bit tại tất cả vị trí tap, tính trên trạng thái hiện tại (trước khi dịch).
Trạng thái mới nhận được bằng cách dịch mọi bit sang trái một vị trí (bit vị trí 2 trở thành bit vị trí 1, v.v.) và chèn bit phản hồi $f$ vào vị trí cuối cùng ( $L$ ).

Cho seed ban đầu, danh sách tap và số bit cần sinh $m$ , hãy in ra $m$ bit đầu ra liên tiếp.

Ví dụ: Với $L=4$ , seed = 1000, tap = $\{4, 1\}$ , $m = 6$ :

Bước 1: trạng thái 1000 → đầu ra 1, $f = s_4 \oplus s_1 = 0 \oplus 1 = 1$ → trạng thái mới 0001
Bước 2: trạng thái 0001 → đầu ra 0, $f = 1 \oplus 0 = 1$ → trạng thái mới 0011
... tiếp tục cho đến khi đủ 6 bit đầu ra: 100011.

Định dạng đầu vào:
- Dòng 1: hai số nguyên $L$ và $m$ ( $1 \le L \le 20$ , $0 \le m \le 1000$ ) — độ dài thanh ghi và số bit cần sinh.
- Dòng 2: chuỗi seed gồm đúng $L$ ký tự 0/1 (trạng thái ban đầu, vị trí 1 → vị trí $L$ ).
- Dòng 3: số nguyên $k$ ( $1 \le k \le L$ ) — số lượng vị trí tap.
- Dòng 4: $k$ số nguyên phân biệt trong đoạn $[1, L]$ — các vị trí tap.
Định dạng đầu ra:
In ra đúng một dòng gồm $m$ ký tự 0/1 là $m$ bit đầu ra liên tiếp (không có khoảng trắng). Nếu $m = 0$ , in ra dòng trống.

solution

Đề bài: [An toàn thông tin] Sinh dãy bit từ thanh ghi dịch phản hồi tuyến tính (LFSR)