黑红树

题目描述

    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/b中a%K和b%K的精确值。如果这个概率就是0或1,直接输出0 0或1 1(中间有空格)。

样例输入1

2 3 2 100
1
2

样例输出1

0 0
5 9

样例输入2

2 3 2 20
4
6

样例输出2

0 1
0 9

这道题的求解顺序应是:求值->化简->取模,不能错,错了就是见祖宗
明显的是在奇数层绝对是不会掉下来的,那么就把二层看作一层进行dp。
那么在h层刚好掉下来的概率是h-2层活下来的概率 * 连续走两次一样的概率,就是,化简一下就好了。那么对活下来的概率dp就行了,(准确来说是递推),应该好搞吧。在h层活的概率就是h-2层活的概率 * 走两次不一样的概率(ps:因为可以先红后黑,或先黑后红,所以要乘2),式子是
对活下来的概率先预处理一波,然后询问的话O(1)回答;其实活下来的概率是个等比数列,写出通项公式,对于每个询问进行快速幂运算就好了。
想说明的一点是取模之后再约分是不对的,要先把式子约分,这样可以保证算出来的答案一定是真正答案模意义下的,这道题就这个样子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
int p,q,t,k;
int dp[2][1010101],die[2],live[2];
inline int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){
x=x*10+(ch^48);
ch=getchar();
}
return x;
}
int gcd(int x,int y){
int tep;
while(y!=0){
tep=x%y;
x=y;
y=tep;
}
return x;
}
void ready(){
dp[0][0]=dp[1][0]=1;
for(int i=1;i<=500000;++i){
dp[0][i]=((long long)dp[0][i-1]*(long long)live[0])%(long long)k;
dp[1][i]=((long long)dp[1][i-1]*(long long)live[1])%(long long)k;
}
}
int main(){
p=read();q=read();t=read();k=read();
int gcd_=gcd(p,q);
p/=gcd_;q/=gcd_;
die[0]=2*p*p+q*q-2*p*q;
die[1]=q*q;
gcd_=gcd(die[0],die[1]);
die[0]/=gcd_;die[1]/=gcd_;
live[0]=p*(q-p)*2;
live[1]=q*q;
gcd_=gcd(live[0],live[1]);
live[0]/=gcd_;live[1]/=gcd_;
ready();
register int x,y=0,z;
while(t--){
x=read();
x-=y;
if((x&1)||(x<=0)){
printf("0 0\n");
y=0;
continue;
}
y=((long long)dp[0][(x>>1)-1]*die[0])%k;
z=((long long)dp[1][(x>>1)-1]*die[1])%k;
printf("%d %d\n",y,z);
}
return 0;
}

发布于

2019-10-26

更新于

2021-09-29

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...