大致题意： 有\(6\)个人玩大富翁，共有\(n\)块地，进行\(500\)轮，已知每个人掷骰子掷出\(1\sim6\)的概率。当某人到达一块未被占领的地时，他可以占领它。求最后每个人占有地的期望块数。
概率\(DP\)
这应该是一道概率\(DP\)题。
我们可以定义\(Arrive_{i,j,k}\)表示第\(i\)个人在第\(j\)轮到达第\(k\)块地的概率，\(Never_{i,j,k}\)表示第\(i\)个人在第\(j\)轮及之前从未到达过第\(k\)块地的概率。
显然，初始化\(Arrive_{i,0,1}=1,Never_{i,0,j}=1(1\le j\le n)\)。
然后，我们枚举\(i,j,k\)以及骰子掷出的步数\(t\)来进行转移。
由\(t\)可计算出上一步应由\(pre=(k+n-t\%n-1)\%n+1\)转移过来。
注意转移时应特判\(pre\)不为\(1\)，应为\(pre=1\)时说明已经走出了一个循环，接下来会重复计算。
但若这是第一轮，当\(pre=1\)时\(Arrive\)数组依然需要转移，因为\(Arrive\)数组此时只有\(k=1\)的位置上有值。
计算答案
接下来考虑如何计算答案。
我们枚举第\(i\)个人，第\(j\)轮，以及第\(k\)块地，则应将第\(i\)个人的\(ans\)加上下面这个式子：
\[\prod_{t=1}^{i-1}Never_{t,j,k}\cdot Arive_{i,j,k}\cdot\prod_{t=i+1}^6Never_{t,j-1,k}\]
这应该比较好理解：
- 当\(t<i\)时，第\(t\)个玩家比第\(i\)个玩家先走，我们要确保第\(t\)个玩家在这一轮及以前从未走过第\(k\)块地。
- 当\(t=i\)时，我们要确保第\(t\)个玩家在这一轮刚好走到第\(k\)块地。
- 当\(t>i\)时，第\(t\)个玩家比第\(i\)个玩家后走，因此这个玩家就算这一轮走到第\(k\)块地也没关系，所以只需确保他在这一轮以前从未走过第\(k\)块地即可。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 500
using namespace std;
int n;double p[7][7],Arrive[7][N+5][N+5],Never[7][N+5][N+5];
int main()
{
RI i,j,k,t,pre;Reg double ans,res;for(scanf("%d",&n),i=1;i<=6;++i) for(j=1;j<=6;++j) scanf("%lf",&p[i][j]);//读入
for(i=1;i<=6;++i)
{
for(Arrive[i][0][1]=j=1;j<=n;++j) Never[i][0][j]=1;//初始化
for(j=1;j<=500;++j) for(k=1;k<=n;++k) for(t=1;t<=6;++t)//枚举状态进行转移
{
(pre=(k+n-t%n-1)%n+1)^1&&(Never[i][j][k]+=p[i][t]*Never[i][j-1][pre]),//转移Never数组
(pre^1||!(j^1))&&(Arrive[i][j][k]+=p[i][t]*Arrive[i][j-1][pre]);//转移Arrive数组
}
}
for(i=1;i<=6;++i,printf("%.3lf\n",ans)) for(ans=0,j=1;j<=500;++j) for(k=1;k<=n;++k)//统计答案
{
for(res=Arrive[i][j][k],t=1;t^i;++t) res*=Never[t][j][k];
for(t=i+1;t<=6;++t) res*=Never[t][j-1][k];ans+=res;
}return 0;
}