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ố Euler đếm descent của hoán vị

    Một descent của hoán vị (σ1,…,σn)(\sigma_1,\dots,\sigma_n)(σ1​,…,σn​) là chỉ số iii thỏa σi>σi+1\sigma_i>\sigma_{i+1}σi​>σi+1​. Số Euler A(n,k)A(n,k)A(n,k) đếm số hoán vị của nnn phần tử có đúng kkk descent, thỏa truy hồi

    A(n,k)=(k+1)A(n−1,k)+(n−k)A(n−1,k−1),A(0,0)=1.A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1),\quad A(0,0)=1.A(n,k)=(k+1)A(n−1,k)+(n−k)A(n−1,k−1),A(0,0)=1.

    Cho n,kn,kn,k, in A(n,k) mod (109+7)A(n,k) \bmod (10^9+7)A(n,k)mod(109+7).

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

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

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

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

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

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

    Ví dụ:

    Đầu vào:

    3 1

    Đầu ra:

    4

    Giải thích:

    Các hoán vị của $\{1,2,3\}$ có đúng 1 descent: $132,213,231,312$ — gồm 4 hoán vị.

    Đang tải editor...