Qiuly

Dice 概率/期望DP HDU4652
对于第一问,设 $f_i$ 表示已经连续了 $i$ 次结果相同,到 $f_n$ 的期望次数。那么当前的一次骰子有 ...
扫描右侧二维码阅读全文
27
2019/05

Dice 概率/期望DP HDU4652

对于第一问,设 $f_i$ 表示已经连续了 $i$ 次结果相同,到 $f_n$ 的期望次数。那么当前的一次骰子有 $\frac{1}{m}$ 的概率会掷到一样的面,也就变成了 $f_{i+1}$ ,那么剩下的情况就只能变成 $f_1$ 了。

$$ f_i=\frac{1}{m}f_{i+1}+\frac{m-1}{m}f_1+1\\ f_i=\frac{1}{m}f_{i+1}+\frac{m-1}{m}f_1+1,f_{i+1}=\frac{1}{m}f_{i+2}+\frac{m-1}{m}f_1+1\\ f_i-f_{i+1}=\frac{1}{m}f_{i+1}+\frac{m-1}{m}f_1+1-(\frac{1}{m}f_{i+2}+\frac{m-1}{m}f_1+1)\\ f_i-f_{i+1}=\frac{1}{m}f_{i+1}-\frac{1}{m}f_{i+2}\\ m(f_i-f_{i+1})=f_{i+1}-f_{i+2}f_i=\frac{1}{m}f_{i+1}+\frac{m-1}{m}f_1+1\\ f_i=\frac{1}{m}f_{i+1}+\frac{m-1}{m}f_1+1,f_{i+1}=\frac{1}{m}f_{i+2}+\frac{m-1}{m}f_1+1\\ f_i-f_{i+1}=\frac{1}{m}f_{i+1}+\frac{m-1}{m}f_1+1-(\frac{1}{m}f_{i+2}+\frac{m-1}{m}f_1+1)\\ f_i-f_{i+1}=\frac{1}{m}f_{i+1}-\frac{1}{m}f_{i+2}\\ m(f_i-f_{i+1})=f_{i+1}-f_{i+2} $$

通过第一个式子我们可以得知 $f_0-f_1=1$ ,那么 $f_{1}-f_2=m\cdots f_{n-1}-f_n=m^{n-1}$ ,求和后 $f_0-f_n=1+m+m^2+m^3\cdots m_{n-1}=\frac{m^n-1}{m-1}$ ,因为 $f_n=0$ ,所以答案直接算就好了。

对于第二问,设 $f_i$ 表示已经连续了 $i$ 次不同的结果,到 $f_n$ 的期望次数,当前掷一次骰子不得到与之前重复的面的概率为 $\frac{m-i}{m}$ :

$$ f_i=\frac{m-i}{m}f_{i+1}+\frac{i}{m}f_1 $$

不过,这样真的是对的吗?如果当前的重复对象是这个连续不同序列的第一项,那么我们不应该回到 $f_{1}$ ,而是回到 $f_{i}$ ,这样的概率为 $\frac{1}{m}$ ,那么我们列出新的式子:

$$ f_i=\frac{m-i}{m}f_{i+1}+\frac{1}{m}(f_1+f_2+\cdots+f_{i})+1\\ f_i-f_{i+1}=\frac{m-i-1}{m}(f_{i+1}-f_{i+2})\\ \frac{m}{m-i-1}(f_i-f_{i+1})=f_{i+1}-f_{i+2}\\ $$

显然 $f_0-f_1=1$ ,那么根据下面的公式 $f_1-f_2=\frac{m}{m-1},f_2-f_3=\prod_{i=1}^{2}\frac{m}{m-i}$ ,发现有点规律!$f_{n-1}-f_n=\prod_{i=1}^{n-1}\frac{m}{m-i}$ ,对所有式子求和后可以得到 $f_0-f_n=1+\sum_{i=1}^{n-1}\prod_{j=1}^{i}\frac{m}{m-j}$ ,$f_n$ 显然为 $0$ ,那么我们就得到答案了。

Code:

#include <cmath>
#include <cstdio>
using namespace std;

double S0(int n,int m) {return (pow(m,n)-1.0)/(m-1.0);}
double S1(int n,int m) {
    double res=1,ans=1;
    for(int i=1;i<n;++i) res=1.0*m/(m-i)*res,ans+=res;
    return ans;
}

int main() {
    int T,op,n,m;
    while(scanf("%d",&T)!=EOF)while(T--) {
        scanf("%d%d%d",&op,&m,&n);
        printf("%.9lf\n",op?S1(n,m):S0(n,m));
    }
    return 0;
}
最后修改:2019 年 05 月 30 日 03 : 26 PM

发表评论