trang chủ / đề bài / ld_tst_26_b

Hoán vị

Đề bài

Mô tả

Giáo sư Math dạy toán ở trường đại học Uni có n sinh viên theo học. Trong chuyên đề số học gần đây, giáo sư Math đã nói về hạng của các hoán vị.

Một dãy gồm k số nguyên có giá trị nằm trong đoạn từ 1 đến k sao cho mỗi số xuất hiện đúng 1 lần được gọi là một hoán vị. Dễ dàng nhận thấy có tất cả k! hoán vị khác nhau. Các hoán vị này được sắp xếp theo thứ tự từ điển.

Ví dụ: với k=3, ta có 3!=6 hoán vị theo thứ tự từ điển như sau: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

Vị trí của hoán vị trong thứ tự từ điển được gọi là hạng của hoán vị. Trong ví dụ trên, hoán vị (3,1,2) có hạng là 5.

Giáo sư Math gán cho mỗi sinh viên của ông ta một hoán vị. Tất cả các sinh viên sẽ tính toán để tìm hạng của hoán vị mà giáo sư gán cho mình. Giáo sư Math sử dụng một thuật toán đơn giản để sinh các hoán vị và chọn một hoán vị cơ sở gồm k số nguyên. Sau đó, ông gửi cho mỗi sinh viên 2 số nguyên a,b lần lượt là hai vị trí cần đổi chỗ trong hoán vị cơ sở. Sau khi thực hiện hoán đổi hai vị trí trong hoán vị cơ sở, sinh viên sẽ có được hoán vị của mình.

Math đưa ra một hoán vị cơ sở và n cặp vị trí cần đổi chỗ cho n sinh viên.

Yêu cầu: Hãy viết chương trình giúp các sinh viên tính hạng hoán vị của mình. Vì kết quả có thể rất lớn nên chỉ cần giữ lại phần dư khi chia cho 109+7.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên k và n (2≤k≤3·105; 1≤n≤105);
  • Dòng thứ hai chứa k số nguyên là hoán vị cơ sở;
  • n dòng tiếp theo, mỗi dòng chứa hai số nguyên a,b (1≤a<b≤k) thể hiện hai vị trí cần đổi chỗ hoán vị cơ sở.

Dữ liệu ra

Gồm n số nguyên, mỗi số trên một dòng là hạng các hoán vị của các sinh viên (theo modulo 109+7) theo thứ tự các cặp đổi chỗ trong dữ liệu vào.

Ràng buộc

  • 2≤k≤3·105, 1≤n≤105
  • 1≤a<b≤k

Subtasks

  • Subtask 1 (20% số điểm): k≤8.
  • Subtask 2 (20% số điểm): k,n≤3000.
  • Subtask 3 (20% số điểm): n≤3000.
  • Subtask 4 (20% số điểm): b=a+1.
  • Subtask 5 (20% số điểm): Không có giới hạn gì thêm.

Ví dụ

Input Output Giải thích
5 3
1 5 4 2 3
1 3
2 3
2 5
91
17
9
Hoán vị cơ sở (1,5,4,2,3) có hạng 23. Cặp (1,3) cho (4,5,1,2,3) có hạng 91; cặp (2,3) cho (1,4,5,2,3) có hạng 17; cặp (2,5) cho (1,3,4,2,5) có hạng 9.
4 4
3 1 4 2
1 4
2 3
1 2
3 4
8
17
4
13
Ví dụ thêm (không có trong đề gốc). Cặp (1,4) cho hoán vị (2,1,4,3) có hạng 8.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0