CF698C. LRU

题意：n种物品，大小为k的队列，\(p_i\)的概率选择第i种物品放入队尾，如果已经有i了就不放了。队列大小>k时弹出队首。求\(10^{100}\)次操作后每种物品在队列里的概率

为什么没有官方题解啊，所以看了讨论区的题解

一开始想的是，一个元素在队列里，说明后来加入的元素种类<k，对于每种物品i，求出每个\(|S| =0…k-1 : i \notin S\)的集合出现在i右面的概率就行了。但这时候要求的是\(S\)中每种物品至少出现1次，至多无限次，只是简单的乘上\(\prod\limits_{i \in S}p_i\) 再乘上 \(\frac{1}{1-x}\)是不对的。

所以考虑容斥原理，求出\(S\)的任意子集出现的概率。

求这个概率很简单，每种元素可以不出现，设\(x=\sum\limits_{i \in S}p_i\)，那么

\(P=x+x^2+...+x^{\infty}=\frac{1}{1-x}\)

根据容斥原理，\(i\)的答案就是

和之前的恰好k个问题一样，这个容斥系数需要乘上超集的个数，比如大小为\(i\)的集合，他的大小为\(j\)的超集的个数是\(\binom{n-1-i}{j-i}\)，注意是\(n-1\)因为当前计算答案的元素不能选

需要注意的是，我们要同时求恰好\(0...k-1\)个，所以每个的容斥系数都要+1，并且要处理之前所有大小的超集

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=21, M=(1<<20)+5;

inline int read(){

    char c=getchar();int x=0,f=1;

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    return x*f;

}

int n, k, c[N][N];

double p[N], sum[M], coe[N], g[M];

inline int one(int x) { int c=0; while(x) x&=x-1, c++; return c; }

int main() {

	freopen("in","r",stdin);

	n=read(); k=read();

	for(int i=0; i<n; i++) scanf("%lf",&p[i]), sum[1<<i] = p[i];

	c[0][0]=1;

	for(int i=1; i<=n; i++) {

		c[i][0]=1;

		for(int j=1; j<=i; j++) c[i][j] = c[i-1][j] + c[i-1][j-1];

	}

	int all=1<<n;

	for(int i=0; i<all; i++) if(!sum[i]) sum[i] = sum[i&-i] + sum[i^(i&-i)];

	for(int i=k-1; i>=0; i--) {

		coe[i] = 1;

		for(int j=i+1; j<=k-1; j++) coe[i] -= coe[j] * c[n-1-i][j-i];

		//printf("coe %d %lf\n",i,coe[i]);

	}

	for(int i=0; i<n; i++) {

		if(p[i]==0 || p[i]==1 || k==1) {printf("%.9lf ", p[i]); continue;}

		double ans=0;

		for(int s=0; s<all; s++)

			if(!((1<<i) & s) && one(s)<=k-1) ans += coe[one(s)]/(1-sum[s]);// printf("s %d %lf\n",s, ans);

		printf("%.9lf ", p[i]*ans);

	}

}