题目描述
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/b中a%K和b%K的精确值。如果这个概率就是0或1，直接输出0 0或1 1（中间有空格）。
对于30%数据,p,q<=5,T<=1000,K<=127,对于任意解密后的Q，有Q<=30
对于60%数据,p,q<=20,T<=100000,K<=65535,对于任意解密后的Q,有Q<=100
对于100%数据,p,q<=100,T<=1000000, K<=1000000007,对于任意解密后的Q,有Q<=1000000
对于100%数据,有q>p,即0<= p/q<=1
稍稍研究可得，只有在偶数高度上才会掉下去，因为走到偶数边时，红点一定等于黑点，所以走到哪里都无所谓。故把树两个高度分为一层。只有走两个红或两个黑才会掉下去。初始化出生存概率，乘1000000遍，随便问。
所以问奇数高度输出0 0，问偶数：上一层活着*这一层死。
其实这不是最恶心的，要输出分数，还要约分，重点还要取模。。（搞错顺序直接死。。）
但通过吧死，活的概率都约分到最简而减少约分次数。
神犇ljm告诉我，取模后虽然值变了，但是取模意义下的精确值，并无影响。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll p,q,t,K,live[2],die[2];
ll shang[1000005],xia[1000005];
ll a=0,b=0;
ll gcd(ll x,ll y){return (x%y)==0 ? y:gcd(y,x%y);}
ll read()
{
ll sum=0,f=1;char x=getchar();
while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
while(x>='0'&&x<='9')sum=sum*10+x-'0',x=getchar();
return sum*f;
}
int main()
{
//freopen("brtree.in","r",stdin);
//freopen("brtree.out","w",stdout);
p=read();q=read();t=read();K=read();
live[0]=2*p*(q-p);live[1]=q*q;
ll l=gcd(live[0],live[1]);
live[0]/=l;live[1]/=l;
die[0]=p*p*2+q*q-2*p*q;die[1]=q*q;
l=gcd(die[0],die[1]);
die[0]/=l;die[1]/=l;
shang[0]=1;xia[0]=1;
for(int i=1;i<=500002;i++)
{
shang[i]=(shang[i-1]*live[0])%K;
xia[i]=(xia[i-1]*live[1])%K;
}
ll x;
while(t--){
x=read();
x-=a;
if(x==0||(x&1)){
printf("0 0
");
a=0;
continue;
}
else
{
x/=2;
a=(shang[x-1]*die[0])%K;
b=(xia[x-1]*die[1])%K;
printf("%lld %lld
",a%K,b%K);
}
}
}