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ố đơn ánh và toàn ánh

    Cho hai tập hữu hạn ∣A∣=n|A| = n∣A∣=n và ∣B∣=m|B| = m∣B∣=m. Hãy đếm:

    • Số đơn ánh (injective) từ AAA vào BBB: bằng m⋅(m−1)⋯(m−n+1)m \cdot (m-1) \cdots (m-n+1)m⋅(m−1)⋯(m−n+1) nếu n≤mn \le mn≤m, ngược lại 000.
    • Số toàn ánh (surjective) từ AAA lên BBB: bằng ∑i=0m(−1)i(mi)(m−i)n\sum_{i=0}^{m} (-1)^i \binom{m}{i} (m-i)^n∑i=0m​(−1)i(im​)(m−i)n.

    In hai giá trị này, mỗi giá trị lấy  mod (109+7)\bmod (10^9+7)mod(109+7).

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

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

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

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

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

      Hai số nguyên cách nhau bởi dấu cách: số đơn ánh và số toàn ánh, cùng  mod (109+7)\bmod (10^9+7)mod(109+7).

    Ví dụ:

    Đầu vào:

    3 3

    Đầu ra:

    6 6

    Giải thích:

    Tu tap 3 phan tu vao tap 3 phan tu: so don anh $=3!=6$, so toan anh cung $=6$.

    Đang tải editor...