Codeforces 398C LRU (概率dp)

题目链接：C. LRU

题意:

给定$n$件物品和容量为$k$的背包,每件物品有一个概率$pi$,$\sum pi=1$,每次有$pi$的概率把第$i$件物品加入背包,若其已经存在背包则不加入，否则放入背包，当背包内物品大于$k$时，挤掉最左边的物品,问经过$10^{100}$次操作后各物品存在背包的概率

题解：

显然，经过$10^{100}$，能出现的($pi>0$)一定出现了，否则假设只出现部分，其对应概率和$\sum qj<1$，那么其取幂$10^{100}$后约为0，故所有$pi>0$的数都一定出现在某种最终排列中,实际上，我们只关心背包中最后加入的$k$个不同的数，因为之前的数都会被这$k$个数"挤掉"(本来就存在的实际上也相当于挤掉)，因为$n$很小这样我们只需要状态压缩枚举转移即可，对应当前状态$i$，枚举新加入的不在$i$集合中的点$j$，记录$res=\sum qj$，$那么dp[i|(1<<j)]+=dp[i]\ast \frac{qj}{res}$，当集合$i$中元素为k时统计下各个出现的数，记录到对应答案即可，注意：当$n$个数中如果$pi!=0$数小于$k$，显然最后是最多排满所有$pi!=0$的点,，所有这里的$k$要和$pi!=0$的数量取个$min$
具体细节和不懂可以看代码和注释：

//  CF 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
	#ifndef local
	#define endl '\n'
#endif */
#define mkp make_pair
using namespace std;
using std::bitset;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll MAXN=2e6+10;
const ll INF=1e18;
const ll N=2e5+100;
const ll mod=1e9+7;
const ll hash_p1=1610612741;
const ll hash_p2=805306457;
const ll hash_p3=402653189;
//-----------------------------------------------------------------------------------------------------------------*/
// ll head[MAXN],net[MAXN],to[MAXN],edge[MAXN]/*流量*/,cost[MAXN]//费用;
/* 
void add(ll u,ll v,ll w,ll s){
	to[++cnt]=v;net[cnt]=head[u];edge[cnt]=w;cost[cnt]=s;head[u]=cnt;
	to[++cnt]=u;net[cnt]=head[v];edge[cnt]=0;cost[cnt]=-s;head[v]=cnt;
}
struct elemt{
	int p,v;
};
-----------------------------------
求[1,MAXN]组合式和逆元 
ll mi(ll a,ll b){
	ll res=1;
	while(b){
		if(b%2){
			res=res*a%mod;
		}	
		a=a*a%mod;
		b/=2;
	}
	return res;
}
ll fac[MAXN+10],inv[MAXN+10];
void init(){
	fac[0]=1;inv[0]=1;
	for(ll i=1;i<=MAXN;i++){
		fac[i]=(fac[i-1]*i)%mod;
		inv[i]=mi(fac[i],mod-2);
	}
}
ll C(int m,int n){//组合式C(m,n); 
	if(!n){
		return 1;
	}
	if(mmp;
struct comp{
	public:
		bool operator()(elemt v1,elemt v2){
			return v1.v --小顶堆  less --大顶堆  
priority_queue,comp>q;

	set::iterator it=st.begin();
*/
//emplace_back()  等于push_back(),但效率更高,传输pair时emplace_back(i,j)==push_back({i,j}) 
// vector>edge; 二维虚拟储存坐标 
//-----------------------------------------------------------------------------------------------------------------*/
//mt19937 rnd(time(0));//高质量随机化函数，直接调用rnd()即可
//mapmp[N]; 
//emplace_back() 
/*
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
*/
double dp[4000010];//到达状态i的概率
double p[100];
double ans[100];
int main(){
/*cout<
/*cout<
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//同步流
	int k,n;
	cin>>n>>k;
	int num=0;
	for(int i=0;i<n;i++){
		cin>>p[i];
		if(p[i]!=0){
			num++;
		}
	}
	k=min(k,num);
	dp[0]=1.0;
	for(int i=0;i<(1<<n);i++){//枚举当前状态
		int cnt=0;//当前状态中1的个数
		double res=0.0;//出现非当前状态中数的概率
		for(int j=0;j<n;j++){
			if(i&(1<<j)){
				cnt++;
			}
			else{
				res+=p[j];
			}
		}
		if(cnt==k){//到达最终状态，记录答案
			for(int j=0;j<n;j++){
				if(i&(1<<j)){//当前状态存在j
					ans[j]+=dp[i];
				}
			}
		}
		else if(cnt<k&&res!=0){//去更新后面的状态（res==0时当前没有可放的数）
			for(int j=0;j<n;j++){
				if(!(i&(1<<j))){//当前j可以放入(原来没有j)
					dp[i|(1<<j)]+=dp[i]*p[j]/res;//选择第j个的概率为p[j]/res,(不能选当前已经有的i，所有要/res)
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		cout<<setiosflags(ios::fixed)<<setprecision(10)<<ans[i]<<" ";
	}
	cout<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152