組合計數瞎做

計數/ll

不能再計數了，再計數下去就要變得奇怪了♥

無多項式含量。

01 CF1392H ZS Shuffles Cards

首先有一個比較有趣的轉化：期望抽牌輪數等于每次抽到 joker 時抽牌數量乘期望抽到 joker 次數。

可以發現前面的東西是常數，由于每張牌排在所有 joker 前面的機率是獨立的，為 \(\frac{1}{m+1}\)，是以一個期望抽牌序列長度為 \(\frac{n}{m+1}+1\)。（後面還有一張 joker）

考慮設 \(f_x\) 表示還有 \(x\) 張牌沒有抽到時期望抽 joker 次數，那麼我們讨論下一張牌是否是 joker：（注意洗牌不會清空你抽到過的牌集合）

\[f_x=\frac{m}{m+x}(f_x+1)+\frac{x}{m+x}f_{i-1}

\]

由于 \(f_1=m+1\)，是以我們可以通過數學歸納法得到 \(f_n=1+\sum_{i=1}^n\frac{m}{i}\)。

然後就沒了，時間複雜度：\(O(n)\)。

AC 記錄

02 P2767 樹的數量

顯然可以設計出來一個 \(O(n^3)\) 的 dp：

\(f_{i,j}\) 表示 \(i\) 個節點，根節點 \(j\) 叉的方案數，轉移可以字首和一手轉移一下，比較 naive。

好像有非常高明的做法，暫時鴿了：Fuss-Catalan 數、(m-1)-Dyck 路與 m 叉樹，廣義二項級數 & 廣義指數級數 學習筆記

大概就是經典結論，若生成函數 \(F_k(z)=zF_k^k(z)+1\)，那麼 ：

\[[z^n]F^m_k(z)=\frac{m{kn+m\choose n}}{kn+m}

\]

帶入這道題就是

\[\frac{nm+1\choose n}{nm+1}=\frac{nm\choose n-1}{n}

\]

lucas 定理即可，時間複雜度 \(O(mod)\)，好像可以卷積？

AC 記錄

03 P3330 [ZJOI2011]看電影

正睿金華講過的題，好像有點不太記得了。

首先特判 \(n>k\)。

dp 設計應該比較簡單 \(f_{i,j,k}\) 表示到達第 \(i\) 位置，有 \(j\) 個人在等待，有 \(k\) 個人落座的機率，然後就枚舉目前開始的人數量轉移就好了，複雜度是 \(O(Tn^3k)\)，過不去。

我們發現實際上枚舉多的人數可以類似字首和優化，就可以做到 \(O(Tn^2k)\) 了，勉強能過。

但是實際上有高明的組合意義做法：

我們令序列後面添加一個新的座位，再将它變為一個環，那麼我們每個人就都一定能落座，題意轉化為沒有人坐在最後一個座位的方案數。

我們發現成環之後每個點都是相同的，于是我們就可以欽定一個位置不選，那麼機率為：

\[\frac{\frac{(k+1)^n}{k+1}\times(k-n+1)}{k^n}

\]

左邊是圓排列，右邊就是欽定那個不選的位置在哪裡。

04 CF1528F AmShZ Farm