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ố Stirling loại hai

    Số Stirling loại hai S(n,k)S(n,k)S(n,k) đếm số cách phân hoạch tập nnn phần tử thành đúng kkk tập con không rỗng. Công thức truy hồi:

    S(n,k)=k⋅S(n−1,k)+S(n−1,k−1),S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1),S(n,k)=k⋅S(n−1,k)+S(n−1,k−1),

    với S(0,0)=1S(0,0)=1S(0,0)=1 và S(n,0)=0S(n,0)=0S(n,0)=0 khi n>0n>0n>0.

    Cho n,kn, kn,k, hãy tính S(n,k) mod (109+7)S(n,k) \bmod (10^9+7)S(n,k)mod(109+7).

    Ví dụ: S(4,2)=7S(4,2)=7S(4,2)=7 (7 cách chia 4 phần tử thành 2 nhóm).

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

      Một dòng gồm hai số nguyên nnn và kkk.

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

      0≤k≤n≤20000 \le k \le n \le 20000≤k≤n≤2000.

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

      Một dòng: S(n,k) mod (109+7)S(n,k) \bmod (10^9+7)S(n,k)mod(109+7).

    Ví dụ:

    Đầu vào:

    4 2

    Đầu ra:

    7

    Giải thích:

    Chia 4 phần tử thành đúng 2 nhóm không rỗng có 7 cách → $S(4,2)=7$.

    Đang tải editor...