题目链接
题解
f[i][j] 表示i 个人坐成一圈玩游戏，到最后第j 个人胜出的概率
这样有n^2个状态数，O（n）转移
首先枚举庄家抽到的卡牌k，得到这一轮被淘汰的人的位置d 。表示此轮第j个人被淘汰）。
第d个人被淘汰之后，剩下的i-1 个人要组成一个新的环，庄家为第d 个人的下一个。
当d>j 时，第jj个人是新的环里从新庄家数起的第i-d+j个人，当d<j时，第j个人是新的环里从新庄家数起的第j-d 个人。
[f[i][j]+=
egin{cases}
f[i-1][i-d+j]/m & ext {d>j } \
f[i-1][j-d]/m & ext {d<j } \
0 & ext {d==j }
end{cases}]
code
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn = 57;
inline int read() {
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
return x*f;
}
int n,m;
int a[maxn];
double dp[maxn][maxn];
int main() {
n=read(),m=read();
for(int i=1;i<=m;++i)
a[i]=read();
dp[1][1]=100;
for(int i=1;i<=n;++i) {
for(int j=1;j<=i;++j) {
for(int k=1;k<=m;++k) {
int to=a[k]%i;if(!to)to=i;
//printf("%d
",to);
//else dp[i][j]+=dp[i-1][(j-to+i-1)%i+1]/m;
if(to>j) dp[i][j]+=dp[i-1][i-to+j]/m;
else if(to<j) dp[i][j]+=dp[i-1][j-to]/m;
// printf("%.2lf %%",dp[i][j]);
}
}
}
for(int i=1;i<=n;++i)
printf("%.2lf%% ",dp[n][i]);
return 0;
}