vijos 黑红树 - NekoMio's Blog

题目描述#

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

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

这是二叉树，除根节点外每个节点都有红与黑之间的一种颜色。
每个节点的两个儿子节点都被染成恰好一个红色一个黑色。
这棵树你是望不到头的（树的深度可以到无限大）

黑红树上的高度这样定义(根节点)=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

样例输入2

2 3 2 20
4
6

样例输出#

样例输出1

0 0
5 9

样例输出2

0 1 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

题解#

不写了
主要就是两行两行的考虑

1
#include <cstdio>
2
#include <cstring>
3
int P;
4
class frac
5
{
6
  public:
7
    long long a, b;
8
    long long gcd(long long A, long long B)
9
    {
10
        return B == 0 ? A : gcd(B, A % B);
11
    }
12
    frac Update(frac s)
13
    {
14
        if (s.a == 0)
15
            return s;
16
        int GCD = s.gcd(s.a, s.b);
17
        return (frac){s.a / GCD, s.b / GCD};
18
    }
19
    frac operator*(const frac A)
20
    {
21
        return (frac){a * A.a % P, b * A.b % P};
22
    }
23
    frac operator*(const int A)
24
    {
25
        return (frac){a * A % P, b % P};
26
    }
27
};
28
frac ans[1000001];
29
// 0 b, 1 r
30
// 0 = ,1 b>r ,2,b<r
31
int main()
32
{
33
    //freopen("brtree.in", "r", stdin);
34
    //freopen("brtree.out", "w", stdout);
35
    int p, q, T;
36
    scanf("%d%d%d%d", &p, &q, &T, &P);
37
    p %= P;
38
    q %= P;
39
    frac B = (frac){q - p, q};
40
    frac R = (frac){p, q};
41
    frac BR = B * R * 2;
42
    frac BBRR = (frac){p * p + (q - p) * (q - p), q * q};
43
    BR = BR.Update(BR);
44
    BBRR = BBRR.Update(BBRR);
45
    ans[2] = BBRR;
46
    for (int i = 4; i <= 1000000; i += 2)
47
    {
48
        ans[i] = ans[i - 2] * BR;
49
    }
50
    int k = 0, r = 0;
51
    while (T--)
52
    {
53
        scanf("%d", &k);
54
        k -= r;
55
        //int Gcd = ans[k].gcd(ans[k].a, ans[k].b);
56
        r = 0;
57
        printf("%lld %lld\n", ans[k].a % P, ans[k].b % P);
58
        r = ans[k].a % P;
59
    }
60
}