NOIP 模擬 八十五
T1 衝刺NOIP2021模擬18 莓良心
容易發現答案和每一個 \(w_i\) 無關，我們只需要求出總和然後計算方案數。
對於每一個數貢獻的方案數是相同的，首先是自己的部分就是\(\begin{Bmatrix} n\\k\end{Bmatrix}\)。
然後考慮每個數和其他數在一組時都會額外有貢獻，考慮將兩個數捆綁那麼答案是 \((n-1)\times\begin{Bmatrix} n-1\\k\end{Bmatrix}\)
計算只需要以上兩個第二類斯特林數就可以完成。
\(\mathcal O(n^2)\) 的計算方式顯然不能滿足實現，我們需要容斥去求。
\(\begin{Bmatrix} n\\k\end{Bmatrix}=\frac{1}{k!}\times \sum \limits _{i=0}^{k}(-1)^i\times \begin{pmatrix} k\\i\end{pmatrix}\times (k-i)^n\)
後面的冪可以線性遞推，複雜度\(\mathcal O(n)\)。
T2 衝刺NOIP2021模擬18 盡梨了
考慮兩個商店滿足\(a_1\times (b_2+1)>a_2\times(b_1+1)\)，一定是第一個在前面。
首先根據以上要求排序，然後考慮 \(\mathcal O(n^2)\) 的 dp。設 \(dp_{i,j}\) 為考慮前 i 個，選了 j 個的最小時間。
轉移只選要看當前點是否要去選擇。
對於 a 不為 0，我們發現時間的增長是指數型的，於是第二維只有 log 級別。
然後考慮 加上 a 為0，此時我們二分，能塞多少塞多少。
然後得到答案。此題重在分析數據。
T3 衝刺NOIP2021模擬18 團不過
考慮求出先手必敗的方案數，用總方案減去即可。
設 \(p_i\) 為\(2^n-1\) 的 i 次下降冪，這樣總方案顯然為 \(p_n\)。
設 \(f_i\) 為 i 堆石子先手必敗的方案數。我們只需要根據前 i-1 的結果來調整即可。
\]
這樣遞推是減去了前 i-1 為 0 這一位不可取 0，後者是任意 i-2 為 0 然後 這一位會和前面有相同。
T4 衝刺NOIP2021模擬18 七負我
根據調整法答案最大是把時間均分給最大的完全圖。
我們只需要找出最大的完全圖即可。
meet in middle 。前面 dp ，後面 並出邊根據 dp 數組出答案。
