题目

{% fold 点击显/隐题目 %}

题解

求m面骰子投出连续n次相同/不相同的数学期望

根据正向推概率,逆向推期望的原则来看,我们应该采取从后往前推得形式来计算这道题

首先先来分析dp的意义
对于第一种情况而言,需要求连续n次相同的期望
如果用dp[i]表示i个相同的期望
对于任意一种情况,都有对于i有1/m的概率和前一数字相同,也有(m-1)/m的概率和前一数字不同
也即: dp[i]可以转移至dp[1]和dp[i+1]
该函数无后效性,并且我们只能得到 dp[i+1]=(1/m)*dp[i] 和 dp[1] += ((m-1)/m)*dp[i] 两个式子
因此,应该换一种含义,使dp可以逆向推出答案

用dp[i]表示已经有i个连续,到n个连续的期望
那么很显然 dp[n] = 0
并且dp[0] = dp[1] + 1 (对于0个相同,显然随便投一个数字都可以满足要求)
而且根据含义,有 dp[i]=1+1m×dp[i+1]+m−1m×dp[1]dp[i] = 1 + \frac{1}{m} \times dp[i+1] + \frac{m-1}{m} \times dp[1]

剩下就是数学化简过程了
{% raw %}$
\begin{align*}
dp[i] &= 1 + \frac{1}{m} \times dp[i+1] + \frac{m-1}{m} \times dp[1] \
dp[i] - dp[1] &= 1 + \frac{1}{m} \times (dp[i+1] - dp[1]) \
dp[i] - dp[1] &= m \times (dp[i-1] - dp[1] - 1) \
令 a_i &= dp[i]-dp[1] \
a_i &= m \times a_{i-1} - m \
a_i &= m^2 \times a_{i-2} - m^2 - m \
&…… \
a_i &= m^{i-1} \times a_1 - \frac{m^i-m}{1-m} \
dp[i] - dp[1] &= - \frac{m-m^i}{1-m} \
dp[i] &= dp[1] + \frac{m^i-m}{1-m} \
\
dp[1] &= dp[n] - \frac{m^n-m}{1-m} \
dp[0] &= dp[n] - \frac{m^n-m}{1-m} + 1 \
dp[0] &s= \frac{m^n-m}{m-1} + 1
\end{align*}
${% endraw %}

也即,对于第一种情况,答案就是 mn−mm−1+1\frac{m^n-m}{m-1} + 1

第二种情况同理
按照相同的概念可以推出
{% raw %}$
\begin{align*}
dp[0] &= 1 + dp[1] \
dp[i] &= \frac {\sum_{k=1}^{i}dp[k]}{m} + \frac{m-i}{m}\times dp[i+1] \
dp[i-1] &= \frac {\sum_{k=1}^{i-1}dp[k]}{m} + \frac{m-i+1}{m} \times dp[i] \
则 dp[i] - dp[i-1] &= \frac{1}{m} \times dp[i] + \frac{m-i}{m}\times dp[i+1] - \frac{m-i+1}{m} \times dp[i]) \
dp[i] - dp[i-1] &= \frac{m-i}{m}\times (dp[i+1] - dp[i]) \
dp[i] - dp[i-1] &= \frac{m}{m-i+1} \times (dp[i-1]-dp[i-2]) \
dp[i-1] - dp[i] &= \frac{m}{m-i+1} \times (dp[i-2]-dp[i-1]) \
\
dp[0] - dp[1] &= 1 \
dp[1] - dp[2] &= \frac{m}{m-1} \times 1 \
dp[2] - dp[3] &= \frac{m}{m-2} \times \frac{m}{m-1} \times 1 \
&……\
dp[n-1] - dp[n] &= \prod_{j=0}^{n-1} \frac{m}{m-j} \

\therefore dp[0] - dp[n] &= \sum_{i=0}^{n-1} \prod_{j=0}^{i} \frac{m}{m-j} \
dp[0] &= \sum_{i=0}^{n-1} \prod_{j=0}^{i} \frac{m}{m-j}
\end{align*}
${% endraw %}

最后要计算的就是 {% raw %}∑i=0n−1∏j=0imm−j\sum_{i=0}^{n-1} \prod_{j=0}^{i} \frac{m}{m-j}{% endraw %}
O(n)的时间可以得到答案

代码

{% fold 点击显/隐代码 %}```cpp Dice https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include

double pow(double a, int n) {
if (n == 0)
return 1.0;
double ans = pow(a, n >> 1);
return ans * ans * (n & 1 ? a : 1);
}

double calc1(int n, int m) { return (pow(m, n) - m) / (m - 1) + 1; }
double calc2(int n, int m) {
double sum = 0.0;
double p = 1.0;
for (int i = 0; i < n; ++i) {
p *= (double)m / (m - i);
sum += p;
}
return sum;
}

int main() {
int T;
int c, n, m;

while (scanf("%d", &T) != EOF) {
    while (T--) {
        scanf("%d%d%d", &c, &m, &n);
        double (*calc)(int, int) = (!c ? &calc1 : &calc2);
        printf("%.16f\n", calc(n, m));
    }
}
return 0;

}

{% endfold %}