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 số toàn ánh giữa hai tập hữu hạn

    Số toàn ánh (surjection) từ tập nnn phần tử lên tập kkk phần tử bằng k!⋅S(n,k)k!\cdot S(n,k)k!⋅S(n,k) với S(n,k)S(n,k)S(n,k) là số Stirling loại hai, cũng cho bởi công thức bao hàm–loại trừ

    ∑i=0k(−1)i(ki)(k−i)n.\sum_{i=0}^{k}(-1)^i\binom{k}{i}(k-i)^n.∑i=0k​(−1)i(ik​)(k−i)n.

    Cho n,kn,kn,k, in số toàn ánh modulo 109+710^9+7109+7. Lưu ý nếu k>nk>nk>n kết quả là 0; với n=k=0n=k=0n=k=0 kết quả là 1.

    • Đị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ố toàn ánh modulo 109+710^9+7109+7.

    Ví dụ:

    Đầu vào:

    3 2

    Đầu ra:

    6

    Giải thích:

    Toàn ánh từ tập 3 phần tử lên tập 2 phần tử: $2!\,S(3,2)=2\cdot 3=6$.

    Đang tải editor...