CSES - Permutation Inversions | Hoán vị nghịch thế

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
nhphucqt
Dạng bài
Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Nhiệm vụ của bạn là đếm số lượng hoán vị của \(1, 2, \dots, n\) có đúng \(k\) cặp nghịch thế (tức là cặp hai phần tử ở sai thứ tự).

Ví dụ, với \(n = 4\) và \(k = 3\), có \(6\) hoán vị:

  • \([1,4,3,2]\)
  • \([2,3,4,1]\)
  • \([2,4,1,3]\)
  • \([3,1,4,2]\)
  • \([3,2,1,4]\)
  • \([4,1,2,3]\)

Input

  • Dòng đầu vào duy nhất có hai số nguyên \(n\) và \(k\).

Output

  • In đáp án chia lấy dư cho \(10^9 + 7\).

Constraints

  • \(1 \le n \le 500\)
  • \(0 \le k \le \frac{n\left(n-1\right)}{2}\)

Example

Sample input

4 3

Sample output

6

Bình luận


  • 0
    nguyen_ducminh    11:45 p.m. 1 Tháng 9, 2023 ← đã chỉnh sửa

    CSES - Permutation Inversions | Hoán vị nghịch thế

    Nhiệm vụ của bạn là đếm số hoán vị của dãy \(1,2,...,n\) mà có chính xác \(k\) nghịch thế. Số nghịch thế của một hoán vị được định nghĩa là số cặp phần tử trong hoán vị bị sai về thứ tự tương đối.

    Ví dụ, với \(n = 4\) và \(k = 3\), có \(6\) hoán vị thỏa mãn:

    • \([1,4,3,2]\)
    • \([2,3,4,1]\)
    • \([2,4,1,3]\)
    • \([3,1,4,2]\)
    • \([3,2,1,4]\)
    • \([4,1,2,3]\)

    Input

    • Gồm hai số nguyên \(n\) (\(1 \leq n \leq 500\)) và \(k\) (\(0 \leq k \leq \frac{n(n-1)}{2}\)).

    Output

    • In ra đáp án theo modulo \(10^9 + 7\)

    Test 1

    Input 
    4 3
    Output 
    6