算法
概率DP。
设$f[i][j]$表示还剩i个人时第j个人的获胜概率。
边界显然是$f[1][1]=1.0$。
那么状态如何转移呢？
我们可以首先枚举庄家抽到的卡牌$k$，得到这一轮被淘汰的人的位置$c$。当然，如果$c=j$，就不要考虑了（因为这表示此轮第$j$个人被淘汰）。
而第$c$个人被淘汰之后，剩下的$i-1$个人要组成一个新的环，庄家为第$c$个人的下一个。容易算出，当$c>j$时，第$j $个人是新的环里从新庄家数起的第$i-c+j$个人，当$c<j$时，第$j$个人是新的环里从新庄家数起的第$j-c$个人。
所以$f[i][j]+=\begin{cases}f[i-1][j-c]/m&(c<j)\\0&(c=j)\\f[i-1][i-c+j]/m&(c>j)\end{cases}$
注意到$j=c$时是不用计算的。
代码
#include <bits/stdc++.h>
#define re register
using namespace std;
double f[60][60]; //f[i][j]表示还剩i个人时第j个人的获胜概率
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;
}
转移写错啦
已修改。
窝以前是怎么写错的。。
我都不会算概率