<h1 id="heading">题目</h1>
<p>{% fold 点击显/隐题目 %}</p>
<div class="oj"><div class="part" title="Description"> 
There is a very simple and interesting one-person game. You have 3 dice, namely Die1, Die2 and Die3. Die1 has K1 faces. Die2 has K2 faces. Die3 has K3 faces. All the dice are fair dice, so the probability of rolling each value, 1 to K1, K2, K3 is exactly 1 / K1, 1 / K2 and 1 / K3. You have a counter, and the game is played as follow:  
<p>Set the counter to 0 at first.<br>
Roll the 3 dice simultaneously. If the up-facing number of Die1 is a, the up-facing number of Die2 is b and the up-facing number of Die3 is c, set the counter to 0. Otherwise, add the counter by the total value of the 3 up-facing numbers.<br>
If the counter's number is still not greater than n, go to step 2. Otherwise the game is ended.</p>
<p>Calculate the expectation of the number of times that you cast dice before the end of the game.</p>
</div><div class="part" title="Input">
There are multiple test cases. The first line of input is an integer T (0 &lt; T &lt;= 300) indicating the number of test cases. Then T test cases follow. Each test case is a line contains 7 non-negative integers n, K1, K2, K3, a, b, c (0 &lt;= n &lt;= 500, 1 &lt; K1, K2, K3 &lt;= 6, 1 &lt;= a &lt;= K1, 1 &lt;= b &lt;= K2, 1 &lt;= c &lt;= K3).  
</div><div class="part" title="Output">
For each test case, output the answer in a single line. A relative error of 1e-8 will be accepted.  
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
2
0 2 2 2 1 1 1
0 6 6 6 1 1 1
</div><div class="output part" title="Sample Output">
1.142857142857143
1.004651162790698
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
<p>题目思维比较独特,需要一些数学技巧<br>
<div class='image'><a href='//static.oyohyee.com/post/zoj3329.png' target='_blank' rel='noopener noreferrer'><img src="//static.oyohyee.com/post/zoj3329.png" /></a></div></p>
<p>如图,设 <code>dp[i]</code> 表示当前计数为 <code>i</code> 的时候结束游戏的期望值<br>
则在状态 <code>i</code> 的时候可以转移到状态 <code>0</code> 和 状态 <code>i+j</code><br>
计算出当前骰子投出和为 <code>j</code> 的概率为 <code>p[j]</code>(dp[0]是投出<code>a</code>,<code>b</code>,<code>c</code>的概率)<br>
则有 <code>dp[i] = dp[0]p[0] + sum{ dp[i+j]p[j] }</code></p>
<p>然后会发现一个很重要的问题,<strong>状态同时向两侧转移</strong><br>
也即无论是从大到小还是从小到大或者其他转移形式,这个式子都不满足<strong>无后效性</strong><br>
但是这里可以看出,往小了转移只有 <code>dp[0]</code> 一个状态<br>
可以用数学重新推导一下</p>
<p>{% raw %}$<br>
\begin{align*}<br>
dp[i] &amp;= \sum (dp[i+j] \times p[j]) + dp[0] \times p[0]  \<br>
设: dp[i] &amp;= A[i] \times dp[0] + B[i] \<br>
带入原式得: dp[i] &amp;= \sum((A[i+j] \times dp[0] + B[i+j) \times p[j]) + dp[0] \times p[0] \<br>
整理得: dp[i] &amp;=\sum ((p[j]*A[i+j]) + p[0]) \times dp[0]) + \sum(p[j] \times B[i+j]) + 1 \<br>
\<br>
\therefore A[i] &amp;= \sum(p[j] \times A[i+j]) + p[0] \<br>
B[i] &amp;= \sum (p[j] \times B[i+j]) + 1 \<br>
\<br>
且: dp[0] &amp;= \frac{B[0]}{1-A[0]} \<br>
A[i] &amp;= B[i] = 0,i&gt;n<br>
\end{align*}<br>
${% endraw %}</p>
<p>这样只需要预先处理出 <code>p[i]</code> 然后用 <code>O(n)</code> 的时间求出 <code>A[i]</code>,<code>B[i]</code> 即可<br>
最后结果就是 <code>B[0]/(1-A[0])</code></p>
<h1 id="heading-2">代码</h1>
<p>{% fold 点击显/隐代码 %}```cpp One Person Game <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份<br>
#include <cstdio><br>
#include <cstring><br>
using namespace std;</p>
<p>#define Log(format, ...) //printf(format, ##<strong>VA_ARGS</strong>)</p>
<p>const int maxk = 3;<br>
const int maxnum = 20;<br>
const int maxn = 550;</p>
<p>int n, k[maxk], a[maxk];<br>
double A[maxn], B[maxn], p[maxnum];</p>
<p>int main() {<br>
int T;<br>
scanf(&quot;%d&quot;, &amp;T);<br>
while (T--) {<br>
scanf(&quot;%d%d%d%d%d%d%d&quot;, &amp;n, &amp;k[0], &amp;k[1], &amp;k[2], &amp;a[0], &amp;a[1], &amp;a[2]);</p>
<pre><code>    memset(p, 0, sizeof(p));
    for (int i = 1; i &lt;= k[0]; ++i)
        for (int j = 1; j &lt;= k[1]; ++j)
            for (int l = 1; l &lt;= k[2]; ++l) {
                if (i == a[0] &amp;&amp; j == a[1] &amp;&amp; l == a[2]) {
                    p[0] += 1;
                } else {
                    p[i + j + l] += 1;
                }
            }

    int sum = k[0] * k[1] * k[2];
    for (int i = 0; i &lt; maxnum; ++i) {
        p[i] = p[i] / sum;
        Log(&quot;%d %f\n&quot;, i, p[i]);
    }

    memset(A, 0, sizeof(A));
    memset(B, 0, sizeof(B));
    for (int i = n; i &gt;= 0; --i) {
        for (int j = 3; j &lt; maxnum; ++j) {
            Log(&quot;%d %d %f %f %f\n&quot;, i,j, p[j],A[i+j],B[i+j]);
            A[i] += p[j] * A[i + j];
            B[i] += p[j] * B[i + j];
        }
        Log(&quot;%d %f %f\n&quot;, i, A[i],B[i]);
        A[i] += p[0];
        B[i] += 1;
        Log(&quot;%d %f %f\n&quot;, i, A[i],B[i]);
    }

    printf(&quot;%.15f\n&quot;, B[0] / (1 - A[0]));
}
return 0;
</code></pre>
<p>}</p>
<pre style="background-color:#fff">{% endfold %}</pre>

ZOJ 3329.One Person Game