k993. 合併排序 - 高中生程式解題系統

內容

有一天66檸檬66不幸追撞了肯肯肯的豐田世紀，肯肯肯很生氣，給66檸檬66看了以下的 C++ 程式碼：

這個是合併排序的程式，輸入陣列大小 $n$ 與一個 $1 \sim n$ 的排列 $a_{1} \sim a_{n}$ ，程式會將 $a_{1} \sim a_{n}$ 排序好，並輸出呼叫 cmp 函式的次數 cnt。

肯肯肯給66檸檬66的和解條件是：輸入 $n, p$ ， $p$ 為質數，66檸檬66要輸出對於所有 $1 \leq k \leq n$ ，大小為 $k$ 的排列經過以上程式的 merge_sort 後，cnt 的期望值是多少。

答案要 $mod p$ 後再輸出，若答案為 $x$ ，並且化成最簡分數後為 $\frac{a}{b}$ ，那 $x mod p = a \times b^{- 1} mod p$ ，其中 $b^{- 1}$ 為 $b$ 的模逆元。

66檸檬66想了三回後還是沒想到，請你幫幫他！

輸入說明

輸入兩個正整數 $n, p$ 。

$1 \leq n \leq 10^{5}$
$10^{8} + 7 \leq p \leq 10^{9} + 7$
$p$ 為質數

輸出說明

輸出 $n$ 行，第 $i$ 行輸出當 $k = i$ 時，大小為 $k$ 的排列經過 merge_sort 後 cnt 的期望值是多少。

範例輸入 #1

1 100000007

範例輸出 #1

範例輸入 #2

6 1000000007

範例輸出 #2

測資資訊：

記憶體限制： 128 MB
公開測資點#0 (4%): 1.0s , <1K
公開測資點#1 (4%): 1.0s , <1K
公開測資點#2 (6%): 1.0s , <1K
公開測資點#3 (6%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1K
公開測資點#6 (30%): 1.0s , <1K
公開測資點#7 (30%): 1.0s , <1K

提示：

$20 % ： n \leq 7$

$20 % ： n \leq 2000$

$60 % ：無特別限制$

標籤:

出處:

第七屆簡單的小競賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」