Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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ụ

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.