小朋友

Posted on In

题目大意：n 个小朋友在一起做游戏，第 i 个小朋友的快乐值为 Di。当第 i 个小朋友和 第 j 个小朋友一起玩时，他们能获得 Di xor Dj 的快乐值。每一个小朋友 i 都 想知道，他和谁一起玩能够获得最大的快乐值，请你帮他们每个人分别求出这个 值。

看到异或联系二进制，显然的贪心是我们按位进行操作，每一位都取与他不同的

二进制拆分之后弄到01Trie上就好

小细节：初始化时候p=1,tot=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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 2e6 + 66, mod = (1 << 24);

inline ll read()
{
    int s(0), w(1);
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void put(ll x)
{
    if (! x) putchar('0');
    if (x < 0) putchar('-'), x = -x;
    int num(0); char c[66];
    while (x) c[++ num] = x % 10 + 48, x /= 10;
    while (num) putchar(c[num --]);
    return (void)(putchar('\n'));
}

int n, m, yhm, maxv, t, pd;
int d[N], ans[N];
int ch[N][30], tot = 1;

inline int ksm(int a, int b)
{
    int ret(1);
    for (; b; b >>= 1)
    {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
    }
    return ret;
}

inline void yhm_insert(int x)
{
    int i, p(1), k;
    for (i = t; i >= 0; -- i)
    {
        k = (x & (1 << i)) ? 1 : 0;
        if (! ch[p][k]) ch[p][k] = ++ tot;
        p = ch[p][k];
    }
    return;
}


inline int yhm_query(int x)
{
    int i, p(1), k, sum(0);
    for (i = t; i >= 0; -- i)
    {
        k = (x & (1 << i)) ? 0 : 1;
        if (! ch[p][k]) p = ch[p][1 - k];
        else sum = (sum + (1 << i)) % mod, p = ch[p][k];
    }
    return sum;
}

inline void pres_dou()
{
    int K = read(), B = read(), P = read(), i;
    d[1] = P;
    for (i = 2; i <= n; ++ i) d[i] = (K * d[i - 1] + B % mod) % mod, maxv = max(maxv, d[i]);

    if (maxv == 0) return (void)(pd = 1);
    t = log(maxv) / log(2) + 1;
    t += (maxv & (1 << t)) ? 0 : -1;

    for (i = 1; i <= n; ++ i) yhm_insert(d[i]);
    return;
}

signed main()
{
    freopen("friend.in", "r", stdin), freopen("friend.out", "w", stdout);
    
    int i; n = read(); pres_dou();
    if (pd)
    {
        put(0);
        fclose(stdin), fclose(stdout);
        return 0;
    }
    for (i = 1; i <= n; ++ i) ans[i] = d[i] ? yhm_query(d[i]) : maxv;

    for (i = 1; i <= n; ++ i) yhm = (yhm + ans[i] * ksm(3, i - 1) % mod) % mod;
    put(yhm);

    fclose(stdin), fclose(stdout);
    return 0;
}