首页 > 代码库 > hdu4599Dice 概率dp+扩展欧几里得
hdu4599Dice 概率dp+扩展欧几里得
//给一个正常的骰子
//F[n] 为这个骰子有一个数连续出现n次的期望
//h[n] 我这个骰子连续出现n个1的期望
//g[n] 为出现n个1的期望
//求最小的m1使得G(m1)>=F[n] , 最小的m2使得G(m2) >= H(n)
//f[i] 一个数连续掷了i次,其F[n]
//非常easy得到f[i] = 1 + 1/6*f[i+1] + 5/6*f[1] f[n] = 0
//easy求得F[n] = f[0] = (6^(n+1) - 6)/5
//h[i] 1连续出了i次其连续掷n次的期望
//h[i] = 1 + 1/6*h[i+1] + 5/6*h[0] h[n] = 0;
//H[n] = h[0] = (6^n-1)/5
//g[i] 为掷了i次1 的G[n]
//g[i] = 1/6*g[i] + 5/6*g[i+1] g[n] = 0 ;
//G[n] = g[0] = 6*n
//可得m1 >= (6^n - 1)/30 , m2 >= (6^n - 1)/5
//所以m1 = (6^n - 6)/30 + 1 , m2 = (6^n - 1)/5 ;
//因为须要对求余, 所以先用扩展欧几里得求出30和5的逆元
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std ;
const int mod = 2011 ;
typedef __int64 ll ;
ll prim(ll n)
{
ll c = 1;
ll a = 6 ;
while(n)
{
if(n&1)c = (c*a)%mod ;
a = (a*a)%mod ;
n/=2 ;
}
return c ;
}
ll exgcd(ll a , ll b , ll &x , ll &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a ;
}
ll r = exgcd(b , a%b , x , y) ;
ll temp = x ;
x = y ;
y = temp - a/b*y ;
return r;
}
int main()
{
ll n ;
ll x1 , y ,x2;
exgcd(5 , mod ,x1,y) ;
exgcd(30 , mod ,x2,y) ;
while(x1<0)x1+=mod ;
while(x2<0)x2+=mod;
while(scanf("%I64d" ,&n)&&n)
{
ll m1 = (prim(n)*x1 - x1 + mod)%mod ;
ll m2 = (prim(n)*x2 - 6*x2 + 1 + mod)%mod ;
while(m2<0)m2+=mod ;
printf("%I64d %I64d\n" , m2 ,m1) ;
}
return 0 ;
}
//F[n] 为这个骰子有一个数连续出现n次的期望
//h[n] 我这个骰子连续出现n个1的期望
//g[n] 为出现n个1的期望
//求最小的m1使得G(m1)>=F[n] , 最小的m2使得G(m2) >= H(n)
//f[i] 一个数连续掷了i次,其F[n]
//非常easy得到f[i] = 1 + 1/6*f[i+1] + 5/6*f[1] f[n] = 0
//easy求得F[n] = f[0] = (6^(n+1) - 6)/5
//h[i] 1连续出了i次其连续掷n次的期望
//h[i] = 1 + 1/6*h[i+1] + 5/6*h[0] h[n] = 0;
//H[n] = h[0] = (6^n-1)/5
//g[i] 为掷了i次1 的G[n]
//g[i] = 1/6*g[i] + 5/6*g[i+1] g[n] = 0 ;
//G[n] = g[0] = 6*n
//可得m1 >= (6^n - 1)/30 , m2 >= (6^n - 1)/5
//所以m1 = (6^n - 6)/30 + 1 , m2 = (6^n - 1)/5 ;
//因为须要对求余, 所以先用扩展欧几里得求出30和5的逆元
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std ;
const int mod = 2011 ;
typedef __int64 ll ;
ll prim(ll n)
{
ll c = 1;
ll a = 6 ;
while(n)
{
if(n&1)c = (c*a)%mod ;
a = (a*a)%mod ;
n/=2 ;
}
return c ;
}
ll exgcd(ll a , ll b , ll &x , ll &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a ;
}
ll r = exgcd(b , a%b , x , y) ;
ll temp = x ;
x = y ;
y = temp - a/b*y ;
return r;
}
int main()
{
ll n ;
ll x1 , y ,x2;
exgcd(5 , mod ,x1,y) ;
exgcd(30 , mod ,x2,y) ;
while(x1<0)x1+=mod ;
while(x2<0)x2+=mod;
while(scanf("%I64d" ,&n)&&n)
{
ll m1 = (prim(n)*x1 - x1 + mod)%mod ;
ll m2 = (prim(n)*x2 - 6*x2 + 1 + mod)%mod ;
while(m2<0)m2+=mod ;
printf("%I64d %I64d\n" , m2 ,m1) ;
}
return 0 ;
}
hdu4599Dice 概率dp+扩展欧几里得
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。