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 hoán vị có đúng k điểm cố định

    Một điểm cố định của hoán vị σ\sigmaσ là vị trí iii thỏa σ(i)=i\sigma(i)=iσ(i)=i. Hãy đếm số hoán vị của nnn phần tử có đúng kkk điểm cố định. Công thức: chọn kkk vị trí cố định rồi nhân với số mất trật tự (derangement) của n−kn-kn−k phần tử còn lại:

    (nk) Dn−k.\binom{n}{k}\,D_{n-k}.(kn​)Dn−k​.

    Vì kết quả có thể lớn, hãy in nó modulo 109+710^9+7109+7.

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

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

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

      0≤n≤1060 \le n \le 10^60≤n≤106, 0≤k≤1060 \le k \le 10^60≤k≤106.

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

      Một dòng: số hoán vị có đúng kkk điểm cố định, lấy modulo 109+710^9+7109+7.

    Ví dụ:

    Đầu vào:

    4 1

    Đầu ra:

    8

    Giải thích:

    $\binom{4}{1}D_3=4\cdot 2=8$ hoán vị của 4 phần tử có đúng 1 điểm cố định.

    Đang tải editor...