首页 > 代码库 > 2014.10.31我出的模拟赛【黑红树】

2014.10.31我出的模拟赛【黑红树】

黑红树(brtree.*)

背景

  Mz们在czy的生日送他一个黑红树种子……czy种下种子,结果种子很快就长得飞快,它的枝干伸入空中看不见了……

题目描述

Czy发现黑红树具有一些独特的性质。

1、 这是二叉树,除根节点外每个节点都有红与黑之间的一种颜色。

2、 每个节点的两个儿子节点都被染成恰好一个红色一个黑色。

3、 这棵树你是望不到头的(树的深度可以到无限大)

4、 黑红树上的高度这样定义:h(根节点)=0,h[son]=h[father]+1。

Czy想从树根顺着树往上爬。他有p/q的概率到达红色的儿子节点,有1-p/q的概率到达黑色节点。但是他知道如果自己经过的路径是不平衡的,他会马上摔下来。一条红黑树上的链是不平衡的,当且仅当红色节点与黑色节点的个数之差大于1。现在他想知道他刚好在高度为h的地方摔下来的概率的精确值a/b,gcd(a,b)=0。那可能很大,所以他只要知道a,b对K取模的结果就可以了。另外,czy对输入数据加密:第i个询问Qi真正大小将是给定的Q减上一个询问的第一个值a%K.

格式

第一行四个数p,q,T,k,表示走红色节点概率是p/q,以下T组询问,答案对K取模。接下来T行,每行一个数 Q,表示czy想知道刚好在高度Q掉下来的概率(已加密)

输出T行,每行两个整数,表示要求的概率a/ba%K和b%K的精确值。如果这个概率就是01,直接输出0 01 1(中间有空格)。

样例输入1     样例输入2

2 3 2 100    2 3 2 20

1                4

2                6

样例输出1     样例输出2

0 0             0 1

5 9             0 9

 

数据范围

对于30%数据,p,q<=5,T<=1000,K<=127,对于任意解密后的Q,有Q<=30

对于60%数据,p,q<=20,T<=100000,K<=65535,对于任意解密后的Q,Q<=1000

对于100%数据,p,q<=100,T<=1000000, K<=1000000007,对于任意解密后的Q,Q<=1000000

对于100%数据,q>p,0<= p/q<=1

 

其实是和我以前出的一题很像,大致是一样的

 

考虑把树两层两层分开,那么每层之间是互不影响的

在每一层结束的概率可以算出来

至于约分,前20个搞出质因数暴力

具体去看看代码就懂了
http://www.cnblogs.com/zhber/p/4036010.html

2014.10.31我出的模拟赛【黑红树】