「LibreOJ NOI Round 1」北校门外的回忆

发表于 | 更新于 | 分类于 ，

神仙题一道

$\Large\mathcal{Description}$

无耻地丢一个链接 $\Large{☞}$ $\Large{戳这里}$

题目内容严重超出我的表达范围

$\Large\mathcal{Solution}$

首先，有这样的结论 $:$

  • $k$ 为奇数时，$x \times 2^y$ $mod$ $k$ 成环
  • $k$ 为偶数且 $x$ 所含因子 $2$ 的个数比 $k$ 多时，$x \times 2^y$ $mod$ $k$ 成环

归纳一下就是，$x$ 所含因子 $2$ 的个数比 $k$ 多(或相等)时，$x \times 2^y$ $mod$ $k$ 成环。($k$ 为奇数时，所含因子 $2$ 的个数为 $0$) 相关证明会在最后给出。

所以，$1-n$ 每一个数都只有两种状态 $:$ 在一条链上 $or$ 不在链上

我们可以找出每一条链，并对这些链进行维护(线段树或者树状数组)。而对于不在链上的点，可以暴力跳到链上，每次最多跳 $O(log_{2}n)$ 次。

这就是本题的大体思路。

但这还没完。

我们注意到 $n$ 有 $1e9$ ，这显然不能直接维护 时间、空间两开($bao$)花($zha$)

但可以发现由于是链，所以一条链可以由一个数确定。于是我们可以倍增预处理出每个点所在的链，之后用动态开点线段树对链进行维护。

完美！时间、空间两开花！

$\Large\mathcal{Code}$

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 2e5 + 7;

int n, q, k;
int up[N], to[N][20], upt[N][20], len[N], p[N], num[N];
bool vis[N];

inline void init() {      \\预处理
    for (int i = 1; i <= k; ++i) p[i] = log2(i & (-i));
    for (int i = 1; i < k; ++i) {
        if (vis[i] || p[i] < p[k]) continue;
        int cnt = 0, tot = 0;
        num[++cnt] = i, vis[i] = true;
        int x = (i << 1); 
        if (x >= k) ++tot, x -= k;
        while (x != i) {
            num[++cnt] = x, vis[x] = true;
            x <<= 1;
            if (x >= k) ++tot, x -= k;
        }
        for (int j = 1; j <= cnt; ++j) {
            up[num[j]] = tot, len[num[j]] = cnt;
            int y = (j + cnt - 2) % cnt + 1;
            to[num[j]][0] = num[y], upt[num[j]][0] = (num[y] * 2 >= k);
        }
        for (int j = 1; j < 20; ++j)
            for (int l = 1; l <= cnt; ++l) {
                to[num[l]][j] = to[to[num[l]][j - 1]][j - 1];
                upt[num[l]][j] = upt[num[l]][j - 1] + upt[to[num[l]][j - 1]][j - 1];
            }
    }

}

inline int lowbit(int x) {
    while (!(x % k)) x /= k;
    return x % k;
}

inline int lowbitv(int x) {
    int tot = 0;
    while (!(x % k)) x /= k, ++tot;
    x %= k;
    while (tot--) x *= k;
    return x;
}

int dis;

inline int Find_Head(int x) {    \\找链首
    int tot = 0;
    while (!(x % k)) x /= k, ++tot;
    int head = x % k, cnt = (x - head) / k; dis = 1;
    dis += (cnt / up[head]) * len[head], cnt %= up[head];
    for (int i = 19; i >= 0; --i) {
        if (upt[head][i] > cnt) continue;
        cnt -= upt[head][i];
        dis += (1 << i);
        head = to[head][i];
    }
    while (tot--) head *= k;
    return head;
}

struct node {
    int ls, rs, val;
};

struct Segment_Tree {
    int rt = 0, siz = 0;
    node tre[N << 5];
    inline void update(int &p, int l, int r, int x, int y, int v) {
        if (!p) p = ++siz;
        if (x <= l && r <= y) {
            tre[p].val ^= v;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) update(tre[p].ls, l, mid, x, y, v);
        if (y > mid) update(tre[p].rs, mid + 1, r, x, y, v);
    }
    inline int query(int p, int l, int r, int x) {
        if (!p) return 0;
        if (l == r) return tre[p].val;
        int mid = (l + r) >> 1;
        if (x <= mid) return query(tre[p].ls, l, mid, x) ^ tre[p].val;
        else return query(tre[p].rs, mid + 1, r, x) ^ tre[p].val;
    }
};
Segment_Tree T1, T2, T3; //T1 : 非链  T2 : 链  T3 : 链头

signed main() {
    read(n), read(q), read(k);
    init();
    while (q--) {
        int opt, x, v;
        read(opt), read(x);
        if (opt == 1) {
            read(v);
            while (x <= n && p[lowbit(x)] < p[k]) {
                T1.update(T1.rt, 1, n, x, x, v);
                x += lowbitv(x);
            }
            if (x > n) continue;
            int head = Find_Head(x);
            T2.rt = T3.query(T3.rt, 1, n, head);
            int tmp = T2.rt; 
            T2.update(T2.rt, 1, n, dis, n, v);
            if (!tmp) T3.update(T3.rt, 1, n, head, head, T2.rt);
        }
        else {
            int ans = 0;
            while (x) {
                if (p[lowbit(x)] < p[k]) ans ^= T1.query(T1.rt, 1, n, x);
                else {
                    int head = Find_Head(x);
                    T2.rt = T3.query(T3.rt, 1, n, head);
                    if (T2.rt) ans ^= T2.query(T2.rt, 1, n, dis);
                }
                x -= lowbitv(x);
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

$\Large\mathcal{Extended}$

结论 $:$ $x$ 所含因子 $2$ 的个数比 $k$ 多(或相等)时，$x \times 2^y$ $mod$ $k$ 成环

因为 $x$ 的变化只与最后一个非零位的数值有关。所以这里讨论的 $x$ 取值为 $1 \le x \le k - 1$。

$x + lowbitv(x)$ 相当于 $x \times 2$，每一次运算 $x$ 的因子 $2$ 的个数都会多一，其他不变，所以该位不会变成零 (不会变成 $k$ 的倍数)。

有根据欧拉定理 $a^{\phi(p)}$ $\equiv$ $1$ ($mod~p$)，所以值成环。

证毕。