<h1 id="heading">题目</h1>
{% fold 点击显/隐题目 %}
<div class="oj"><div class="part" title="Description">
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: 
 <ul><li>0 m n: ask for the expected number of tosses until the last n times results are all same.</li><li>1 m n: ask for the expected number of tosses until the last n consecutive results are pairwise different.</li></ul>
</div><div class="part" title="Input">
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.
</div><div class="part" title="Output">
For each query, output the corresponding result. The answer will be considered correct if the absolute or relative error doesn't exceed 10-6.
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
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
</div><div class="output part" title="Sample Output">
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
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
<blockquote>
求m面骰子投出连续n次相同/不相同的数学期望
</blockquote>
根据正向推概率,逆向推期望的原则来看,我们应该采取从后往前推得形式来计算这道题
首先先来分析dp的意义 
对于第一种情况而言,需要求连续n次相同的期望 
如果用<code>dp[i]</code>表示<code>i</code>个相同的期望 
对于任意一种情况,都有对于<code>i</code>有<code>1/m</code>的概率和前一数字相同,也有<code>(m-1)/m</code>的概率和前一数字不同 
也即: <code>dp[i]</code>可以转移至<code>dp[1]</code>和<code>dp[i+1]</code> 
该函数无后效性,并且我们只能得到 <code>dp[i+1]=(1/m)*dp[i]</code> 和 <code>dp[1] += ((m-1)/m)*dp[i]</code> 两个式子 
因此,应该换一种含义,使<code>dp</code>可以逆向推出答案
用<code>dp[i]</code>表示已经有<code>i</code>个连续,到<code>n</code>个连续的期望 
那么很显然 <code>dp[n] = 0</code> 
并且<code>dp[0] = dp[1] + 1</code> (对于<code>0</code>个相同,显然随便投一个数字都可以满足要求) 
而且根据含义,有 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>d</mi><mi>p</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo>=</mo><mn>1</mn><mo>+</mo><mfrac><mn>1</mn><mi>m</mi></mfrac><mo>×</mo><mi>d</mi><mi>p</mi><mo stretchy="false">[</mo><mi>i</mi><mo>+</mo><mn>1</mn><mo stretchy="false">]</mo><mo>+</mo><mfrac><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow><mi>m</mi></mfrac><mo>×</mo><mi>d</mi><mi>p</mi><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">dp[i] = 1 + \frac{1}{m} \times dp[i+1] + \frac{m-1}{m} \times dp[1]</annotation></semantics></math>dp[i]=1+m1​×dp[i+1]+mm−1​×dp[1]
剩下就是数学化简过程了 
{% raw %}$ 
\begin{align*} 
dp[i] &amp;= 1 + \frac{1}{m} \times dp[i+1] + \frac{m-1}{m} \times dp[1] \ 
dp[i] - dp[1] &amp;= 1 + \frac{1}{m} \times (dp[i+1] - dp[1]) \ 
dp[i] - dp[1] &amp;= m \times (dp[i-1] - dp[1] - 1) \ 
令 a_i &amp;= dp[i]-dp[1] \ 
a_i &amp;= m \times a_{i-1} - m \ 
a_i &amp;= m^2 \times a_{i-2} - m^2 - m \ 
&amp;…… \ 
a_i &amp;= m^{i-1} \times a_1 - \frac{m^i-m}{1-m} \ 
dp[i] - dp[1] &amp;= - \frac{m-m^i}{1-m} \ 
dp[i] &amp;= dp[1] + \frac{m^i-m}{1-m} \ 
\ 
dp[1] &amp;= dp[n] - \frac{m^n-m}{1-m} \ 
dp[0] &amp;= dp[n] - \frac{m^n-m}{1-m} + 1 \ 
dp[0] &amp;s= \frac{m^n-m}{m-1} + 1 
\end{align*} 
${% endraw %}
也即,对于第一种情况,答案就是 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mfrac><mrow><msup><mi>m</mi><mi>n</mi></msup><mo>−</mo><mi>m</mi></mrow><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></mfrac><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">\frac{m^n-m}{m-1} + 1</annotation></semantics></math>m−1mn−m​+1
第二种情况同理 
按照相同的概念可以推出 
{% raw %}$ 
\begin{align*} 
dp[0] &amp;= 1 + dp[1] \ 
dp[i] &amp;= \frac {\sum_{k=1}^{i}dp[k]}{m} + \frac{m-i}{m}\times dp[i+1] \ 
dp[i-1] &amp;= \frac {\sum_{k=1}^{i-1}dp[k]}{m} + \frac{m-i+1}{m} \times dp[i] \ 
则 dp[i] - dp[i-1] &amp;= \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] &amp;= \frac{m-i}{m}\times (dp[i+1] - dp[i]) \ 
dp[i] - dp[i-1] &amp;= \frac{m}{m-i+1} \times (dp[i-1]-dp[i-2]) \ 
dp[i-1] - dp[i] &amp;= \frac{m}{m-i+1} \times (dp[i-2]-dp[i-1]) \ 
\ 
dp[0] - dp[1] &amp;= 1 \ 
dp[1] - dp[2] &amp;= \frac{m}{m-1} \times 1 \ 
dp[2] - dp[3] &amp;= \frac{m}{m-2} \times \frac{m}{m-1} \times 1 \ 
&amp;……\ 
dp[n-1] - dp[n] &amp;= \prod_{j=0}^{n-1} \frac{m}{m-j} \
\therefore dp[0] - dp[n] &amp;= \sum_{i=0}^{n-1} \prod_{j=0}^{i} \frac{m}{m-j} \ 
dp[0] &amp;= \sum_{i=0}^{n-1} \prod_{j=0}^{i} \frac{m}{m-j} 
\end{align*} 
${% endraw %}
最后要计算的就是 {% raw %}<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msubsup><msubsup><mo>∏</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mi>i</mi></msubsup><mfrac><mi>m</mi><mrow><mi>m</mi><mo>−</mo><mi>j</mi></mrow></mfrac></mrow><annotation encoding="application/x-tex">\sum_{i=0}^{n-1} \prod_{j=0}^{i} \frac{m}{m-j}</annotation></semantics></math>∑i=0n−1​∏j=0i​m−jm​{% endraw %} 
<code>O(n)</code>的时间可以得到答案
<h1 id="heading-2">代码</h1>
{% fold 点击显/隐代码 %}```cpp Dice <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份 
#include <cstdio>
double pow(double a, int n) { 
if (n == 0) 
return 1.0; 
double ans = pow(a, n &gt;&gt; 1); 
return ans * ans * (n &amp; 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 &lt; n; ++i) { 
p *= (double)m / (m - i); 
sum += p; 
} 
return sum; 
}
int main() { 
int T; 
int c, n, m;
<pre><code>while (scanf(&quot;%d&quot;, &amp;T) != EOF) {
 while (T--) {
 scanf(&quot;%d%d%d&quot;, &amp;c, &amp;m, &amp;n);
 double (*calc)(int, int) = (!c ? &amp;calc1 : &amp;calc2);
 printf(&quot;%.16f\n&quot;, calc(n, m));
 }
}
return 0;
</code></pre>
}
<pre style="background-color:#fff">{% endfold %}</pre>

HDU 4652.Dice