Asusetic
0%

2021.07.13模拟赛

发表于 分类于 Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

我最菜了/kk

T1 矩阵

试图对每一个价值计数大失败

直接考虑每一个数字的能贡献答案的概率，因为每个数字都最多只会贡献 11 的价值，直接对概率求和即答案

设 pip_i 为 i+1i+1 的概率，则 pi=pi−1×n2−n−(i−1)n2−ip_i=p_{i-1}\times\dfrac{n^2-n-(i-1)}{n^2-i}

因为前 i−1i-1 个需要不在同一列且 ii 不在这一列，递推即可

O(n)O(n)

T2 欧拉

第二部分就是上帝与集合的正确用法，主要是对 φ(i×a)\varphi(i \times a)求和

两种做法，一种是题解里比较优秀的做法，另一种是 RenaMoe 给出的不依赖于无平方因子的做法

第一种：

如果 p∣ap|a 则必然有 gcd⁡(p,ap)=1\gcd(p,\dfrac{a}{p})=1 由这个性质可以考虑分开计算

∑φ(i×a)=∑p∤iφ(i×ap)φ(p)+∑i=1⌊np⌋φ(i×a)×p\sum \varphi (i \times a) = \sum\limits_{p \nmid i} \varphi(i\times\frac{a}{p})\varphi(p)+\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i\times a) \times p

=∑p∤iφ(i×ap)φ(p)+∑i=1⌊np⌋φ(i×a)×(φ(p)+1)=\sum\limits_{p \nmid i} \varphi(i\times\frac{a}{p})\varphi(p)+\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i\times a) \times (\varphi(p)+1)

$\sum\limits_{p \nmid i} \varphi(i\times\frac{a}{p})\varphi(p)+\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i\times a) \times \varphi(p)
+\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i\times a) $

可以通过各种方式发现前两项是互补的，即 φ(p)∑φ(i×ap)\varphi(p)\sum\varphi(i\times \dfrac{a}{p})

然后直接递归算即可

第二种：
考虑 $ \varphi(i \times a) $ 展开式 $ ia\prod \frac{p_i-1}{p_i} $ 我们希望把 $ \varphi(a) $ 提出去，观察 φ(i×a)\varphi(i \times a) 展开式可以发现，如果我们把属于 aa 的部分提出去，那么剩下的是 ii 除去和 aa 共有的素因子（不计重数）

考虑构造 f(a,i)f(a,i) 表示 不计重数的 ii 与 aa 的非共有素因子，则答案为

φ(a)∑iφ(f(a,i))f(a,i)\varphi(a) \sum i \dfrac{\varphi(f(a,i))}{f(a,i)}

直接计算即可，复杂度同样 O(n)O(n)

T3 标算惨遭卡飞！随机数据惨遭暴力水过！

显然是得跑网络流，不过直接连边必然跑不过

考虑在如果给树做括号序映射到序列上，那么 l,rl,r 和 子树的限制就是平面上的一个矩形

KDT优化建图即可，复杂度 O(玄学2)O(玄学^2)

