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ố Bell

    Số Bell BnB_nBn​ đếm số phân hoạch của một tập nnn phần tử thành các tập con không rỗng rời nhau. Có thể tính bằng tam giác Bell (Bell triangle):

    Bn+1=∑j=0n(nj)Bj,B0=1B_{n+1} = \sum_{j=0}^{n} \binom{n}{j} B_j, \quad B_0 = 1Bn+1​=∑j=0n​(jn​)Bj​,B0​=1

    Cho nnn, hãy tính Bn mod (109+7)B_n \bmod (10^9+7)Bn​mod(109+7).

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

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

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

      0≤n≤30000 \le n \le 30000≤n≤3000.

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

      Một số nguyên là Bn mod (109+7)B_n \bmod (10^9+7)Bn​mod(109+7).

    Ví dụ:

    Đầu vào:

    3

    Đầu ra:

    5

    Giải thích:

    Tap 3 phan tu co 5 phan hoach nen $B_3=5$.

    Đang tải editor...