Fibonacci vs Galois: đếm bit khác nhau

Với cùng taps và cùng trạng thái đầu, LFSR Fibonacci và Galois (theo định nghĩa ở các bài trước) thường sinh ra hai chuỗi keystream khác nhau. Hãy sinh $k$ bit từ cả hai cấu hình và đếm số vị trí mà hai chuỗi khác nhau.

Fibonacci: XOR các tap rồi đưa vào cuối.
Galois: dịch, đưa bit xuất vào cuối, nếu bit xuất = 1 thì XOR taps vào trạng thái.

Ví dụ

Với taps $1\,0\,1$ , trạng thái $0\,0\,1$ , $k=7$ → số vị trí khác nhau là một giá trị xác định.

Định dạng đầu vào:
Dòng 1: $n$ . Dòng 2: taps. Dòng 3: trạng thái đầu. Dòng 4: $k$ .
Ràng buộc đầu vào:
$1 \le n \le 16$ , $1 \le k \le 100000$ .
Định dạng đầu ra:
Một số nguyên: số vị trí hai chuỗi khác nhau.

solution

Đề bài: [An toàn thông tin] So sánh Fibonacci và Galois LFSR

Fibonacci vs Galois: đếm bit khác nhau

Ví dụ