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] Số Motzkin M_n

    Số Motzkin MnM_nMn​ đếm số đường đi từ (0,0)(0,0)(0,0) đến (n,0)(n,0)(n,0) dùng các bước (1,1),(1,0),(1,−1)(1,1),(1,0),(1,-1)(1,1),(1,0),(1,−1) không xuống dưới trục hoành. Chúng thỏa truy hồi

    (n+2)Mn=(2n+1)Mn−1+(3n−3)Mn−2,M0=M1=1.(n+2)M_n=(2n+1)M_{n-1}+(3n-3)M_{n-2},\quad M_0=M_1=1.(n+2)Mn​=(2n+1)Mn−1​+(3n−3)Mn−2​,M0​=M1​=1.

    Cho nnn, in Mn mod (109+7)M_n \bmod (10^9+7)Mn​mod(109+7) (mọi phép chia dùng nghịch đảo modular).

    • Đị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≤1060 \le n \le 10^60≤n≤106.

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

      Một dòng: Mn mod (109+7)M_n \bmod (10^9+7)Mn​mod(109+7).

    Ví dụ:

    Đầu vào:

    4

    Đầu ra:

    9

    Giải thích:

    Các số Motzkin đầu: $1,1,2,4,9$; vậy $M_4=9$.

    Đang tải editor...