洛谷p2059 概率dp

首先仔细读题目
按顺时针从庄家位置数第X个人将被处决即退出游戏，
x为1的时候被处决的就是庄家，千万不要理解错位庄家的位置+x就是被处决人的位置，我一开始就是这么理解然后调完发现怎么加起来答案是1但是和样例长的不一样

我们思考下怎么做，对于如此小的数据范围，肯定是可以枚举每一次游戏某一个人获得胜利的概率，如果比如数据范围偏大，那就dp的设计就要去想一次dp得全部答案的方法，要有这个设计方程前的理性思考。

如果我们要得到每个人胜利的概率就需要明确的是

1. 在进行的所有轮次，主人公必定不能死。
2. 我们不去关心到底现在谁是还活着的人。

为什么我们不需要关心现在谁活着？因为对于任意一轮，都是庄家选牌，然后某个人死了，然后庄家换人。不管在场的人是谁，在选牌概率方面都是不会有影响的，明确了这点之后就可以舍弃掉枚举现在谁还活下来这种状态。

接下来是，我们需要什么状态？除了最后一轮之前，我们必然会拥有的东西是什么？**主人公和庄家！！！！**这两个是必然会存在（可能是同一人）。

明确了这上面这一点后就是要找出主人公和庄家最重要的关系。就是位置！！！
庄家选牌，然后从庄家位置数第X个人将被处决，我们的状态可以设计为庄家到主人公顺时针的位置距离。因为这样我们就可以知道庄家选了这张牌后，到底我们的主人公死没死。
设计f[i][j], 表示的是现在在第i轮， 庄家与主人公的距离为j的概率。
状态设计完了后，我们要考虑怎么转移，其实就是我们要算出新的庄主与主人公的顺时针距离是多少。
设
z1 : 当前庄主与新庄主的顺时针距离，
z2:当前庄主与主人公的顺时针距离
num:当前轮的人数是多少（还没杀死人）
我们需要知道新庄主与主人公的顺时针距离，手动玩一玩推一推就可以知道是

int  t;
	if (z1 >= z2)t =  ((num + 1) - (z1 - z2 + 1) + 1);
	else  t = z2  - z1 + 1;

因为是顺时针距离吗，如果z1 >= z2那么就是要让新庄主跑一个大圈回到主人公，要从新庄主走到从1开始的位置让在走到主人公。如果是z1 < z2 那么就是直接新庄主往前跑一点点就是可以到达主人公，不需要新走一遍。

由于我们是设计的状态只是主人公与庄主是位置。所以我们可以这么认为每一新的轮次都把庄主看做在位置1就比较方便理解。

然后写代码的话就是从f[0][j] = 1,j就是主人公与庄主的位置，不断向外部转移就好了。最后答案就是f[n-1][1],1就是指的庄主与主人公位置是1，也就代表着，庄主就是主人公啦，最后的幸存者。其实我觉得唯一的难点是那个推出新庄主与主人公的顺时针位置，我推了好久

int n,m,node[max_];//f[i][j]:第i论，庄家与主人公的顺时针距离为j
double f[max_][max_];
int get_len(int z1, int z2,int num) {
	int  t;
	if (z1 >= z2)t =  ((num + 1) - (z1 - z2 + 1) + 1);
	else  t = z2  - z1 + 1;
	 while (t > num){
		 t -= num;
	 }
	 return t;
}

signed main() {
	n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		node[i] = read();
	}
	double stander = 1.0 / m;
	for (int i = 1; i <= n; i++) {
		//主人公是i
		memset(f, 0, sizeof(f));
		f[0][i] = 1.0;
		for (int j = 0; j < n; j++) {
			//游戏进行到第j轮
			for (int z = 1; z <= n; z++) {
				//庄家与主人公的距离为z
				if (f[j][z] < eps)continue;
				int num = n - j;
				for (int x = 1; x <= m; x++) {
					//枚举所有牌
					int wei = node[x];
					while (wei > num){
						wei -= num;
					}
					if (wei == z)continue;
					wei++;
					while (wei > num ) {
						wei -= num ;
					}
					int len = get_len(wei, z, num);
					f[j + 1][len] += stander * f[j][z];
				}
			}
		}
		printf("%.2lf", f[n - 1][1] * 100);
		cout << '%';
		if (i != n)cout << " ";
	}
	return 0;
}