Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
LQDQPER - Truy vấn hoán vị |
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
Được gửi lên bởi: | Trung Hieu |
Ngày: | 2010-12-09 |
Thời gian chạy: | 1s |
Giới hạn mã nguồn: | 500000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: ASM64 ERL GOSU JS-RHINO PERL6 PYPY RUST SED |
Nguồn bài: | COI 2010 |