內容
有一天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 的期望值是多少。
答案要 $\text{mod }p$ 後再輸出，若答案為 $x$，並且化成最簡分數後為 $\frac{a}{b}$，那 $x\text{ mod }p=a\times b^{-1}\text{ 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
0
範例輸入
#2
6 1000000007
範例輸出
#2
0 1 666666674 666666676 166666675 833333349
測資資訊：
記憶體限制：
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
公開 測資點#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\%：無特別限制$
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||