HDU 4652 Dice

嘟嘟嘟

题目大意就是对于一个m面的骰子，回答这么两个问题：

1.求连续扔n次都是同一数字的期望次数。

2.求连续扔n次每一次数字都不相同的期望次数。

对于期望dp特别菜的我来说，这道题已经算是很难了。反正是抠了一天……

我们先看第一问。

令f_i表示连续 i 次数字都相同的期望，那么要考虑他能转化到什么状态，而不是由什么状态转化过来。

转化到什么状态要考虑到所有情况：包括扔的数字相同的和不同两种情况，于是转移方程就写出来了：

　　f_i = 1 / m * f_i+1 + (m - 1) / m * f₁.

因为如果扔到的数字不同，就退回到了f₁.

然而这个方程是有后效性的，所以变一个形：

　　f_i+1 = m * f_i - (m - 1) * f₁

还可以再变，相邻两项作差得：

　　f_i+1 - f_i = m * (f_i - f_i-1)

当i = 1时，a₁ = f₁ = 1

当i >= 2时,令a_i = f_i - f_i-1

于是a_i就是一个公比为m的等比数列。

然后很显然

　　f_n = S_n = a₁ * (1 - q^_n) / (1 - q) = (1 - mⁿ) / (1 - m).

用快速幂求解即可。

然后是第二问：

令f[i]表示抛出 i 次不一样的数字的期望，则

　　f_i = (m - i) / m * f_i+1 + 1/ m * f_i + 1 / m * f_i-1 + 1/ m * f_i-2 +……+ 1 / m * f₁.

因为有1 / m的概率和第f_j次是相同的。

然后每一次将f_i累加到f_n就行了。

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<cctype>

 #include<vector>

 #include<stack>

 #include<queue>

 using namespace std;

 #define enter puts("")

 #define space putchar(' ')

 #define Mem(a, x) memset(a, x, sizeof(a))

 #define rg register

 typedef long long ll;

 typedef double db;

 const int INF = 0x3f3f3f3f;

 const db eps = 1e-;

 const int maxn = 1e6 + ;

 int T, d, m, n;

 db dp[maxn];

 int quickpow(int a, int b)

 {

     int ret = ;

     while(b)

     {

         if(b & ) ret *= a;

         a *= a; b >>= ;

     }

     return ret;

 }

 int main()

 {

     while(scanf("%d", &T) != EOF)

     {

     while(T--)

     {

         scanf("%d%d%d", &d, &m, &n);

         if(!d) printf("%.9lf\n", (db)(quickpow(m, n) - ) / (db)(m - ));

         else

         {

             dp[] = 1.00; dp[n] = dp[];

             for(rg int i = ; i < n; ++i)

             {

                 dp[i] = (db)m / (db)(m - i) * dp[i - ];

                 dp[n] += dp[i];

             }

             printf("%.9lf\n", dp[n]);

         }

     }

     }

     return ;

 }

巴特西

HDU 4652 Dice

最新文章

热门文章