题目

假设有10种物品，问平均需要抽多少次，才能把所有物品都抽到一遍？

分析

首先要知道 \(Min-Max\) 容斥:

\(min(S) = \sum_{\varnothing \ne T\subseteq S} (−1)^{|T|+1}max(T)\)

\(max(S) = \sum_{\varnothing \ne T\subseteq S} (−1)^{|T|+1}min(T)\)

\(kthmax(S)=\sum_{\varnothing \ne T\subseteq S}\begin{pmatrix}|T| −1\\k-1 \end{pmatrix} (−1)^{|T|−k}min(T)\)

\(E(kthmax(S))=\sum_{\varnothing \ne T\subseteq S}\begin{pmatrix} |T| −1\\k-1 \end{pmatrix}(−1)^{|T|−k}E(min(T))\)

其中，这道题需要求：\(E(10thmax(S))\), 其中 ： \(E(min(T))\) 为 \(\frac{10}{|T|}\)

代码：

#include <bits/stdc++.h>
using namespace std;
double ans;
int main(){
	for(int i=1;i<(1<<10);i++){
		int cnt=0;
		for(int j=0;j<10;j++){
			if(i>>j&1) cnt++;
		}
		int v;
		if((10-cnt)%2==0) v=-1;
		else v=1;
		double num=10./cnt;
		double res=1;
		for(int i=1;i<=cnt;i++){
			res*=(10-i);
		}
		for(int i=1;i<=cnt;i++){
			res/=i;
		}
		ans+=res*v*num;
	}
	printf("%.10lf",ans);
	return 0;
}