题解 P1409 【骰子】
ChthollyTree
2019-10-02 18:50:18
你们的方法啊
都太复杂了！
由于这里只要求保留⑨位小数，所以说，我们不必推方程组
和正解做法一样，我们定义$f[i][j]$表示有$i$个人，你在第$j$个
我们定义$g[i][j]$
$g[i][1] = \frac{1}{6}$
$g[i][j](j!=1) = f[i-1][j-1]$
$next(j)$表示$j$在环上的上一个位置,即$next(1) = i$其他$next(j) = j-1$
然后$f[i][j]$就是$g[i][j] + \frac{1}{2}f[i][next(j)]$
也就是
$\sum_{k=1}^{inf}\frac{1}{2^k}*g[i][next(next...next(j))]$（$k$个next）
由于到$k$比较大的时候，$\frac{1}{2^k}$ 非常小
此时对答案的贡献可以忽略不计
一般$k$上限取50比较好
可能看代码会更好理解一些
```
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005
#define db double
int n,m;
db f[MAXN][MAXN];
db g[MAXN][MAXN];
void rd() {
cin >> n >> m;
}
signed main()
{
rd();
f[1][1] = 1;
for(int i = 2; i <= n; i ++) {
g[i][1] = (db)1/6;
for(int j = 2; j <= i; j ++) {
g[i][j] = (db)1/3*f[i-1][j-1];
}
for(int j = 1; j <= i; j ++) {
db w = 1;
int ne = j;
for(int t = 1; t <= 50; t ++) {
f[i][j] += g[i][ne] * w;
w /= 2;
ne --;
if(ne < 1) ne = i;
}
}
}
printf("%.9lf",f[n][m]);
return 0;
}
```