P2059 [JLOI2013]卡牌游戏

题意

有\(n\)个人玩约瑟夫游戏，有\(m\)张卡，每张卡上有一个正整数，每次庄家有放回的抽一张卡，干掉从庄家起顺时针的第\(k\)个人(计算庄家)，干掉的那位下家成为新庄家，初始庄家为1，最后活下的人胜利，求每个人获胜概率。

---

约瑟夫类型的题目有个套路，以庄家为相对位置进行重新编号。

可以进行dp

\(dp_{i,j}\)表示第\(i\)轮(倒着数的)距离庄家为\(j\)的人的获胜概率，这样就可以很简单的转移了

复杂度\(O(n^2m)\)

---

Code:

#include <cstdio>

double dp[52][52];

int n,m,bee[52];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++) scanf("%d",bee+i);

	dp[1][1]=100;

	for(int i=2;i<=n;i++)

		for(int j=1;j<=i;j++)

			for(int k=1;k<=m;k++)

			{

				int c=bee[k]%i;

				c=c?c:c+i;

				if(c>j) dp[i][j]+=dp[i-1][i+j-c]/m;

				else if(c<j) dp[i][j]+=dp[i-1][j-c]/m;

			}

	for(int i=1;i<=n;i++) printf("%.2lf ",dp[n][i]);

	return 0;

}

---

2019.2.11