首页 > ACM题库 > HDU-杭电 > HDU 4599-Dice-数论-[解题报告]HOJ
2015
09-17

HDU 4599-Dice-数论-[解题报告]HOJ

Dice

问题描述 :

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)

输入:

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.

输出:

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.

样例输入:

1
2
0

样例输出:

1 1 
2 7

题目

对于 F(N)=1+6*F(N-1)   =>   F(N)+1/5=6(F(N-1)+1/5);  =>  F(1)=1   =>    F(N) = (6^N)/5-1/5;

对于 H(N)=6*F(N);

对于 G(N)=6*N;

我也不知道这样为什么是正确,好像正规的推导是倒着来,  F(N)=1/6 *(1+ F(N+1))+5 / 6 *(1+F(1)),F(N)=0   //(有1/6的可能一样,剩余的5/6将回归到F(1));

也就是我们要求 6*m1>= (6^N)/5-1/5,6*m2>=6*( (6^N)/5-1/5);

用逆元.

(摘自:http://hi.baidu.com/zhanggmcn/item/ef4dadceb4fb993e449416e7)

对于(a/b)%mod,如果b为a的因数,那么对于b的逆元c(b*c%mod==1)

有(a/b*1)%mod=(a/b*b*c)%mod=(a*c)%mod;

所以可以求出b的乘法逆元.

方一: 扩展欧几里得:bx+mod*y=1解出的x就是b的乘法逆元

方二:如果mod是素数,那么b的逆元为  b^(mod-2)%mod;

首先对于m2>=(6^n-1)/5,显然6^n的各位是6,减去1后,能被5整除,加上mod2011是素数,所以可以直接做.

对于m1>=(6^n-1)/30,为了整除,且m1最小,m1=(6^+24)/30;

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define mod 2011
typedef long long ll;

inline ll Pow(ll a,ll n)
{
	ll ans=1,t=a;
	while(n)
	{
		if(n%2) ans=ans*t%mod;
		n/=2;
		t=t*t%mod;
	}
	return ans;
}
ll n;
int main()
{
	while(~scanf("%I64d",&n))
	{
		ll m1,m2;
		ll ny=Pow(5,mod-2);
		m2=(Pow(6,n)-1+mod)%mod*ny%mod;

		ny=Pow(30,mod-2);
		m1=(Pow(6,n)+24)%mod*ny%mod;
		printf("%I64d %I64d\n",m1%mod,m2%mod);
	}
	//system("pause");
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/zhuhuangjian/article/details/10457003