Dice

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 211    Accepted Submission(s): 127


Problem Description Given a normal dice (with 1, 2, 3, 4, 5, 6 on each face), we define: 
F(N) to be the expected number of tosses until we have a number facing up for N consecutive times.
H(N) to be the expected number of tosses until we have the number '1' facing up for N consecutive times.
G(M) to be the expected number of tosses until we have the number '1' facing up for M times.
Given N, you are supposed to calculate the minimal M1 that G (M1) >= F (N) and the minimal M2 that G(M2)>=H(N)  
Input The input contains multiple cases. 
Each case has a positive integer N in a separated line. (1<=N<=1000000000) 
The input is terminated by a line containing a single 0.  
Output For each case, output the minimal M1 and M2 as required in a single line, separated by a single space. 
Since the answer could be very large, you should output the answer mod 2011 instead.  
Sample Input 1 2 0  
Sample Output 1 1 2 7  
Source 2013 ACM-ICPC吉林通化全国邀请赛——题目重现  
Recommend liuyiding   |   We have carefully selected several similar problems for you:  4934 4933 4932 4931 4930   
Statistic | Submit | Discuss | Note
设dp[i]为已经连续掷出i次相同点数,要到达目标状态所需的平均期望
则：dp[i] = (1/6)*(dp[i+1]+1) + (5/6)*(dp[1]+1)----------------------(1)
{ dp[0]是我们最终要求的值,dp[n] = 0 }


其中，下次掷出相同点数的概率为(1/6),再加上本身掷的一次,因此为(1/6)*(dp[i+1]+1)
如果下次掷的点数不同则相当于从1开始掷,因此为(5/6)*(dp[1]+1)
化简上式(1)可得：
dp[i] = (1/6)*(dp[i+1]) + (5/6)*(dp[1]) + 1------------------------------(2)
dp[i+1] = (1/6)*(dp[i+2]) + (5/6)*(dp[1]) + 1--------------------------(3)


两式相减(3) - (2)可得：
dp[i+1] - dp[i] = (1/6)*(dp[i+2] - dp[i+1])-----------------------------(4)


令a[i] = dp[i] - dp[i+1]----------------------------------------------------(5)
则a[i+1] = dp[i+2] - dp[i+1]
则(4)式变为：a[i+1] = 6*a[i]--------------------------------------------(6)
由(2)式可知：dp[0] - dp[1] = 1,则a[0] = 1


因此a[i] = 6^i---------------------------------------------------------------(7)


dp[n-1] - dp[n] = 6^(n-1)
dp[n-2] - dp[n-1] = 6^(n-2)
...
dp[0] - dp[1] = 1
则dp[0] = dp[n] + 6^0 + 6^1 + 6^2 + ... + 6^(n-2) + 6^(n-1)-----(8)
由于dp[n] = 0,则最终我们要求的结果dp[0]：
dp[0] = (6^n - 1)/5--------------------------------------------------------(9)
即F[n] = (6^n - 1)/5------------------------------------------------------(10)
H[n] = 6*F[n] = 6*(6^n - 1)/5------------------------------------------(11)
G[m] = 6*m----------------------------------------------------------------(12)
由于题目要求使得G[m1]>=F[n] && G[m2]>=H[n]的最小整数值
则 m1 >= (6^n - 1)/30, m2>=(6^n - 1)/5
由于6^n尾数为6,因此要使得m1、m2为整数,则
m1 >= (6^n + 24)/30, m2>=(6^n - 1)/5
即求出在n的情况下上述两个表达式的值即可,
分母的情况用模n情况下的a的逆元来解决。
#include #include using namespace std; typedef long long LL; const LL MOD = 2011; LL quick_mod(LL a,LL b,LL m) { LL ans = 1; while(b) { if(b&1) { ans = (ans*a)%m; b--; } b/=2; a = a*a%m; } return ans; } int main() { //F(n) = (6^n-1)/5-----H(n) = 6*F(n)-----G(m) = 6*m; //M1 = (6^n+24)/30-----M2 = (6^n-1)/5 LL N; while(scanf("%I64d",&N) && N) { LL hehe,ans1,ans2; hehe = quick_mod(6,N,MOD); ans1 = ((hehe+24+MOD)%MOD*1944)%MOD; ans2 = ((hehe-1+MOD)%MOD*1609)%MOD; printf("%I64d %I64d ",ans1,ans2); } return 0; }