LQDQPER - Truy vấn hoán vị
Giới hạn- Thời gian: 0.692s
- Bộ nhớ: 1536MB
- Mã nguồn: 500000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một hoán vị của dãy n phần tử a1, a2, ..., an gọi là hoán vị gốc và một số các truy vấn hoán vị. Một truy vấn hoán vị là một cặp (i, j) (1 ≤ i ≤ j ≤ n). Với mỗi truy vấn hoán vị (i, j), bạn đổi chỗ 2 phần tử tại vị trí I và vị trí j và in ra số hiệu hoán vị của dãy hoán vị mới đó . Các truy vấn không ảnh hưởng đến hoán vị gốc . Ví dụ , nếu hoán vị gốc là (1,5,4,2,3) và các cặp là (1,3),(2,3) và (2,5) thì ta sẽ thu được 3 hoán vị là : (4,5,1,2,3) , (1,4,5,2,3) và (1,3,4,2,5) . Chúng có các số hiệu là 91,17 và 9 . Yêu cầu In ra số hiệu của các hoán vị . Các số này có thể rất lớn nên đưa ra sau khi đã mod 1000 000 007 Dữ liệu Dòng 1: n (1 ≤ n ≤ 300000) và q (1 ≤ q ≤ 100000) số lượng truy vấn hoán vị Dòng 2: n số a1, a2 , ..., an . Trong q dòng sau, mỗi dòng chứa 2 số i, j biểu thị một truy vấn hoán vị (1 ≤ i ≤ j ≤ n). Kết quả In ra q số nguyên , mỗi số 1 dòng là số hiệu của mỗi hoán vị mod 1000 000 007 theo thứ tự xuất hiện trong input . Ví dụ
Cho một hoán vị của dãy n phần tử a1, a2, ..., an gọi là hoán vị gốc và một số các truy vấn hoán vị.
Một truy vấn hoán vị là một cặp (i, j) (1 ≤ i ≤ j ≤ n).
Với mỗi truy vấn hoán vị (i, j), bạn đổi chỗ 2 phần tử tại vị trí I và vị trí j và in ra số hiệu hoán vị của dãy hoán vị mới đó .
Các truy vấn không ảnh hưởng đến hoán vị gốc .
Ví dụ , nếu hoán vị gốc là (1,5,4,2,3) và các cặp là (1,3),(2,3) và (2,5) thì ta sẽ thu được 3 hoán vị là : (4,5,1,2,3) , (1,4,5,2,3) và (1,3,4,2,5) . Chúng có các số hiệu là 91,17 và 9 .
Yêu cầu
In ra số hiệu của các hoán vị . Các số này có thể rất lớn nên đưa ra sau khi đã mod 1000 000 007
Dữ liệu
- Dòng 1: n (1 ≤ n ≤ 300000) và q (1 ≤ q ≤ 100000) số lượng truy vấn hoán vị
- Dòng 2: n số a1, a2 , ..., an .
- Trong q dòng sau, mỗi dòng chứa 2 số i, j biểu thị một truy vấn hoán vị (1 ≤ i ≤ j ≤ n).
Kết quả
In ra q số nguyên , mỗi số 1 dòng là số hiệu của mỗi hoán vị mod 1000 000 007 theo thứ tự xuất hiện trong input .
Ví dụ
Dữ liệu
5 3
1 5 4 2 3
1 3
2 3
2 5
Kết quả
91
17
9
- Người up: kauke
- Nguồn bài: COI 2010