partychicken
Articles12
Tags3
Categories3
CCPC2020 Weihai E

CCPC2020 Weihai E

问题描述

在游戏“炉石传说”中,存在一张卡牌”考古专家雷诺”,其在特定条件下会对敌方所有随从随机地进行总量为10点的伤害。而其随机方式是对于每一点伤害依次进行判定,等概率地从所有敌方的存活随从中选择一个进行伤害。我们关注于对于某特定随从序列其杀死随从数量的期望,并将其伤害从常数 $10$ 推广到某一给定数值 $m$,得到如下问题:

  • 对某一正项序列 $a_1,a_2,\cdots,a_n$ ,依次进行 $m$ 次操作,每次在所有非零项 $a_{p_1},a_{p_2}, \cdots,a_{p_m}$ 中等概率地选取一个数 $a_{p_i}$ 并令 $a_{p_i}=a_{p_i}-1$ 。记 $m$ 次后的非零项个数为 $x$ ,求 $x$ 的期望 $E(x)$.

问题解法

定义 $S_l= \{s_1,s_2,\cdots,s_l \}$ 表示一个长度为 $l$ 的操作序列,其中,$s_i \in[1,n]$ 表示第 $i$ 次操作选取了 $a_{s_i}$ .

令 $ \sigma_i^{S_l}$ 表示经 $S_l$ 的前 $i$ 次操作后,序列 $ \{a_i\}$ 剩余的非零项的个数。特别地,令 $ \sigma^{S_l}= \sigma_l^{S_l}$ 表示经过全部 $S_l$ 的操作后,其非零项的个数。

那么,每个合法操作序列出现的概率

定义 $\Gamma$ 为所有长度为 $m$ 的合法操作序列的集合,则

接下来,我们将问题的求解分为两个步骤。

Part I

定义集合 $\Gamma_{l,Set}$ $0 \le l \le m,Set \subseteq [n]$ 是序列 $S= \{s_1,s_2, \cdots,s_n \}$ 的集合,要求序列满足:

  1. $ \forall 1 \le i \le n,s_i=0 || s_i \in Set$
  2. $ \forall j \in S,cnt_j(Set)=a_j$

其中,$s_i=0$ 代表第 $i$ 次操作的对象 $\notin Set$ , $cnt_i(S)$ 表示序列 $S$ 中 $i$ 的出现次数

设 $f_{l,Set} (0 \le l \le m,Set \subseteq [n])$ 为

则有,

其中,

递推式中的第一项表示 $s_l=0$ 的概率,后面则是枚举 $s_l=i$ 且 $cnt_i(S)=a_i$ 的概率,将这两类情况求和,即为满足条件的总概率.

可以通过预处理所有的 $sum(A)$ 以及 $|A|$ 使这个递推式可以在 $O(nm2^n)$ 的时间内完成.

Part II

可以发现,$ \forall S \in \Gamma_{m,Set},cnt_0(S)$ 恒定,所以只需考虑 $s_i=0$ 的位置,给每个位置赋上不属于 $Set$ 的值,并且满足$ \forall i \notin Set,cnt_i(S)<a_i$ 即可得到一个合法的序列.记这样的方案总数为 $g_{Set}$,则有:

令 $h_{l,Set}$,表示序列 $S’= \{s_1,s_2,\cdots,s_l\}$ 满足:

  1. $\forall 1 \le i \le l,s_i \in Set $
  2. $\forall i \in Set,cnt_i(S’)<a_i $

的个数,则 $h_{m-|Set|,Set}=g_{Set^{C}}$,所以只要求得 $h_{i,Set}$ 序列即可.

易得递推式

其中,$low(Set)$,表示 $Set$ 中的最小元素.

上述递推可以在 $O(m^2 2^n)$ 的时间内完成.

综上,问题得解.总时间复杂度为 $O(m(n+m)2^n)$.

Code

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
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=5e4+100;
double fac[MAXN],fav[MAXN],dp[110][MAXN],fir[MAXN][110];
int n,m,dat[MAXN],sum[MAXN],num[MAXN],lower[MAXN];
double qpow(double base,int tim)
{
double ans=1;
while(tim)
{
if(tim&1) ans*=base;
base*=base;tim>>=1;
}
return ans;
}
void init()
{
fac[0]=fac[1]=1;
fav[0]=fav[1]=1;
for(int i=2;i<=MAXN-100;i++)
{
fac[i]=fac[i-1]*i;
fav[i]=fav[i-1]/i;
}
}
double C(int a,int b)
{
return fac[b]*fav[a]*fav[b-a];
}
double get_dp(int x,int res)
{
if(fir[x][res]>(1e-8)) return fir[x][res];
int now=lower[x];
if(res==0) fir[x][res]=1;
else for(int i=0;i<=dat[now]-1;i++)
fir[x][res]+=get_dp(x^(1<<now-1),res-i)*C(i,res);
//cout<<"!!!!"<<now<<" "<<x<<" "<<res<<" "<<fir[x][res]<<endl;
return fir[x][res];
}
int main()
{
cin>>n>>m;init();
for(int i=1;i<=n;i++)
scanf("%d",&dat[i]);
for(int i=0;i<(1<<n);i++)
for(int j=1;j<=n;j++)
if(i&(1<<(j-1)))
{
if(lower[i]==0) lower[i]=j;
else lower[i]=min(lower[i],j);
num[i]++;
sum[i]+=dat[j];
}
if(sum[(1<<n)-1]==m)
{
printf("%d",n);
return 0;
}
dp[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<(1<<n);j++)
{
if(sum[j]>i) continue;
//cout<<num[(1<<n)-1]<<" "<<(n-num[j])<<endl;
if(i>sum[(1<<n)-1]-(n-num[j])) continue;
dp[i][j]=dp[i-1][j]/(n-num[j]);
for(int k=1;k<=n;k++)
if(j&(1<<(k-1)))
{
double p=1.0/(n-num[j^(1<<(k-1))]);int res=i-sum[j^(1<<(k-1))];
dp[i][j]+=dp[i-1][j^(1<<(k-1))]*C(dat[k]-1,res-1)*p;
}
//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}
// for(int i=0;i<=(1<<n)-1;i++)
// printf("%.3lf ",dp[m][i]);
// cout<<endl;
fir[0][0]=1;
for(int i=0;i<1<<n;i++)
{
int now=lower[i];
for(int j=0;j<=m;j++)
for(int k=0;k<=min(dat[now]-1,j);k++)
fir[i][j]+=fir[i^(1<<(now-1))][j-k]*C(k,j);
}
double ans=0;int base=(1<<n)-1;
for(int i=0;i<(1<<n);i++)
if(m>=sum[i]&&fir[base^i][m-sum[i]]!=0) ans+=num[i]*dp[m][i]*fir[base^i][m-sum[i]];
printf("%.10lf \n",ans);
}
Author:partychicken
Link:http://partychicken.github.io/2022/04/20/E/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
×