type
status
date
slug
summary
tags
category
icon
password
题目描述
- 这是二叉树，除根节点外每个节点都有红与黑之间的一种颜色
- 每个节点的两个儿子节点都被染成恰好一个红色一个黑色
- 这棵树你是望不到头的（树的深度可以到无限大）
- 黑红树上的高度这样定义：，
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 10012
样例输出1
0 05 9
样例输入2
2 3 2 2046
样例输出2
0 10 9
这道题的求解顺序应是：求值->化简->取模，不能错，错了就是见祖宗
明显的是在奇数层绝对是不会掉下来的，那么就把二层看作一层进行dp
那么在h层刚好掉下来的概率是h-2层活下来的概率 * 连续走两次一样的概率，就是 ，化简一下就好了，那么对活下来的概率dp就行了，（准确来说是递推），应该好搞吧。在h层活的概率就是 层活的概率 走两次不一样的概率（ps：因为可以先红后黑，或先黑后红，所以要乘 ），式子是
对活下来的概率先预处理一波，然后询问的话 回答；其实活下来的概率是个等比数列，写出通项公式，对于每个询问进行快速幂运算就好了。
想说明的一点是取模之后再约分是不对的，要先把式子约分，这样可以保证算出来的答案一定是真正答案模意义下的，这道题就这个样子。