分析
设 $f_{i, j}$ 表示还剩 $i$ 个人时第 $j$ 个人的获胜概率。
考虑转移。首先枚举庄家抽到的卡牌 $k$，从而得到这一轮被淘汰的人的位置 $c$。
如果 $c \neq j$，则无法转移。否则第 $c$ 个人被淘汰之后，剩下的 $i-1$ 个人要组成一个新的环，庄家为第 $c$ 个人的下一个。容易算出，当 $c > j$ 时，第 $j$ 个人是新的环里从新庄家数起的第 $i - c + j$ 个人；当 $c < j$时，第 $j$ 个人是新的环里从新庄家数起的第 $j-c$ 个人。于是可以得到转移
$$
f_{i, j} \gets^+ \begin{cases}\frac{f_{i - 1, j - c}}{m}, & c < j \\ 0, & c = j \\ \frac{f_{i - 1, i - c + j}}{m}, & c > j\end{cases}
$$
代码
#include <bits/stdc++.h>
#define re register
using namespace std;
double f[60][60];
int num[60];
int main() {
int n,m; scanf("%d%d",&n,&m);
for (re int i=1;i<=m;i++) scanf("%d",&num[i]);
f[1][1]=1.0;
for (re int i=2;i<=n;i++)
for (re int j=1;j<=n;j++)
for (re int k=1;k<=m;k++) {
int c=(num[k]%i) ? num[k]%i : i;
if (c<j) f[i][j]+=f[i-1][j-c]/m;
else if (c>j) f[i][j]+=f[i-1][i-c+j]/m;
}
for (re int i=1;i<=n;i++) printf("%.2lf%% ",f[n][i]*100.0);
return 0;
}
3 条评论
转移写错啦
已修改。
窝以前是怎么写错的。。
我都不会算概率