CF755G PolandBall and Many Other Balls 題解

codeforces

luogu

有 \(n\) 個球，構造若幹組滿足：

每組至多兩個球至少一個球

不存在一個球出現在多個組

如果一組有兩個球，這兩個球相鄰

問為 \(k\in[0,m]\) 的方案數。

首先，有個顯然的 dp 為 \(dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}+dp_{i-2,j-1}\)。

可以考慮成有一個網格每次可以走 \(\vec v=(1,0),(2,1),(1,1)\)，求方案數。

考慮枚舉 \((2,1)\) 個數為 \(k\)，則有答案為

\[\begin{aligned}

&=\sum_{k=0}^m\dbinom{n-2k}{m-k}\dbinom{n-k}{k}\\

&=\sum_{k=0}^m\dbinom{n-k}{m}\dbinom{m}{k}

\end{aligned}

\]

接下來參考了這篇題解

組合意義是先從前 \(m\) 個選出了若幹個，然後從剩下的裡再選出 \(m\) 個的方案數。

可以考慮容斥，欽定 \(k\) 個必須重複選，剩下随意。

方案數是 \(\dbinom{m}{k}2^{m-k}\dbinom{n-k}{m-k}\)，分别為：前 \(m\) 個裡欽定 \(k\) 個重複，前 \(m\) 個裡除了 \(k\) 個之外随意，剩下裡選出不重複的。

\[\therefore\begin{aligned}

&=\sum_{k=0}^m(-1)^k\dbinom{m}{k}\dbinom{n-k}{m-k}2^{m-k}\\

&=m!n^{\underline{m}}\sum_{k=0}^m\frac{(-1)^k}{k!n^{\underline k}}\frac{2^{m-k}}{(m-k)!^2}

點選檢視代碼