Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] Kiểm tra đa thức nguyên thủy (chu kỳ tối đa)

    Đa thức nguyên thủy?

    Một đa thức phản hồi bậc nnn là nguyên thủy khi LFSR tương ứng đạt chu kỳ tối đa 2n−12^n - 12n−1 (đi qua tất cả 2n−12^n-12n−1 trạng thái khác 0).

    Cho taps bậc nnn, hãy kiểm tra: bắt đầu từ trạng thái 0…010\dots010…01, LFSR có chu kỳ đúng bằng 2n−12^n-12n−1 và không bao giờ rơi vào trạng thái 0 hay không. In YES/NO.

    Ví dụ

    taps 1 0 11\,0\,1101 (x3+x+1x^3+x+1x3+x+1) → YES. taps 1 1 11\,1\,1111 → NO.

    • Định dạng đầu vào:

      Dòng 1: nnn. Dòng 2: taps c1…cnc_1 \dots c_nc1​…cn​.

    • Ràng buộc đầu vào:

      1≤n≤181 \le n \le 181≤n≤18.

    • Định dạng đầu ra:

      YES nếu nguyên thủy (chu kỳ 2n−12^n-12n−1), ngược lại NO.

    Ví dụ:

    Đầu vào:

    3
1 0 1

    Đầu ra:

    YES

    Giải thích:

    x^3+x+1 đạt chu kỳ 7 = 2^3-1 nên nguyên thủy -> YES.

    Đang tải editor...