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ố mất trật tự

    Số mất trật tự (derangement) DnD_nDn​ là số hoán vị của {1,2,…,n}\{1,2,\dots,n\}{1,2,…,n} sao cho không phần tử nào đứng đúng vị trí của nó. Ta có truy hồi Dn=(n−1)(Dn−1+Dn−2)D_n = (n-1)(D_{n-1}+D_{n-2})Dn​=(n−1)(Dn−1​+Dn−2​) với D0=1,D1=0D_0=1, D_1=0D0​=1,D1​=0.

    Cho nnn, tính Dn mod (109+7)D_n \bmod (10^9+7)Dn​mod(109+7).

    • Đị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 số nguyên là Dn mod (109+7)D_n \bmod (10^9+7)Dn​mod(109+7).

    Ví dụ:

    Đầu vào:

    4

    Đầu ra:

    9

    Giải thích:

    $D_4=9$: co 9 hoan vi cua 4 phan tu khong co diem co dinh.

    Đang tải editor...