b087:
排序 (transform)
Content
有一個由 𝑁 個數字組成的數列, 這數列是 1 至 𝑁 的某種排列。 這個數列經過 𝐾 輪操作後, 變成了一個由 1 至 𝑁 的順序排列。 而每輪操作都是相同的, 在每一輪操作都有 𝑃 個指令, 每個指令是將指定的位置上的數字對換。 我們想知道在未進行任何操作前, 最初的數列是什麼?
由於數列可能很長， 所以我們不需要輸出整個數列， 只需要輸出三個代表性的整數就可以， 它們分別為 𝐴, 𝐵, 𝑆。
- 𝐴 是最初數列中的第一個數
- 𝐵 是最初數列中的最後一個數
- 𝑆 是最初數列中的測和， 其計算方法如下：設最初數列為 𝑑1, 𝑑2, 𝑑3, ... , 𝑑𝑁, 則其測和為
𝑆 = ( 𝑑1 × 𝑁0 + 𝑑2 × 𝑁1 + 𝑑3 × 𝑁2 + ... + 𝑑𝑁 × 𝑁𝑁 − 1 ) mod 1000000007
其中， mod 1000000007 為取餘運算 （即除以1000000007 後取其餘數）。
Input
輸入第一行有三個正整數, 分別為 𝑁 𝐾 𝑃 (其代表意義見上文內容)
隨後有 𝑃 行, 每行有兩個正整數 𝑎 及 𝑏, 代表要將位置在 𝑎 及 𝑏 上的兩個數字對調 (1 ≤ 𝑎, 𝑏 ≤ 𝑁)
Output
輸出一行, 其上有 3 個數字 𝐴 𝐵 𝑆, 每個數字之間以一個空格分開。 這個數字為最初數列的代表性數字， 其定義見上面題目的描述。
Sample Input
#1
4 3 3 1 4 2 4 1 3
Sample Output
#1
3 2 199
測資資訊：
記憶體限制：
32
MB
不公開 測資點#0 (10%): 0.1s , <1M
不公開 測資點#1 (10%): 0.1s , <1M
不公開 測資點#2 (10%): 0.1s , <1M
不公開 測資點#3 (10%): 0.2s , <1M
不公開 測資點#4 (10%): 0.2s , <1M
不公開 測資點#5 (10%): 0.2s , <1M
不公開 測資點#6 (10%): 0.2s , <1M
不公開 測資點#7 (10%): 0.3s , <10M
不公開 測資點#8 (10%): 0.3s , <10M
不公開 測資點#9 (10%): 0.3s , <10M
不公開 測資點#0 (10%): 0.1s , <1M
不公開 測資點#1 (10%): 0.1s , <1M
不公開 測資點#2 (10%): 0.1s , <1M
不公開 測資點#3 (10%): 0.2s , <1M
不公開 測資點#4 (10%): 0.2s , <1M
不公開 測資點#5 (10%): 0.2s , <1M
不公開 測資點#6 (10%): 0.2s , <1M
不公開 測資點#7 (10%): 0.3s , <10M
不公開 測資點#8 (10%): 0.3s , <10M
不公開 測資點#9 (10%): 0.3s , <10M
Hint ：
10 ≤ 𝑁 ≤ 100000, 𝑁 ≤ 𝐾 ≤ 2𝑁,𝑁/2≤ 𝑃 ≤ 2𝑁
對於30%的數據， 𝑁 ≤ 1000
對於70%的數據，𝑁 ≤ 10000
最初排列: 3 1 4 2 (這是最初的數列，因為它經過下面題目要求的操作後，會變為 1 至 4 的順序排列）
第一輪操作後: 4 3 2 1
第二輪操作後: 2 4 1 3
第三輪操作後: 1 2 3 4 (得到 1 至 4 的順序排列)
因此，輸出為數列的第一個數 （即 3）, 最後一個數 （即 2），及它們的測和： (3 ×40 + 1 ×41 + 4 ×42 + 2 ×43 ) mod 1000000007 = 199
Tags:
出處:
MOIJ 2023
[管理者：
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||