loopers期望題目感悟-期望的線性性
”我想永遠當你最珍貴的寶物..……“
米婭有 n 個尋寶的地區，在第 i 個地區尋寶可以帶來 \(a_i\) 的快樂值，每次米婭會隨機選擇一個還沒有的搜尋過的地區進行尋寶，搜尋第 個地區（ 還沒有搜尋過）的概率為，
搜尋后會得到 \(a_i\) 的快樂值
由于某種原因，米婭搜尋了一號地區后就會停止，米婭想知道她可以獲得的快樂值的期望由于miya只在一天不斷輪回，所以米婭只想知道這個數在 意義下的值，
所以我們可以比較容易(屁)發現對于每個i有i必須在1前選擇才能完成，
所以我們可以根據期望的線性性，eg: CF280C Game on Tree
所以我們考慮一整個序列，一個i有效當且僅當它在 \(a_1\) 之前的序列中出現，所以我們可以考慮僅僅這兩個的位置關系：
即有 \(\frac{a_i}{a_1+a_i}\) 的期望對于每個i，線性逆元累加就可以，
棘手問題：處理逆元：
我們求出前綴積 \(h_i\) 函式和后綴積 "\(t_i\)" 函式并且求出 $ \prod _{a_i+a1}^n$ 的逆元，然后乘上前后綴就可以愉快解決了，效仿 $ O(n)$ 求 \(1 \sim i\) 階乘的逆元，
代碼加載失敗
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/322945.html
標籤：C++