动态规划与概率
约瑟夫问题变形：m张牌，每次随机抽一张牌，牌上数字mi，从0报数到mi-1的人出局，问每个人获胜概率。
1<=n,m,卡牌上数字<=50
关于约瑟夫问题是可以递推求出n个人x固定的时候胜利的人的
f[i]表示i个人中获胜的人是谁，f[i]=(f[i-1]+x)%n
考虑i个人的第一轮中，第x个人出局后，所有人从x,x+1...0,1,x-2重新编号为0,1...n-2，那么又变成了一个规模较小的问题，同时上一次的获胜者y在第一轮中应该位于(y+x)%n的位置
这道题目中，设fi[i][j]表示i个人的时候，第j个人获胜的概率，fi[i][j]=sigma((k+mi)%i==j)f[i-1][k]/m，初始化fi[1][0]=100(百分数表示)，最后输出fi[n][]就可以了。
可以由f[i][j]→f[i+1][(j+x)%(i+1)] 即当(k+mi)%i==j时
从简单推到一般 先想一个人时 获胜率肯定为100% 再往后推
#include<bits/stdc++.h> using namespace std; #define Max(x,y) (x)>(y)?(x):(y) #define Min(x,y) (x)>(y)?(y):(x) #define rg register #define ll long long const int N=100+5,M=0,inf=0x3f3f3f3f,P=99999997; int n,m,a[N]; double f[N][N]; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } int main(){ // freopen("in.txt","r",stdin); rd(n),rd(m); for(int i=1;i<=m;++i) rd(a[i]); f[1][0]=f[1][1]=100.0; for(int i=2;i<=n;++i) for(int j=1;j<=i;++j){ for(int k=1;k<=m;++k){ int x=(a[k]%i)?a[k]%i:i; if(x<j) f[i][j]+=f[i-1][j-x]/m; else if(x>j) f[i][j]+=f[i-1][i-(x-j)]/m; } } for(int i=1;i<=n;++i) printf("%.2f%% ",f[n][i]); return 0; }