Tổng nghịch thế

Xem PDF




Thời gian:
Java 3.0s
Python 3.0s

Tác giả:
Dạng bài
Điểm: 500 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Gọi \(\pi=\left(p_1, p_2,..., p_n\right)\) là một hoán vị của \((1, 2,...,n)\), một cặp chỉ số \((i, j)\) được gọi là nghịch thế nếu \(i < j\) nhưng \(p_i > p_j\).

Cho một hoán vị \(\pi_0\) và số nguyên dương \(k\), xét \(k\) hoán vị liên tiếp \(\pi_0\), \(\pi_1\),..., \(\pi_{k-1}\) kể từ hoán vị \(\pi_0\), hãy tính tổng \(f(\pi_0)+f(\pi_1)+...+f(\pi_{k-1})\) với \(f(\pi)\) là số lượng cặp nghịch thế trong hoán vị \(\pi\).

Input

  • Dòng đầu chứa hai số nguyên dương \(n\), \(k\) lần lượt là kích thước của hoán vị \(\pi_0\) và số lượng hoán vị liên tiếp cần xét.

  • Dòng tiếp theo chứa \(n\) số nguyên dương \(p_1\), \(p_2\),..., \(p_n\) mô tả hoán vị \(\pi_0\).

  • Dữ liệu đảm bảo luôn tồn tại ít nhất \(k\) hoán vị hợp lệ kể từ hoán vị \(\pi_0\) trở đi.

Output

  • Một số nguyên duy nhất là kết quả của bài toán.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(n\leq 10^3, k\leq 10\).
  • Subtask \(2\) (\(40\%\) số điểm): \(n\leq 10^5, k\leq 10\).
  • Subtask \(3\) (\(20\%\) số điểm): \(n\leq 10^5, k\leq 10^5\).

Example

Test 1

Input
5 4
1 2 3 4 5
Output
4
Note
  • Hoán vị \(\pi_0=(1,2,3,4,5)\) không có cặp nghịch thế nào.
  • Hoán vị \(\pi_1=(1,2,3,5,4)\) có một cặp nghịch thế là \((4, 5)\).
  • Hoán vị \(\pi_2=(1,2,4,3,5)\) có một cặp nghịch thế là \((3, 4)\).
  • Hoán vị \(\pi_3=(1,2,4,5,3)\) có hai cặp nghịch thế là \((3, 5)\)\((4, 5)\).

Vậy tổng số nghịch thế là \(0+1+1+2=4\).


Bình luận


  • -5
    tuanlinh 8:44 a.m. 7 Tháng 7, 2020

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

    1 phản hồi

    • -5
      tuanlinh 8:41 p.m. 6 Tháng 7, 2020

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

      3 phản hồi