Các lượt nộp

Danh sách bài

Báo lỗi

solution

Đề bài: [An toàn thông tin] Chu kỳ của LFSR

Chu kỳ của LFSR

Một LFSR Fibonacci bậc $n$ với trạng thái khác 0 sẽ tuần hoàn. Chu kỳ là số bước nhỏ nhất $T > 0$ để trạng thái quay lại trạng thái ban đầu.

Hãy tính chu kỳ $T$ . Với đa thức nguyên thủy thì $T = 2^n - 1$ (chu kỳ tối đa); với đa thức khác, $T$ có thể nhỏ hơn.

Ví dụ

$n=3$ , taps $1\,0\,1$ , trạng thái $0\,0\,1$ → $T = 7 = 2^3-1$ .

Định dạng đầu vào:
Dòng 1: $n$ . Dòng 2: taps. Dòng 3: trạng thái đầu (khác 0).
Ràng buộc đầu vào:
$1 \le n \le 18$ , trạng thái khác toàn 0.
Định dạng đầu ra:
Một số nguyên: chu kỳ $T$ .

Ví dụ:

Đầu vào:

3
1 0 1
0 0 1

Đầu ra:

7

Giải thích:

Đa thức x^3+x+1 nguyên thủy nên chu kỳ = 2^3-1 = 7.

Đang tải editor...