# 题目

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

You have a dice with m faces, each face contains a distinct number. We assume when we tossing the dice, each face will occur randomly and uniformly. Now you have T query to answer, each query has one of the following form:
• 0 m n: ask for the expected number of tosses until the last n times results are all same.
• 1 m n: ask for the expected number of tosses until the last n consecutive results are pairwise different.
The first line contains a number T.(1≤T≤100) The next T line each line contains a query as we mentioned above. (1≤m,n≤106) For second kind query, we guarantee n≤m. And in order to avoid potential precision issue, we guarantee the result for our query will not exceeding 109 in this problem.
For each query, output the corresponding result. The answer will be considered correct if the absolute or relative error doesn't exceed 10-6.
6 0 6 1 0 6 3 0 6 5 1 6 2 1 6 4 1 6 6 10 1 4534 25 1 1232 24 1 3213 15 1 4343 24 1 4343 9 1 65467 123 1 43434 100 1 34344 9 1 10001 15 1 1000000 2000
1.000000000 43.000000000 1555.000000000 2.200000000 7.600000000 83.200000000 25.586315824 26.015990037 15.176341160 24.541045769 9.027721917 127.908330426 103.975455253 9.003495515 15.056204472 4731.706620396
{% endfold %}

# 题解

dp[i]表示已经有i个连续,到n个连续的期望

{% 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 %}

{% 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 %}

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 %}`