2022 HDU 多校 Round 5 (HDU 7185-7196) 训练记录

A. Pandaemonium Asphodelos: The First Circle (Savage)

用一个 map 维护一下相同 attribute 的极长段对整个区间的划分，单独记录每个 attribute 的基础权值，用一个线段树维护每个位置相对基础权值的偏差。

在执行修改 attribute 的操作时，注意对线段树上对应区间进行更新即可。

由于不同的区间个数是 $O(q)$ 的，因此总时间复杂度是 $O(q \log q \log n)$。

  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
140
141
142
143
#include <bits/stdc++.h>
using namespace std;

using LL = long long;

struct segTree {
    shared_ptr<segTree> lson, rson;
    LL tag;

    segTree() : tag(0) {};

    void update(int l, int r, LL val, int L, int R) {
        if(l <= L && R <= r) {
            tag += val;
            return;
        }
        int mid = (L + R) / 2;
        if(l <= mid) {
            if(!lson) lson = make_shared<segTree>();
            lson->update(l, r, val, L, mid);
        }
        if(r > mid) {
            if(!rson) rson = make_shared<segTree>();
            rson->update(l, r, val, mid + 1, R);
        }
    }

    LL query(int pos, int L, int R) {
        LL ans = tag;
        if(L != R) {
            int mid = (L + R) / 2;
            if(pos <= mid && lson) {
                ans += lson->query(pos, L, mid);
            }
            if(pos > mid && rson) {
                ans += rson->query(pos, mid + 1, R);
            }
        }
        return ans;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;

    int attr_id = 0, last = 0;
    map<int, pair<int, int>> LR {{0, {0, -1}}, {n, {1, 0}}, {n + 1, {n + 1, -1}}};

    function<int(int)> get_attr = [&] (int x) {
        return LR.lower_bound(x)->second.second;
    };

    vector<LL> value {0};
    shared_ptr<segTree> root = make_shared<segTree>();

    while(q--) {
        int op;
        cin >> op;
        if(op == 1) {
            int x, c;
            cin >> x >> c;
            x = ((x - 1) ^ last) % n + 1;
            c = ((c - 1) ^ last) % ((n - 1) / 2) + 1;
            
            x = max(x, c + 1);
            x = min(x, n - c);
            int l = x - c, r = x + c;

            pair<int, pair<int, int>> tmp;
            for(auto it = LR.lower_bound(l); it->second.first <= r; it++) {
                int ll = it->second.first, rr = it->first;
                if(ll < l) {
                    tmp = {l - 1, make_pair(ll, it->second.second)};
                    ll = l;
                }
                if(rr > r) {
                    it->second.first = r + 1;
                    rr = r;
                }
                root->update(ll, rr, value[it->second.second], 1, n);
            }

            LR.erase(LR.lower_bound(l), LR.upper_bound(r));
            if(tmp.first) {
                LR.insert(tmp);
            }

            LR[r] = {l, ++attr_id};
            value.push_back(0);
        } else if(op == 2) {
            int x, y;
            cin >> x >> y;
            x = ((x - 1) ^ last) % n + 1;
            y = ((y - 1) ^ last) % n + 1;

            auto it = LR.lower_bound(y);
            int l = it->second.first, r = it->first;
            int attr_x = get_attr(x), attr_y = it->second.second;
            root->update(l, r, value[attr_y] - value[attr_x], 1, n);
            it->second.second = attr_x;

            // merge segment with same attr
            vector<int> del_key;
            if(prev(it)->second.second == attr_x) {
                it->second.first = prev(it)->second.first;
                del_key.push_back(prev(it)->first);
            }
            if(next(it)->second.second == attr_x) {
                next(it)->second.first = it->second.first;
                del_key.push_back(it->first);
            }
            for(int key : del_key) {
                LR.erase(key);
            }
        } else if(op == 3) {
            int x, v;
            cin >> x >> v;
            x = ((x - 1) ^ last) % n + 1;
            value[get_attr(x)] += v;
        } else {
            int x;
            cin >> x;
            x = ((x - 1) ^ last) % n + 1;
            LL ans = root->query(x, 1, n) + value[get_attr(x)];
            cout << ans << "\n";
            last = ans & 0x3FFFFFFF;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--) {
        solve();
    }

    return 0;
}

B. Jo loves counting

不妨设 $n$ 分解素因子的结果是 $\prod p_i^{k_i}$，不难推出 $f(n) = \dfrac{n}{\prod k_i}$，而这显然是一个积性函数。

对于积性函数求和，我们往往会构造另一个积性函数 $g$ 使得其 Dirichlet 卷积 $f * g$ 好求和，然后通过记忆化搜索在 $O(n^{2/3})$ 时间内求得 $f$ 的前 $n$ 项和。但这一时间代价稍微有些高，大概率过不了。

题目期望的做法是把 $f$ 表示成卷积 $f = g * h$，这样有 $$ \sum_{i = 1}^{n} f(i) = \sum_{st \leq n} g(s)h(t) = \sum_{s = 1}^{n} g(s) \sum_{t = 1}^{n/s} h(t) $$ 如果 $g$ 和 $h$ 都可以 $O(1)$ 求出前缀和的话上式的时间效率是 $O(\sqrt{n})$。

可以取 $h(n) = n$，不难推出 $g$ 只在所有 $k_i \neq 1$ 的点处取值非零，显然这样的数只有 $O(\sqrt{n})$ 个，因此直接暴力预处理出 $g$ 在所有点处的取值即可。

 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
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
using LLL = __int128_t;
const LL mod = 4179340454199820289;
const int MX = 1000000, MXLG = 45;

vector<int> primes;
int d[MX + 5];
LL F[MXLG], Finv[MXLG];
vector<pair<LL, LL>> G;

void dfs(size_t id, LL x, LL val) {
    static const LL MXVAL = 1000000000000;
    if(id == primes.size() || x * primes[id] > MXVAL || x * primes[id] * primes[id] > MXVAL) {
        G.emplace_back(x, (LLL)x * val % mod);
        return;
    }
    LL cur = x;
    for(int i = 0; cur <= MXVAL; i++, cur *= primes[id]) {
        if(i == 1) {
            continue;
        }
        dfs(id + 1, cur, (LLL)val * Finv[i] % mod);
    }
}

LLL get_inv(LL u) {
    return u == 1 ? 1 : (mod - mod / u) * get_inv(mod % u) % mod;
}

int main() {
    F[0] = 1, F[1] = 1;
    for(int i = 2; i < MXLG; i++) {
        F[i] = LLL(mod - mod / i) * F[mod % i] % mod;
    }

    Finv[0] = 1;
    for(int i = 2; i < MXLG; i++) {
        LLL tmp = accumulate(Finv, Finv + i, (LLL)0);
        Finv[i] = (F[i] + mod - tmp % mod) % mod;
    }

    for(int i = 2; i <= MX; i++) {
        if(!d[i]) {
            primes.push_back(i);
            d[i] = i;
        }
        for(int pr : primes) {
            int cur = i * pr;
            if(cur > MX) {
                break;
            }
            d[cur] = pr;
            if(d[i] == pr) {
                break;
            }
        }
    }

    dfs(0, 1, 1);
    G.emplace_back(0, 0);
    sort(G.begin(), G.end());
    partial_sum(G.begin(), G.end(), G.begin(), [&] (pair<LL, LL> x, pair<LL, LL> y) {
        return make_pair(y.first, (x.second + y.second) % mod);
    });

    auto query = [&] (LL l, LL r) {
        auto i = lower_bound(G.begin(), G.end(), make_pair(l, -1LL));
        auto j = lower_bound(G.begin(), G.end(), make_pair(r + 1, -1LL));
        return (prev(j)->second + mod - prev(i)->second) % mod;
    };

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--) {
        LL n, ans = 0;
        cin >> n;
        for(LL i = 1, j; i <= n; i = j + 1) {
            LLL tmp = n / i;
            j = n / tmp;
            ans = (ans + (tmp * (tmp + 1) / 2 % mod) * query(i, j)) % mod;
        }
        cout << static_cast<LL>(get_inv(n) * ans % mod) << "\n";
    }

    return 0;
}

C. Slipper

稍微绕了个弯的签到题。考察 Dijkstra 算法的执行过程，实际上 jump 操作只会在每个深度第一次被更新到时真正起作用，特判一下即可。

G. Count Set

签到题。对于长为 $n$ 的环，选 $k$ 个互不相邻的位置的选法是 $$ \frac{n}{k} \binom{n - k - 1}{k - 1} $$ 预处理完直接乘起来即可。注意每次合并最短的两个多项式才能保证复杂度。

考场上没看到时限 8 秒，推了好久这玩意的母函数到底是什么形式。

J. Bragging Dice

结论题。只有双方手里的骰子点数均两两不同时后手胜。因为其他情况下合法的断言集合是非空且有限的，故其中字典序最大的断言唯一。

K. Kazuha’s String

这个题实际上是在判断有 $a, b, c$ 三个文字的自由群在商掉题目中给出那几个串的生成子群之后得到的商群 $G$ 中两个字符串是否等价。

20 年参加字节冬令营的时候见过这个题，当时 jls 讲评的时候提了一嘴“这玩意就是个群，上手爆搜一下就好了”，我一直感觉有什么一般性算法能直接搜出这个群的结构。

考后冷静下来想想，从群表示论的角度出发会更好做一些。

题目中前三个限制表明 $a^2 = b^3 = c^4 = 1$，考虑构造一个单同态 $G \to S_n$。$a, b, c$ 的阶限制了其循环的长度，进而限制了 $n$ 的取值。

比如我们取 $n = 6$，这样 $b$ 只可能是 $3$ 循环或两个 $3$ 循环的积。手玩一下不难得到一组可行解 $$ b = (1 \ 3 \ 5)(2 \ 4 \ 6) \qquad c = (1 \ 2 \ 6 \ 3) (4 \ 5) \qquad a = bc $$ 直接对着模拟即可。

当然如果有限群记得比较多的话可以一下看出来 $S_4 = \langle a, b | a^2 = b^3 = (ab)^4 = 1 \rangle$，然后发现 $G$ 同构于 $S_4$。

 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
#include <bits/stdc++.h>
using namespace std;

const vector<int> B {2, 3, 4, 5, 0, 1}, invB {4, 5, 0, 1, 2, 3};
const vector<int> C {1, 5, 0, 4, 3, 2}, invC {2, 0, 5, 4, 3, 1};

string solve(const string &s, const string &t) {
    vector<int> perm(6);
    iota(perm.begin(), perm.end(), 0);

    function<void(const vector<int> &)> mult = [&] (const vector<int> &p) {
        vector<int> tmp;
        for(int cur : perm) {
            tmp.push_back(p[cur]);
        }
        perm = move(tmp);
    };

    for(char c : s) {
        if(c == 'a') {  // a = bc
            mult(B), mult(C);
        } else if(c == 'b') {
            mult(B);
        } else {
            mult(C);
        }
    }

    for(char c : t) {
        if(c == 'a') {  // a^{-1} = c^{-1}b^{-1}
            mult(invC), mult(invB);
        } else if(c == 'b') {
            mult(invB);
        } else {
            mult(invC);
        }
    }

    for(size_t i = 0; i < 6; i++) {
        if(perm[i] != i) {
            return "no";
        }
    }
    return "yes";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int _;
    cin >> _;
    while(_--) {
        string s, t;
        cin >> s >> t;
        reverse(t.begin(), t.end());
        cout << solve(s, t) << "\n";
    }

    return 0;
}

FJL 三道题是队友在场内解决了的，场内也发现了 H 是一个 OI 味道十分冲的数据结构缝合题。其他题暂咕，有缘再补。