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] Chia kẹo (sao và vạch)

    Có nnn chiếc kẹo giống nhau chia cho kkk em bé (mỗi em có thể nhận 000 chiếc). Số cách chia bằng số nghiệm nguyên không âm của phương trình

    x1+x2+⋯+xk=n.x_1 + x_2 + \cdots + x_k = n.x1​+x2​+⋯+xk​=n.

    Theo bài toán sao và vạch (stars and bars), số cách bằng

    (n+k−1 k−1 ).\binom{n+k-1}{\,k-1\,}.(k−1n+k−1​).

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

    Ví dụ: n=3n=3n=3 kẹo, k=2k=2k=2 em: các cách (0,3),(1,2),(2,1),(3,0)(0,3),(1,2),(2,1),(3,0)(0,3),(1,2),(2,1),(3,0) — tổng 4=(41)4 = \binom{4}{1}4=(14​).

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

      Một dòng gồm hai số nguyên nnn (số kẹo) và kkk (số em bé).

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

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

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

      Một dòng: số cách chia theo modulo 109+710^9+7109+7.

    Ví dụ:

    Đầu vào:

    3 2

    Đầu ra:

    4

    Giải thích:

    Số nghiệm của $x_1+x_2=3$ là $\binom{3+2-1}{2-1}=\binom{4}{1}=4$.

    Đang tải editor...