20221211 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

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

# A. 桥

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

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

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

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

然后就没了。

	#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. 无聊的计算器

快速幂
$exBSGS$
$exLucas$

没了。

	%: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\%$ 了。

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

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

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

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

至于如何查询答案。

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

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

	#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;
	}

# A. 桥

# B. 无聊的计算器

# C. 消息传递

20221207

20221231