HDU4652 Dice(期望dp推式子)

题目链接

第一问,求连续$n$个数字相同的期望

定义$dp[i]$是已经$i$个不相同,到达目标状态的期望

$dp[n?1]=\frac{1}{m}?dp[n]+\frac{m?1}{m}?dp[1]+1$

$dp[n?2]=\frac{1}{m}?dp[n?1]+\frac{m?1}{m}?dp[1]+1$

…

$dp[i]=\frac{1}{m}?dp[i+1]+\frac{m?1}{m}?dp[1]+1$

那么$dp[i]?dp[i?1]=\frac{1}{m}(dp[i+1]?dp[i])$

那么如果令$d_i=dp[i]?dp[i?1]$,不就是公比为$m$的等比数列吗?

$d_n=dp[1]?dp[0]=?1$

$\sum _{i=1}^n{d}_i=?dp[0]$(错位相减法)

所以可以等比数列求和快速解得

第二问,求连续n个数不相同的概率

定义$dp[i]$为已经$i$个不相同,到达目标的期望

$dp[i]=\frac{m?i}{m}?dp[i+1]+\frac{1}{m}\sum _{j=1}^{i}dp[j]$

$dp[i+1]=\frac{m?i?1}{m}?dp[i+2]+\frac{1}{m}\sum _{j=1}^{i+1}dp[j]$

让$dp[i]?dp[i+1]$得到

$$dp[i]?dp[i+1]=\frac{m?i}{m}?dp[i+1]?\frac{m?i+1}{m}?dp[i+2]?\frac{1}{m}?dp[i+1]$$

$$dp[i]?dp[i+1]=\frac{m?i?1}{m}(dp[i+1]?dp[i+2])$$

$dp[0]?dp[1]=1$

$dp[1]?dp[2]=\frac{m}{m?1}$

$dp[2]?dp[3]=\frac{m}{m?1}?\frac{m}{m?2}$

…

把上面所有等式相加得到

$dp[0]?dp[n]=1+\frac{m}{m?1}+\frac{m}{m?1}?\frac{m}{m?2}....$

#include <bits/stdc++.h>
using namespace std;
int t;
int quick_pow(int x,int n)
{int ans=1;while( n ){if( n&1 )	ans=ans*x;n>>=1;x=x*x;}	return ans;
}
int main()
{while( cin >> t ){while( t-- ){int ok,m,n;cin >> ok >> m >> n;if( ok ){double ans=1,temp=1;for(int i=1;i<=n-1;i++){temp*=m*1.0/(m-i);ans+=temp;}printf("%.6lf\n",ans);}else{double ans=(1.0-quick_pow(m,n))/(1.0-m);printf("%.6lf\n",ans);}}}
}