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] Hoán vị có lặp

    Cho một từ có nnn ký tự, gồm kkk loại ký tự khác nhau với số lần xuất hiện lần lượt là n1,n2,…,nkn_1, n_2, \ldots, n_kn1​,n2​,…,nk​ (với n1+⋯+nk=nn_1+\cdots+n_k = nn1​+⋯+nk​=n). Số hoán vị phân biệt của các ký tự này là

    n!n1! n2!⋯nk!.\frac{n!}{n_1!\,n_2!\cdots n_k!}.n1​!n2​!⋯nk​!n!​.

    Hãy tính giá trị đó theo modulo 109+710^9+7109+7.

    Ví dụ: từ "MISSISSIPPI" có n=11n=11n=11, với M:1, I:4, S:4, P:2 → số hoán vị =11!1! 4! 4! 2!=34650=\frac{11!}{1!\,4!\,4!\,2!}=34650=1!4!4!2!11!​=34650.

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

      Dòng 1: số nguyên kkk (số loại ký tự). Dòng 2: kkk số nguyên dương n1,…,nkn_1,\ldots,n_kn1​,…,nk​.

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

      1≤k≤1001 \le k \le 1001≤k≤100, 1≤ni1 \le n_i1≤ni​, ∑ni≤106\sum n_i \le 10^6∑ni​≤106.

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

      Một dòng: số hoán vị phân biệt theo modulo 109+710^9+7109+7.

    Ví dụ:

    Đầu vào:

    4
1 4 4 2

    Đầu ra:

    34650

    Giải thích:

    Từ MISSISSIPPI: $\frac{11!}{1!4!4!2!}=\frac{39916800}{1152}=34650$.

    Đang tải editor...