首页 模拟赛

长链剖分 + 堆，exBSGS + exLucas，树链剖分 + 线段树

# A. 桥

加入 kk 条边相当于是选 2k2k 个点，将它们路径上的点全都删掉。

先缩边双，重新建图，然后考虑以直径的一个端点为根，进行长链剖分。

把所有的长链全都塞到一个堆里，每次从堆里选两个最大的值加到答案里即可。

相当于是把这两条链连到一起。

然后就没了。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename G> inline void write(G x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;
int n, m, q, rt;
struct node{

    int v, nxt;
}edge[N << 1];
int head[N], tot = 1;
struct Edge {int u, v;}e[N];
vector <int> G[N];

inline void add(int x, int y){
    edge[++tot] = (node){y, head[x]};
    head[x] = tot;
}
            
int dfn[N], low[N], tim;
int stk[N], Top, vis[N];
int scc[N], cnt;

inline void tarjan(int x, int pre){
    dfn[x] = low[x] = ++tim;
    stk[++Top] = x;
    for(int i = head[x], y; i; i = edge[i].nxt){
        if((i ^ 1) == pre) continue;
        if(!dfn[y = edge[i].v]) tarjan(y, i), low[x] = min(low[x], low[y]);
        else low[x] = min(low[x], dfn[y]);
    }
    if(dfn[x] == low[x]){
        int k; cnt++;
        do{
            k = stk[Top--], scc[k] = cnt;
        }while(x != k);
    }
}

int fa[N], dep[N], siz[N], son[N], mxd[N];

inline void dfs1(int x, int f){
    fa[x] = f, dep[x] = dep[f] + 1, mxd[x] = dep[x];
    for(auto y : G[x]){
        if(y == f) continue;
        dfs1(y, x), mxd[x] = max(mxd[x], mxd[y]);
        if(mxd[y] > mxd[son[x]]) son[x] = y;
    }
}

priority_queue <int> que;

inline void dfs2(int x, int topfa){
    if(x == topfa) que.push(mxd[x] - dep[fa[x]]);
    if(son[x]) dfs2(son[x], topfa);
    for(auto y : G[x])
        if(y != fa[x] && y != son[x]) dfs2(y, y);
}

signed main(){
#ifndef ONLINE_JUDGE2
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = read(), q = read();
    for(int i = 1; i <= m; ++i){
        int u = read(), v = read();
        add(u, v), add(v, u), e[i] = (Edge){u, v};
    }
    tarjan(1, 0);
    for(int i = 1; i <= m; ++i)
        if(scc[e[i].u] != scc[e[i].v])
            G[scc[e[i].u]].pb(scc[e[i].v]), G[scc[e[i].v]].pb(scc[e[i].u]);
    dfs1(1, 0);
    for(int i = 1; i <= n; ++i)
        if(dep[i] > dep[rt]) rt = i;
    memset(dep, 0, sizeof(dep));
    memset(mxd, 0, sizeof(mxd));
    memset(son, 0, sizeof(son));
    dep[0] = -1, dfs1(rt, 0);
    dep[0] = 0, dfs2(rt, rt);

    int ans = que.top(); que.pop();
    for(int i = 1; i <= q; ++i){
        write(ans), puts("");
        if(!que.empty()) ans += que.top(), que.pop();
        if(!que.empty()) ans += que.top(), que.pop();
    }
    return 0;
}

# B. 无聊的计算器

  1. 快速幂

  2. exBSGSexBSGS

  3. exLucasexLucas

没了。

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
%:pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
int n, mod, y, z;
int c[1010][1010];

inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

inline int qpow(int a, int b, int p){
    int res = 1;e--
    while(b){
        if(b & 1) res = 1ll * res * a % p;
        a = 1ll * a * a % p, b >>= 1;
    }
    return res;
}

inline int gcd(int a, int b){
    return !b ? a : gcd(b, a % b);
}
3
inline int C(int n, int m){
    for(int i = 0; i <= n; ++i) c[i][0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= min(i, m); ++j) c[i][j] = add(c[i - 1][j - 1] + c[i - 1][j]);
    return c[n][m];
}

map <int, int> vis;

inline int exgcd(int a, int b, int &x, int &y){
    if(!b) return x = 1, y = 0, a;
    int d = exgcd(b, a % b, x, y);
    int z = x;
    x = y, y = z - a / b * y;
    return d;
}

inline int BSGS(int a, int b, int p){
    int m = ceil(sqrt(p)), res = b % p;
    vis.clear();
    for(int i = 0; i <= m; ++i)
        vis[res] = i, res = res * a % p;
    int k = qpow(a, m, p), tmp = k;
    for(int i = 1; i <= m; ++i){
        if(vis[tmp]) return m * i - vis[tmp];
        tmp = tmp * k % p;
    }
    return -1;
}

inline int exBSGS(int a, int b, int p){
    // cout << a << " " << b << " " << p << endl;
    b %= p;
    if(b == 1) return 0;
    int x, y, d = exgcd(a, p, x, y);
    if(d > 1){
        if(b % d) return -1;
        exgcd(a / d, b / d, x, y);
        return exBSGS(a, b / d * x % (p / d), p / d) + 1;
    }
    return BSGS(a, b, p);
}

inline int Inv(int a, int p){
    int x, y;
    return exgcd(a, p, x, y), (x + p) % p;
}

int px[N], pk[N], fac[N];
int tot;

inline void divide(int x){
    for(int i = 2; i * i <= x; ++i){
        if(x % i == 0){
            px[++tot] = i, pk[tot] = 1, fac[tot] = 1;
            while(x % i == 0) pk[tot] *= i, x /= i;
            for(int j = 1; j <= pk[tot]; ++j)
                if(j % i) fac[tot] = fac[tot] * j % pk[tot];
        }
    }
    if(x > 1){
        px[++tot] = x, pk[tot] = x, fac[tot] = 1;
        for(int j = 1; j <= x; ++j)
            if(j % x) fac[tot] = fac[tot] * j % x;
    }
    // cout << tot << endl;
    // for(int i = 1; i <= tot; ++i) cout << px[i] << " " << pk[i] << " " << fac[i] << endl;
}

inline int F(int n, int p, int k, int id){
    if(!n) return 1;
    int res = fac[id], tmp = 1;
    res = qpow(res, n / k, k);
    for(int i = k * (n / k); i <= n; ++i)   
        if(i % p) tmp = tmp * (i % k) % k;
    return F(n / p, p, k, id) * res % k * tmp % k;
}

inline int G(int n, int p){
    return n < p ? 0 : G(n / p, p) + (n / p);
}

inline int calc(int n, int m, int p, int k, int id){
    int fz = F(n, p, k, id), fm1 = Inv(F(m, p, k, id), k), fm2 = Inv(F(n - m, p, k, id), k);
    int mi = qpow(p, G(n, p) - G(m, p) - G(n - m, p), k);
    return fz * fm1 % k * fm2 % k * mi % k;
}

int a[N], b[N];

inline int exlucas(int n, int m, int p){
    int cnt = 0, ans = 0;
    for(int i = 1; i <= tot; ++i)
        a[++cnt] = pk[i], b[cnt] = calc(n, m, px[i], pk[i], i);
    for(int i = 1; i <= cnt; ++i){
        int M = p / a[i], T = Inv(M, a[i]);
        ans = (ans + b[i] * M % p * T % p) % p;
    }
    return ans;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read();
    while(n--){
        int op = read(); y = read(), z = read(), mod = read();
        if(op == 1) write(qpow(y, z, mod)), puts("");
        if(op == 2){
            if(z == 1) {puts("0"); continue;}
            if(y <= 1000 && z <= 1000){
                y %= mod;
                int x = 1, t = y;
                while(y != z && x <= 1000){
                    x++, y = y * t % mod;
                }
                if(x <= 1000) write(x), puts("");
                else puts("Math Error");
            }else{
                int res = exBSGS(y, z, mod);
                if(res == -1) puts("Math Error");
                else write(res), puts("");
            }
        }
        if(op == 3) tot = 0, divide(mod), write(exlucas(z, y, mod)), puts("");
    }
    cerr << clock() << endl;
    return 0;
}

# C. 消息传递

题面略微毒瘤。

看懂题意后就已经做完 90%90\% 了。

首先按 xi+tix_i + t_i 从小到大排序，这样后面的询问就不会影响前面的了。

然后考虑维护每个点处于“等待接收消息”状态结束的时间。

对于一条消息从下到上传递的链，脸上每个点“等待接收消息”状态结束的时间是一个公差为 2 的等差序列（可以手模一下）。

然后树剖线段树维护等差序列即可。

至于如何查询答案。

考虑二分当前点到根节点之间的位置，找到第一个结束等待时间大于当前消息到达时间的点。

然后当前消息就会从这个点返回，加上相应的贡献即可。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;
const int inf = 2e9;
int n, m;
int fa[N][20], lg[N];
vector <int> G[N];

int dep[N], siz[N], son[N];

inline void dfs1(int x){
    dep[x] = dep[fa[x][0]] + 1, siz[x] = 1;
    for(int i = 1; i <= 19; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for(auto y : G[x]){
        dfs1(y), siz[x] += siz[y];
        if(siz[y] > siz[son[x]]) son[x] = y;
    }
}

int top[N], dfn[N], tim;

inline void dfs2(int x, int topfa){
    top[x] = topfa, dfn[x] = ++tim;
    if(son[x]) dfs2(son[x], topfa);
    for(auto y : G[x])
        if(y != fa[x][0] && y != son[x]) dfs2(y, y);
}

#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)

int mx[N << 2], tag[N << 2], D[N << 2];

inline void pushup(int rt){
    mx[rt] = max(mx[ls], mx[rs]);
}

inline void pushtag(int t, int d, int l, int r, int rt){
    tag[rt] = t, D[rt] = d, mx[rt] = t + (r - l) * d;
}

inline void pushdown(int l, int r, int rt){
    if(!tag[rt] && !D[rt]) return;
    pushtag(tag[rt], D[rt], l, mid, ls);
    pushtag(tag[rt] + (mid - l + 1) * D[rt], D[rt], mid + 1, r, rs);
    tag[rt] = D[rt] = 0;
}

void update(int L, int R, int t, int d, int l = 1, int r = n, int rt = 1)
{
    if(l == L && r == R) return pushtag(t, d, l, r, rt);
    pushdown(l, r, rt);
    if(R <= mid) update(L, R, t, d, l, mid, ls);
    else if(L > mid) update(L, R, t, d, mid + 1, r, rs);
    else update(L, mid, t, d, l, mid, ls), update(mid + 1, R, t + (mid - L + 1) * d, d, mid + 1, r, rs);
    return pushup(rt);
}

int query(int L, int R, int l = 1, int r = n, int rt = 1)
{
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return mx[rt];
    pushdown(l, r, rt);
    return max(query(L, R, l, mid, ls), query(L, R, mid + 1, r, rs));
}
struct node{
    int x, t, id;
    inline bool operator < (const node &b) const{
        if(t + dep[x] == b.t + dep[b.x]) return x < b.x;
        else return t + dep[x] < b.t + dep[b.x];
    }
}a[N];
int ans[N];

inline void solve(int i){
    int x = a[i].x, tmp = a[i].t + dep[a[i].x];
    while(query(dfn[top[x]], dfn[x]) <= tmp) x = fa[top[x]][0];
    for(int j = lg[dep[x]]; j >= 0; --j)
        if(dep[fa[x][j]] >= dep[top[x]])
            if(query(dfn[fa[x][j]], dfn[x]) <= tmp) x = fa[x][j];
    if(query(dfn[x], dfn[x]) <= tmp) x = fa[x][0];
    ans[a[i].id] = a[i].t + (dep[a[i].x] - dep[x]) * 2;
    int y = a[i].x;
    while(top[x] != top[y])
        update(dfn[top[y]], dfn[y], tmp + 2 * (dep[top[y]] - dep[x]), 2), y = fa[top[y]][0];
    if(x != y) update(dfn[x] + 1, dfn[y], tmp + 2, 2);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read() + 1, m = read();
    for(int i = 2; i <= n; ++i)
        fa[i][0] = read() + 1, G[fa[i][0]].pb(i);
    for(int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1; 
    dfs1(1), dfs2(1, 1);
    for(int i=  1; i <= m; ++i)
        a[i] = (node){read() + 1, read(), i};
    sort(a + 1, a + 1 + m);
    update(1, 1, inf, 0);
    for(int i = 1; i <= m; ++i) solve(i);
    for(int i = 1; i <= m; ++i) write(ans[i]), putchar(' ');
    return 0;
}

更新于 阅读次数 次