卡牌遊戲(題解)

· · 题解

P2059题目传送门

思路设计

按照一般思路，N 个人有 m 张牌，最后需要求 N 个人胜利的概率。动态规划转移方程肯定会有一维表示第几人。

但是这道题是约瑟夫环的基础上进行游戏，每轮游戏完之后会踢出一个人，所以每轮游戏的人数是不一样的。

先考虑这样一个关键的问题，这道题是顺推还是逆推？

于是我们可以用 dp[i][j]} 表示剩下 i 个人的时候，从庄家开始第 j 个人的存活概率。

可能有人会问：为什么不用进行到第 i 轮游戏或者编号为 j 的人的获胜概率呢？

动态规划转移

设 dp[i][j] 表示剩下 i 个人的时候，从庄家开始第 j 个人的存活概率。

可以看出这里 j 表示的人的编号并不是确定的。

按照套路，先找出转移边界：dp[1][1]=1。意思是剩下 1 个人的时候，从庄家开始第一个人获胜的概率是 1。

然后第一层循环从 i=2 开始枚举剩下几个人，第二层循环 j 枚举抽到的卡牌数。

根据约瑟夫环，根据抽到的牌和这轮的人数算出这轮踢出的人。

算出来剩下 i 个人的时候，所有踢出人的位置，抽到对应每个人的概率显然就是牌的数量，即 \frac{1}{m}。

然后通过剩下 i-1 个人的状态推出剩下 i 个人的状态。剩下 i 个人的时候踢出的人的下一个人就是剩下 i-1 个人的时候的庄家。

然后根据这两轮庄家后相同的人转移：剩下 i-1 个人的时候，假设庄家是 o，剩下 i 个人的时候，假设庄家是 p，那么我们可以将剩下 i-1 个人的时候 o 之后的每个人的概率都转移到剩下 i 个人的时候 p 的之后每个人的上面。

如图，左边是剩下 i 个人的情况，右边是剩下 i-1 个人的情况，我们可以将左侧编号 1 转移到右侧编号 1，左侧编号 2 转移到右侧编号 2 等等。

设 p 和 k 是第 i 轮的庄家后第 p 个人和第 i-1 轮庄家后第 k 个人。这里要枚举庄家后每一个人，将每轮对应庄家转移，那么最后对于第 i 个人来说，他获胜的概率是 dp[n][i]。因为剩下 n 个人的时候，1 为最初的庄家，庄家后第 i 个人就是对应编号的第 i 个人。

最后放上代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
    inline int read(){
        int f(1),x(0);
        char ch=getchar();
        for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
        return f*x;
    }
    inline void Write(int x){
        if(x>9) Write(x/10);
        putchar(x%10+48);
    }
    inline void write(int x){
        if(x<0) putchar('-'),x=-x;
        Write(x);
        putchar(' ');
    }
}
using namespace Testify;
const int N=1e5+5;
int n,m;
double dp[55][55];//剩下i个人，赢的人从庄家 数起是j的概率()
int card[55];
signed main(void){
    n=read(),m=read();
    for(register int i=1;i<=m;i++){
        card[i]=read();
    }
    dp[1][1]=1.0;//只剩下1个人力
    for(register int i=2;i<=n;i++){//
        for(register int j=1;j<=m;j++){
            int p=card[j]%i;
            if(p==0) p=i;
            for(register int k=1;k<i;k++){//上一个状态
                p++;
                if(p>i) p=1;
                dp[i][p]+=(dp[i-1][k]/m);
            }
        }
    }

    for(register int i=1;i<n;i++){
        printf("%.2lf%% ",dp[n][i]*100);
    }
    printf("%.2lf%%",dp[n][n]*100);
    return 0;
}