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

    solution

    Đề bài: [Toán rời rạc] Đếm xâu nhị phân tránh mẫu 111

    Hãy đếm số xâu nhị phân độ dài nnn không chứa ba số 1 liên tiếp (mẫu cấm 111). Đây là dãy Tribonacci dịch chuyển: gọi f(n)f(n)f(n) là số xâu hợp lệ thì f(n)=f(n−1)+f(n−2)+f(n−3)f(n)=f(n-1)+f(n-2)+f(n-3)f(n)=f(n−1)+f(n−2)+f(n−3) với f(0)=1,f(1)=2,f(2)=4f(0)=1,f(1)=2,f(2)=4f(0)=1,f(1)=2,f(2)=4. In f(n) mod (109+7)f(n)\bmod(10^9+7)f(n)mod(109+7). Quy ước xâu rỗng (n=0n=0n=0) là hợp lệ.

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

      Một dòng chứa số nguyên nnn.

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

      0≤n≤1070 \le n \le 10^70≤n≤107.

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

      Một dòng: số xâu hợp lệ modulo 109+710^9+7109+7.

    Ví dụ:

    Đầu vào:

    3

    Đầu ra:

    7

    Giải thích:

    Trong 8 xâu độ dài 3 chỉ có `111` bị cấm; còn lại 7 xâu hợp lệ.

    Đang tải editor...