upd：复杂度似乎有点问题，原题BZOJ3681，待补

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
#include <algorithm>
#include <array>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
const int N = 4e5 + 5;
#define meow(args...) fprintf(stderr, args)
int S, T;
namespace NetworkFlow {
const int INF = 0x3f3f3f3f;
struct Graph {
    struct Node {
        int v, w, nxt;
    };
    vector<Node> edge;
    vector<int> head;
    Graph() {
    }
    Graph(int n) : head(n, -1) {
    }
    void resize(int n) {
        head.resize(n);
        head.assign(n, -1);
    }
    void add(int u, int v, int w) {
        edge.emplace_back(Node{v, w, head[u]});
        head[u] = edge.size() - 1;
    }
    void add_flow(int u, int v, int w) {
        // meow("u:%d v:%d flow:%d\n", u, v, w);
        add(u, v, w);
        add(v, u, 0);
    }
};
int level[N];
bool bfs(int S, int T, const Graph &G) {
    memset(level, 0, sizeof(level));
    level[T] = 1;
    std::queue<int> q;
    q.push(T);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = G.head[now]; ~i; i = G.edge[i].nxt) {
            int v = G.edge[i].v;
            if (!level[v] && G.edge[i ^ 1].w) {
                level[v] = level[now] + 1;
                q.push(v);
                if (v == S) {
                    return level[S];
                }
            }
        }
    }
    return level[S];
}
vector<int> cur;
int dfs(int x, int T, int maxflow, Graph &G) {
    if (x == T) {
        return maxflow;
    }
    int res = 0;
    for (int i = cur[x]; ~i && res < maxflow; i = G.edge[i].nxt) {
        cur[x] = i;
        int v  = G.edge[i].v;
        if (G.edge[i].w && level[v] == level[x] - 1) {
            int x = dfs(v, T, std::min(G.edge[i].w, maxflow - res), G);
            if (x) {
                G.edge[i].w -= x;
                G.edge[i ^ 1].w += x;
                res += x;
            }
        }
    }
    if (res < maxflow) {
        level[x] = -1;
    }
    return res;
}
int MaxFlow(const int S, const int T, const Graph &G) {
    cur.resize(G.head.size());
    Graph tmpG = G;
    int res    = 0;
    while (bfs(S, T, tmpG)) {
        cur.assign(tmpG.head.begin(), tmpG.head.end());
        int x;
        while (x = dfs(S, T, INF, tmpG)) {
            res += x;
        }
    }
    return res;
}
} // namespace NetworkFlow
array<int, N> id, pos;
NetworkFlow::Graph G;
namespace KDT {
using NetworkFlow::INF;
struct Point {
    int p[2];
    const int &operator[](const int &x) const {
        return p[x];
    }
    int &operator[](const int &x) {
        return p[x];
    }
} p[N];
struct Rectangle {
    Point l, r;
};
struct Node {
    Rectangle range;
    Point p;
    int id;
    int ls, rs;
} tr[N];
void pushup(int x) {
    for (int i = 0; i < 2; i++) {
        tr[x].range.l[i] = tr[x].range.r[i] = tr[x].p[i];
        if (tr[x].ls) {
            tr[x].range.l[i] = min(tr[x].range.l[i], tr[tr[x].ls].range.l[i]);
            tr[x].range.r[i] = max(tr[x].range.r[i], tr[tr[x].ls].range.r[i]);
        }
        if (tr[x].rs) {
            tr[x].range.l[i] = min(tr[x].range.l[i], tr[tr[x].rs].range.l[i]);
            tr[x].range.r[i] = max(tr[x].range.r[i], tr[tr[x].rs].range.r[i]);
        }
    }
}
int tot;
void build(int rt, int l, int r, bool d) {
    id[rt] = ++tot;
    if (l == r) {
        tr[rt].range.l[0] = tr[rt].range.r[0] = p[l].p[0];
        tr[rt].range.l[1] = tr[rt].range.r[1] = p[l].p[1];
        pos[l]                                = id[rt];
        return;
    }
    const int mid = l + r >> 1;
    std::nth_element(p + l, p + mid, p + r,
                     [&](const Point &A, const Point &B) -> bool {
                         return A[d] < B[d];
                     });
    build(rt << 1, l, mid, d ^ 1);
    build(rt << 1 | 1, mid + 1, r, d ^ 1);
    G.add_flow(id[rt], id[rt << 1], INF);
    G.add_flow(id[rt], id[rt << 1 | 1], INF);
    tr[rt].ls = rt * 2;
    tr[rt].rs = rt * 2 + 1;
    for (int i = 0; i < 2; i++) {
        tr[rt].range.l[i] =
            min(tr[tr[rt].ls].range.l[i], tr[tr[rt].rs].range.l[i]);
        tr[rt].range.r[i] =
            max(tr[tr[rt].ls].range.r[i], tr[tr[rt].rs].range.r[i]);
    }
}
bool In(const Rectangle &A, const Rectangle &B) {
    return (A.l[0] <= B.l[0] && A.l[1] <= B.l[1] && A.r[0] >= B.r[0] &&
            A.r[1] >= B.r[1]);
}

bool At(const Rectangle &A, const Rectangle &B) {
    return !(A.l[0] > B.r[0] || A.r[0] < B.l[0] || A.l[1] > B.r[1] ||
             A.r[1] < B.l[1]);
}
void link(int rt, const Rectangle &A, int pos) {
    if (In(A, tr[rt].range)) {
        G.add_flow(pos, id[rt], INF);
        return;
    }
    if (At(A, tr[tr[rt].ls].range)) {
        link(tr[rt].ls, A, pos);
    }
    if (At(A, tr[tr[rt].rs].range)) {
        link(tr[rt].rs, A, pos);
    }
}
} // namespace KDT
struct Graph {
    vector<int> edge[N];
    void add(int u, int v) {
        edge[u].push_back(v);
    }
} Tr;
int n, m;
array<int, N> st, ed, p;
int tim;
void dfs(int x, const Graph &G) {
    st[x]            = ++tim;
    KDT::p[tim].p[1] = p[x];
    KDT::p[tim].p[0] = tim;
    for (auto v : G.edge[x]) {
        dfs(v, G);
    }
    ed[x] = tim;
}
int root;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 2; i <= n; i++) {
        int fa;
        cin >> fa;
        Tr.add(fa, i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    dfs(1, Tr);
    G.resize(max(5 * n, 10000));
    KDT::build(1, 1, n, 0);
    S = ++KDT::tot;
    T = ++KDT::tot;
    for (int i = 1; i <= n; i++) {
        G.add_flow(pos[i], T, 1);
    }
    while (m--) {
        int l, r, d, mx;
        cin >> l >> r >> d >> mx;
        KDT::Rectangle nya;
        nya.l[1] = l;
        nya.r[1] = r;
        nya.l[0] = st[d];
        nya.r[0] = ed[d];
        ++KDT::tot;
        KDT::link(1, nya, KDT::tot);
        G.add_flow(S, KDT::tot, mx);
    }
    cout << NetworkFlow::MaxFlow(S, T, G) << endl;
    cout.flush();
}

T4 区间GCD

线段树随便搞就行，甚至能带修

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
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 80100;
typedef long long ll;
const ll mod = (ll)1 << 31;
int sum[N], len, q;
ll ans = 0;
char s[N];
namespace SegmentTree {
#define ls(x) (x * 2)
#define rs(x) (x * 2 + 1)
struct Node {
    ll g, c, d, gc, cd, gcd;
    int l, r;
} tr[N * 4];

void pushup(int rt) {
    int ls = ls(rt), rs = rs(rt);
    tr[rt].g   = tr[ls].g + tr[rs].g;
    tr[rt].c   = tr[ls].c + tr[rs].c;
    tr[rt].d   = tr[ls].d + tr[rs].d;
    tr[rt].cd  = (tr[ls].cd + tr[rs].cd + tr[ls].c * tr[rs].d) % mod;
    tr[rt].gc  = (tr[ls].gc + tr[rs].gc + tr[ls].g * tr[rs].c) % mod;
    tr[rt].gcd = (tr[ls].gcd + tr[rs].gcd + tr[ls].gc * tr[rs].d +
                  tr[ls].g * tr[rs].cd) %
                 mod;
}

void build(int rt, int l, int r) {
    if (l == r) {
        tr[rt].l = l, tr[rt].r = r;
        tr[rt].g = tr[rt].d = tr[rt].c = tr[rt].gc = tr[rt].cd = 0;
        if (s[l] == 'g')
            tr[rt].g = 1;
        if (s[l] == 'c')
            tr[rt].c = 1;
        if (s[l] == 'd')
            tr[rt].d = 1;
        return;
    }
    tr[rt].l = l, tr[rt].r = r;
    int mid = (l + r) / 2;
    build(ls(rt), l, mid);
    build(rs(rt), mid + 1, r);
    pushup(rt);
}

Node query(int rt, int l, int r) {
    int L = tr[rt].l, R = tr[rt].r, mid = (L + R) / 2;
    if (l == L && r == R) {
        return tr[rt];
    }
    if (r <= mid)
        return query(ls(rt), l, r);
    else if (l > mid)
        return query(rs(rt), l, r);
    else {
        Node ls = query(ls(rt), l, mid), rs = query(rs(rt), mid + 1, r), res;
        res.g   = ls.g + rs.g;
        res.c   = ls.c + rs.c;
        res.d   = ls.d + rs.d;
        res.cd  = (ls.cd + rs.cd + ls.c * rs.d) % mod;
        res.gc  = (ls.gc + rs.gc + ls.g * rs.c) % mod;
        res.gcd = (ls.gcd + rs.gcd + ls.gc * rs.d + ls.g * rs.cd) % mod;
        return res;
    }
}
} // namespace SegmentTree
using namespace SegmentTree;
int main() {
    cin >> (s + 1);
    len = strlen(s + 1);
    build(1, 1, len);
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << query(1, l, r).gcd % mod << endl;
    }
    return 0;
}