LibreOJ 题解汇总

目录

• ##1. A + B Problem
• ##2. Hello, World!
• ##3. Copycat
• ##4. Quine
• ##7. Input Test
• ##100. 矩阵乘法
• ##101. 最大流
• ##102. 最小费用流
• ##103. 子串查找
• ##104. 普通平衡树
• ##108. 多项式乘法
• ##119. 非负权单源最短路
• ##130. 树状数组 1 ：单点修改，区间查询
• ##139. 树链剖分
• ##161. 乘法逆元 2
• ##510. 「LibreOJ NOI Round #1」北校门外的回忆
• ##546. 「LibreOJ β Round #7」网格图
• ##556. 「Antileaf's Round」咱们去烧菜吧
• ##2030. 「SDOI2016」储能表
• ##2083. 「NOI2016」优秀的拆分
• ##2085. 「NOI2016」循环之美
• ##2086. 「NOI2016」区间
• ##2131. 「NOI2015」寿司晚宴
• ##2143. 「SHOI2017」组合数问题
• ##2146. 「SHOI2017」寿司餐厅
• ##2173. 「FJOI2016」建筑师
• ##2182. 「SDOI2015」寻宝游戏
• ##2244. 「NOI2014」起床困难综合症
• ##2245. 「NOI2014」魔法森林
• ##2249. 「NOI2014」购票
• ##2305. 「NOI2017」游戏
• ##2319. 「NOIP2017」列队
• ##2484. 「CEOI2017」Palindromic Partitions
• ##2483. 「CEOI2017」Building Bridges
• ##2562. 「SDOI2018」战略游戏
• ##2567. 「APIO2016」划艇
• ##2587. 「APIO2018」铁人两项
• ##2718. 「NOI2018」归程
• ##2719. 「NOI2018」冒泡排序
• ##2721. 「NOI2018」屠龙勇士
• ##2816. 「eJOI2018」元素周期表
• ##2983. 「WC2019」数树
• ##3043. 「ZJOI2019」线段树
• ##3045. 「ZJOI2019」开关
• ##3049. 「十二省联考 2019」字符串问题
• ##3089. 「BJOI2019」奥术神杖
• ##3093. 「BJOI2019」光线
• ##3101. 「JSOI2019」精准预测
• ##3119. 「CTS2019 | CTSC2019」随机立方体
• ##3120. 「CTS2019 | CTSC2019」珍珠
• ##3153. 「JOI Open 2019」三级跳
• ##3154. 「JOI Open 2019」汇款
• ##3155. 「JOI Open 2019」病毒实验
• ##6268. 分拆数
• ##6277. 数列分块入门 1
• ##6278. 数列分块入门 2
• ##6279. 数列分块入门 3
• ##6280. 数列分块入门 4
• ##6288. 猫咪
• ##6577. 「ICPC World Finals 2019」瓷砖
• ##6578. 「ICPC World Finals 2019」美丽的桥梁
• ##6580. 「ICPC World Finals 2019」环状 DNA
• ##6581. 「ICPC World Finals 2019」断头路探测者
• ##6583. 「ICPC World Finals 2019」何以伊名始
• ##6584. 「ICPC World Finals 2019」Hobson 的火车

LibreOJ 是一个很好的 OJ，从现在（2019 年 2 月 20 日）开始我的刷题重心将从洛谷逐渐转向 LibreOJ。

这里按照编号排列列出我做过的题目的题解。

您可以通过浏览器的搜索功能找到对应题目。

有些题目的题解已经单独发布在我的博客中，此时我会标注「详细题解请见：『链接』」。

目前我 AC 但并未收录的题目：579、2133、2248、2254、2280、2538、2720、3023、3048、3052、6043、6620。

（更新时间：2019-07-07）

---

##1. A + B Problem

最初的一题。

#include <cstdio>

long long a, b;

int main() {
	scanf("%lld%lld", &a, &b);
	printf("%lld\n", a + b);
	return 0;
}

---

##2. Hello, World!

你好，世界！

#include <cstdio>

int main() {
	puts("Hello, World!");
	return 0;
}

---

##3. Copycat

人类的本质之一。

#include <cstdio>

const int MN = 1005;

int T;
char str[MN];

int main() {
	freopen("copycat.in", "r", stdin);
	freopen("copycat.out", "w", stdout);
	scanf("%d", &T);
	for (int i = 1; i <= T; ++i) {
		scanf("%s", str);
		printf("%s\n", str);
	}
	return 0;
}

---

##4. Quine

经典问题，对于可以读取文件名的语言可以“作弊”，例如下面的 python3 代码：

print open(__file__).read()

当然，若是用“不作弊”方法也是可以的，利用了 printf 的参数和 ASCII 码不会被转义的特点。

#include <cstdio>

char s[] = "#include <cstdio>%c%cchar s[] = %c%s%c;%c%cint main() {%c%cprintf(s, 10, 10, 34, s, 34, 10, 10, 10, 9, 10, 9, 10);%c%creturn 0;%c}";

int main() {
	printf(s, 10, 10, 34, s, 34, 10, 10, 10, 9, 10, 9, 10);
	return 0;
}

---

##7. Input Test

使用 scanf 和 printf 进行整数的输入输出。

#include <cstdio>

long long Ans, x;

int main() {
	for (int i = 3000000; i--; ) {
		scanf("%lld", &x);
		Ans ^= x;
	}
	printf("%lld\n", Ans);
	return 0;
}

---

##100. 矩阵乘法

矩阵的乘法规则：\(C=A\times B\) 则有 \(C_{ij}=\sum_{k=1}^{p}A_{ik}\times B_{kj}\)。

#include <cstdio>
#include <cstring>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 505;

struct Mat{
	int N, M;
	int A[MN][MN];
	Mat(int N = 0, int M = 0) : N(N), M(M) { memset(A, 0, sizeof A); }
	inline friend Mat operator *(Mat A, Mat B) {
		if (A.M != B.N) return Mat();
		int I = A.N, J = B.M, K = A.M;
		Mat C(I, J);
		for (int i = 1; i <= I; ++i) for (int j = 1; j <= J; ++j)
			for (int k = 1; k <= K; ++k)
				C.A[i][j] = (C.A[i][j] + (LL)A.A[i][k] * B.A[k][j]) % Mod;
		return C;
	}
} A, B, C;

int N, P, M;

int main() {
	scanf("%d%d%d", &N, &P, &M);
	A.N = N, A.M = B.N = P, B.M = M;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= P; ++j)
			scanf("%d", &A.A[i][j]);
	for (int i = 1; i <= P; ++i)
		for (int j = 1; j <= M; ++j)
			scanf("%d", &B.A[i][j]);
	C = A * B;
	for (int i = 1; i <= N; ++i, puts(""))
		for (int j = 1; j <= M; ++j)
			printf("%d ", (C.A[i][j] + Mod) % Mod);
	return 0;
}

---

##101. 最大流

采用带有当前弧优化和多路增广的 Dinic 算法解决最大流问题。

Dinic 算法在一般图的最坏时间复杂度为 \(\mathcal{O}(n^2m)\)。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const LL Inf = 0x7fffffffffffffff;

namespace Dinic {
const int MN = 105, MM = 5005;

int N, S, T;
int h[MN], iter[MN], nxt[MM * 2], to[MM * 2], tot; LL w[MM * 2];

inline void Init(int _N) {
	N = _N, tot = 1;
	for (int i = 1; i <= N; ++i) h[i] = 0;
}
inline void SetST(int _S, int _T) { S = _S, T = _T; }

inline void ins(int u, int v, LL x) { nxt[++tot] = h[u], to[tot] = v, w[tot] = x, h[u] = tot; }
inline void insw(int u, int v, LL w1, LL w2 = 0) {
	if (!u) u = S; if (!v) v = T;
	ins(u, v, w1), ins(v, u, w2);
}

int lv[MN], que[MN], l, r;

inline bool Lvl() {
	for (int i = 1; i <= N; ++i) lv[i] = 0;
	lv[S] = 1;
	que[l = r = 1] = S;
	while (l <= r) {
		int u = que[l++];
		for (int i = h[u]; i; i = nxt[i])
			if (w[i] && !lv[to[i]]) {
				lv[to[i]] = lv[u] + 1;
				que[++r] = to[i];
			}
	}
	return lv[T] != 0;
}

LL Flow(int u, LL f) {
	if (u == T) return f;
	LL d = 0, s = 0;
	for (int &i = iter[u]; i; i = nxt[i])
		if (w[i] && lv[to[i]] == lv[u] + 1) {
			d = Flow(to[i], std::min(f, w[i]));
			f -= d, s += d;
			w[i] -= d, w[i ^ 1] += d;
			if (!f) break;
		}
	return s;
}

inline LL Dinic() {
	LL Ans = 0;
	while (Lvl()) {
		for (int i = 1; i <= N; ++i) iter[i] = h[i];
		Ans += Flow(S, Inf);
	}
	return Ans;
}
} // namespace Dinic

int N, M, S, T;

int main() {
	scanf("%d%d%d%d", &N, &M, &S, &T);
	Dinic::Init(N), Dinic::SetST(S, T);
	for (int i = 1; i <= M; ++i) {
		int u, v; LL c;
		scanf("%d%d%lld", &u, &v, &c);
		Dinic::insw(u, v, c);
	}
	printf("%lld\n", Dinic::Dinic());
	return 0;
}

---

##102. 最小费用流

采用类似 Dinic 算法的方法，使用带队列优化的 Bellman-Ford 算法求解带有负权的最短路为节点标号。

使用带有当前弧优化和多路增广的方法进行推流，注意必须流过符合标号差等于费用的边，注意记录 vis 数组表示节点是否被访问过。

#include <cstdio>
#include <algorithm>

const int MN = 405, MM = 15005;
const int Inf = 0x7fffffff;

int N, M, S, T, Ans, Cost;
int h[MN], iter[MN], nxt[MM * 2], to[MM * 2], cap[MM * 2], cost[MM * 2], tot = 1;
inline void ins(int x, int y, int w, int z) {
	nxt[++tot] = h[x], to[tot] = y, cap[tot] = w, cost[tot] = z, h[x] = tot;
}
inline void insw(int x, int y, int w, int z) { ins(x, y, w, z), ins(y, x, 0, -z); }

int dis[MN], que[MN * MM], l, r;
bool inq[MN], vis[MN];

inline bool SPFA() {
	for (int i = 1; i <= N; ++i) dis[i] = Inf, inq[i] = 0;
	dis[S] = 0, que[l = r = 1] = S, inq[S] = 1;
	while (l <= r) {
		int u = que[l++];
		inq[u] = 0;
		for (int i = h[u]; i; i = nxt[i]) {
			if (!cap[i] || dis[to[i]] <= dis[u] + cost[i]) continue;
			dis[to[i]] = dis[u] + cost[i];
			if (!inq[to[i]]) {
				que[++r] = to[i];
				inq[to[i]] = 1;
			}
		}
	}
	return dis[T] != Inf;
}

int Flow(int u, int f) {
	if (u == T) return f;
	vis[u] = 1;
	int d, s = 0;
	for (int &i = iter[u]; i; i = nxt[i]) {
		if (vis[to[i]] || !cap[i] || dis[to[i]] != dis[u] + cost[i]) continue;
		d = Flow(to[i], std::min(f, cap[i]));
		f -= d, s += d;
		cap[i] -= d, cap[i ^ 1] += d;
		Cost += cost[i] * d;
		if (!f) break;
	}
	vis[u] = 0;
	return s;
}

inline int MCMF() {
	Ans = 0, Cost = 0;
	while (SPFA()) {
		for (int i = 1; i <= N; ++i) iter[i] = h[i];
		Ans += Flow(S, Inf);
	}
	return Ans;
}

int main() {
	scanf("%d%d", &N, &M);
	S = 1, T = N;
	for (int i = 1; i <= M; ++i) {
		int u, v, x, c;
		scanf("%d%d%d%d", &u, &v, &x, &c);
		insw(u, v, x, c);
	}
	int Ans;
	Ans = MCMF();
	printf("%d %d\n", Ans, Cost);
	return 0;
}

---

##103. 子串查找

经典的字符串匹配题，可以使用多种算法通过，这里使用 KMP 算法解决。

#include <cstdio>
#include <cstring>

const int MN = 1000005;

int N, M, Ans;
char A[MN], B[MN];
int p[MN];

int main() {
	scanf("%s%s", A + 1, B + 1);
	N = strlen(A + 1), M = strlen(B + 1);
	int k = 0;
	for (int i = 2; i <= M; ++i) {
		while (k && B[k + 1] != B[i]) k = p[k];
		if (B[k + 1] == B[i]) p[i] = ++k;
	}
	k = 0;
	for (int i = 1; i <= N; ++i) {
		while (k && B[k + 1] != A[i]) k = p[k];
		if (B[k + 1] == A[i]) ++k;
		if (k == M) ++Ans, k = p[k];
	}
	printf("%d\n", Ans);
	return 0;
}

---

##104. 普通平衡树

经典的可以使用平衡树维护的问题之一。使用无旋 Treap 解决此问题。

无旋 Treap 以分裂（Split）和合并（Merge）操作为基础，使用随机化作为复杂度保证。

优点是适用范围广，代码难度低，易可持久化。缺点是常数略微大（但是很少被卡），不能作为 Link-Cut Tree 的辅助数据结构（需使用 Splay）。

#include <cstdio>

inline unsigned ran() {
	static unsigned x = 1;
	return x ^= x << 13, x ^= x >> 17, x ^= x << 5;
}

const int MN = 100005;

int Root, val[MN], pri[MN], siz[MN], ls[MN], rs[MN], cnt;
inline int NewNode(int v) { val[++cnt] = v; pri[cnt] = ran(); siz[cnt] = 1; return cnt; }
inline void Comb(int rt) { siz[rt] = siz[ls[rt]] + siz[rs[rt]] + 1; }
int Merge(int rt1, int rt2) {
	if (!rt1 || !rt2) return rt1 + rt2;
	if (pri[rt1] > pri[rt2]) {
		rs[rt1] = Merge(rs[rt1], rt2);
		Comb(rt1);
		return rt1;
	}
	else {
		ls[rt2] = Merge(rt1, ls[rt2]);
		Comb(rt2);
		return rt2;
	}
}
void Split(int rt, int k, int &rt1, int &rt2) {
	if (!rt) { rt1 = rt2 = 0; return ; }
	if (k <= siz[ls[rt]]) {
		Split(ls[rt], k, rt1, rt2);
		ls[rt] = rt2;
		Comb(rt);
		rt2 = rt;
	}
	else {
		Split(rs[rt], k - siz[ls[rt]] - 1, rt1, rt2);
		rs[rt] = rt1;
		Comb(rt);
		rt1 = rt;
	}
}
int Rank(int rt, int x) {
	if (!rt) return 0;
	if (x <= val[rt]) return Rank(ls[rt], x);
	else return siz[ls[rt]] + 1 + Rank(rs[rt], x);
}

int N;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
		int opt, x;
		scanf("%d%d", &opt, &x);
		int rt1, rt2, rt3;
		if (opt == 1) {
			Split(Root, Rank(Root, x), rt1, rt2);
			Root = Merge(rt1, Merge(NewNode(x), rt2));
		}
		if (opt == 2) {
			Split(Root, Rank(Root, x), rt1, rt2);
			Split(rt2, 1, rt2, rt3);
			Root = Merge(rt1, rt3);
		}
		if (opt == 3) {
			printf("%d\n", Rank(Root, x) + 1);
		}
		if (opt == 4) {
			Split(Root, x - 1, rt1, rt2);
			Split(rt2, 1, rt2, rt3);
			printf("%d\n", val[rt2]);
			Root = Merge(rt1, Merge(rt2, rt3));
		}
		if (opt == 5) {
			Split(Root, Rank(Root, x) - 1, rt1, rt2);
			Split(rt2, 1, rt2, rt3);
			printf("%d\n", val[rt2]);
			Root = Merge(rt1, Merge(rt2, rt3));
		}
		if (opt == 6) {
			Split(Root, Rank(Root, x + 1), rt1, rt2);
			Split(rt2, 1, rt2, rt3);
			printf("%d\n", val[rt2]);
			Root = Merge(rt1, Merge(rt2, rt3));
		}
	}
	return 0;
}

---

##108. 多项式乘法

经典的序列卷积模板题，使用快速数论变换（FNTT）解决。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 998244353;
const int G = 3, iG = 332748118;
const int MS = 1 << 18;

inline LL qPow(LL b, int e) {
	LL a = 1;
	for (; e; e >>= 1, b = b * b % Mod)
		if (e & 1) a = a * b % Mod;
	return a;
}

int Sz, R[MS]; LL InvSz;

inline void InitFNTT(int N) {
	int Bt = 0;
	while (1 << Bt < N) ++Bt;
	if (Sz == (1 << Bt)) return ;
	Sz = 1 << Bt, InvSz = -(Mod - 1) / Sz;
	for (int i = 1; i < Sz; ++i) R[i] = R[i >> 1] >> 1 | (i & 1) << (Bt - 1);
}

inline void FNTT(LL *A, int Ty) {
	for (int i = 0; i < Sz; ++i) if (R[i] < i) std::swap(A[R[i]], A[i]);
	for (int j = 1, j2 = 2; j < Sz; j <<= 1, j2 <<= 1) {
		LL gn = qPow(~Ty ? G : iG, (Mod - 1) / j2), g, X, Y;
		for (int i = 0, k; i < Sz; i += j2) {
			for (k = 0, g = 1; k < j; ++k, g = g * gn % Mod) {
				X = A[i + k], Y = g * A[i + j + k] % Mod;
				A[i + k] = (X + Y) % Mod, A[i + j + k] = (X - Y) % Mod;
			}
		}
	}
	if (!~Ty) for (int i = 0; i < Sz; ++i) A[i] = A[i] * InvSz % Mod;
}

int N, M;
LL A[MS], B[MS];

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i <= N; ++i) scanf("%lld", &A[i]);
	for (int i = 0; i <= M; ++i) scanf("%lld", &B[i]);
	InitFNTT(N + M + 1);
	FNTT(A, 1), FNTT(B, 1);
	for (int i = 0; i < Sz; ++i) A[i] = A[i] * B[i] % Mod;
	FNTT(A, -1);
	for (int i = 0; i <= N + M; ++i) printf("%lld ", (A[i] + Mod) % Mod);
	return 0;
}

---

##119. 非负权单源最短路

使用堆优化的 Dijkstra 算法解决非负权最短路问题，复杂度 \(\mathcal{O}((n+m)\log n)\)，若使用斐波那契堆可以优化到 \(\mathcal{O}(n\log n + m)\)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

typedef long long LL;
typedef std::pair<LL, int> P;
const int MN = 2505, MM = 6205;

int N, M, S, T;
int h[MN], nxt[MM * 2], to[MM * 2], w[MM * 2], tot;
inline void ins(int x, int y, int z) {
	nxt[++tot] = h[x], to[tot] = y, w[tot] = z, h[x] = tot;
}

std::priority_queue<P, std::vector<P>, std::greater<P> > pq;
bool vis[MN]; LL dis[MN];

void Dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	dis[S] = 0, pq.push(P(0, S));
	while (!pq.empty()) {
		P p = pq.top(); pq.pop();
		int u = p.second; LL d = p.first;
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = h[u]; i; i = nxt[i]) {
			if (dis[to[i]] > d + w[i]) {
				dis[to[i]] = d + w[i];
				pq.push(P(dis[to[i]], to[i]));
			}
		}
	}
}

int main() {
	scanf("%d%d%d%d", &N, &M, &S, &T);
	for (int i = 1, x, y, z; i <= M; ++i) {
		scanf("%d%d%d", &x, &y, &z);
		ins(x, y, z), ins(y, x, z);
	}
	Dijkstra();
	printf("%lld\n", dis[T]);
	return 0;
}

---

##130. 树状数组 1 ：单点修改，区间查询

树状数组模板题，树状数组可以支持维护单点修改的前缀信息，也可以维护可减的区间信息。

#include <cstdio>

typedef long long LL;
const int MN = 1000005;

int N, Q;
LL b[MN];

inline void Add(int i, int x) { for (; i <= N; i += i & -i) b[i] += x; }
inline LL Qur(int i) { LL x = 0; for (; i; i -= i & -i) x += b[i]; return x; }

int main() {
	scanf("%d%d", &N, &Q);
	for (int i = 1, x; i <= N; ++i)
		scanf("%d", &x),
		Add(i, x);
	for (int q = 1, op, x, y; q <= Q; ++q) {
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) Add(x, y);
		else printf("%lld\n", Qur(y) - Qur(x - 1));
	}
	return 0;
}

---

##139. 树链剖分

树链剖分中的重链剖分结合 DFS 序可以做到 \(\mathcal{O}(n)\) 预处理，在 \(\mathcal{O}(\log^2 n)\) 的时间内处理一般的静态树上树链和子树的修改和询问的问题。

本题中，还涉及了换根操作，通过树链剖分可以方便地求出一个点在另一个点的哪一棵子树，从而做到伪换根。

#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long LL;
const int MN = 100005;
const int MS = 262144;

int N, Q, A[MN];
std::vector<int> G[MN];

int siz[MN], dep[MN], faz[MN], son[MN];
void DFS0(int u) {
	dep[u] = dep[faz[u]] + 1;
	siz[u] = 1;
	for (auto v : G[u]) {
		DFS0(v);
		if (siz[son[u]] < siz[v]) son[u] = v;
		siz[u] += siz[v];
	}
}

int top[MN], ldf[MN], rdf[MN], idf[MN], dfc;
void DFS1(int u, int tp) {
	ldf[u] = ++dfc;
	idf[dfc] = u;
	top[u] = tp;
	if (son[u]) DFS1(son[u], tp);
	for (auto v : G[u])
		if (v != son[u])
			DFS1(v, v);
	rdf[u] = dfc;
}

#define li (i << 1)
#define ri (i << 1 | 1)
#define mid ((l + r) >> 1)
#define ls li, l, mid
#define rs ri, mid + 1, r
int len[MS]; LL sum[MS], tag[MS];
inline void P(int i, LL x) { sum[i] += len[i] * x; tag[i] += x; }
inline void PushDown(int i) { if (tag[i]) P(li, tag[i]), P(ri, tag[i]), tag[i] = 0; }
void Build(int i, int l, int r) {
	len[i] = r - l + 1;
	if (l == r) sum[i] = A[idf[l]];
	else {
		Build(ls), Build(rs);
		sum[i] = sum[li] + sum[ri];
	}
}
void Mdf(int i, int l, int r, int a, int b, int x) {
	if (r < a || b < l) return ;
	if (a <= l && r <= b) return P(i, x);
	PushDown(i);
	Mdf(ls, a, b, x), Mdf(rs, a, b, x);
	sum[i] = sum[li] + sum[ri];
}
LL Qur(int i, int l, int r, int a, int b) {
	if (r < a || b < l) return 0ll;
	if (a <= l && r <= b) return sum[i];
	PushDown(i);
	return Qur(ls, a, b) + Qur(rs, a, b);
}

int Root;
inline void Mdf(int u, int v, int x) {
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
		Mdf(1, 1, N, ldf[top[u]], ldf[u], x);
		u = faz[top[u]];
	}
	if (dep[u] > dep[v]) std::swap(u, v);
	Mdf(1, 1, N, ldf[u], ldf[v], x);
}
inline LL Qur(int u, int v) {
	LL Sum = 0;
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
		Sum += Qur(1, 1, N, ldf[top[u]], ldf[u]);
		u = faz[top[u]];
	}
	if (dep[u] > dep[v]) std::swap(u, v);
	return Sum + Qur(1, 1, N, ldf[u], ldf[v]);
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
	for (int i = 2; i <= N; ++i) scanf("%d", &faz[i]), G[faz[i]].push_back(i);
	DFS0(1);
	DFS1(1, 1);
	Build(1, 1, N);
	Root = 1;
	scanf("%d", &Q);
	while (Q--) {
		int op, u, v, x;
		scanf("%d", &op);
		if (op == 1) scanf("%d", &Root);
		if (op == 2) scanf("%d%d%d", &u, &v, &x), Mdf(u, v, x);
		if (op == 3) {
			scanf("%d%d", &u, &x);
			if (u == Root) Mdf(1, 1, N, 1, N, x);
			else if (ldf[Root] < ldf[u] || rdf[u] < ldf[Root])
				Mdf(1, 1, N, ldf[u], rdf[u], x);
			else {
				v = Root;
				while (top[u] != top[v]) {
					v = top[v];
					if (faz[v] == u) break;
					v = faz[v];
				}
				if (faz[v] != u) v = son[u];
				Mdf(1, 1, N, 1, N, x);
				Mdf(1, 1, N, ldf[v], rdf[v], -x);
			}
		}
		if (op == 4) scanf("%d%d", &u, &v), printf("%lld\n", Qur(u, v));
		if (op == 5) {
			scanf("%d", &u);
			if (u == Root) printf("%lld\n", sum[1]);
			else if (ldf[Root] < ldf[u] || rdf[u] < ldf[Root])
				printf("%lld\n", Qur(1, 1, N, ldf[u], rdf[u]));
			else {
				v = Root;
				while (top[u] != top[v]) {
					v = top[v];
					if (faz[v] == u) break;
					v = faz[v];
				}
				if (faz[v] != u) v = son[u];
				printf("%lld\n", sum[1] - Qur(1, 1, N, ldf[v], rdf[v]));
			}
		}
	}
	return 0;
}

// 2019-04-12 23:13 ~ 23:46
// FJOI2019, rp++

---

##161. 乘法逆元 2

一个可以在 \(\mathcal{O}(n+\log m)\) 的时间和空间复杂度下离线计算 \(n\) 个数 \(a_1,a_2,\ldots,a_n\) 对 \(m\) 的逆元的方法，前提是已知 \(a_i\) 都与 \(m\) 互质。

计算 \(s_i=\prod_{j=1}^{i}a_j\pmod{m}\)，这可以通过 \(s_i=s_{i-1}\times a_i\bmod m\) 线性递推得到，边界是 \(s_0=1\bmod m\)。

计算 \(invs_i\equiv(s_i)^{-1}\pmod{m}\)，这可以通过 \(invs_{i-1}=invs_i\times a_i\bmod m\) 线性递推得到，边界是 \(invs_n\equiv(s_n)^{-1}\pmod{m}\)，可以通过扩展欧几里得算法求出，代码中写的是利用费马小定理的快速幂。

则 \((a_i)^{-1}=invs_i\times s_{i-1}\bmod m\)。

#include <cstdio>

inline int read() {
	int x = 0; char ch;
	while ((ch = getchar()) < '0' && ch > '9') ;
	while (x = x * 10 + (ch & 15), (ch = getchar()) >= '0' && ch <= '9') ;
	return x;
}

typedef long long LL;
const int MN = 5000005;
const int Mod = 1000000007, Coef = 998244353;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; b = (LL)b * b % Mod, e >>= 1)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

int N;
int A[MN], Pro[MN], iPro[MN], Ans;

int main() {
	N = read();
	for (int i = 1; i <= N; ++i) A[i] = read();
	Pro[0] = 1;
	for (int i = 1; i <= N; ++i) Pro[i] = (LL)Pro[i - 1] * A[i] % Mod;
	iPro[N] = qPow(Pro[N], Mod - 2);
	for (int i = N - 1; i >= 0; --i) iPro[i] = (LL)iPro[i + 1] * A[i + 1] % Mod;
	for (int i = 1; i <= N; ++i) Ans = ((LL)Ans * Coef + (LL)iPro[i] * Pro[i - 1]) % Mod;
	printf("%d\n", Ans);
	return 0;
}

---

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

详细题解请见：LOJ 510: 「LibreOJ NOI Round #1」北校门外的回忆。

#include <cstdio>

const int HASH = 19260817, NUMS = 10000005;
int h[HASH], nxt[NUMS], to[NUMS], tot;
inline int Hasher(int val, int typ) {
	int cyp = (val ^ val >> 1) % HASH;
	for (int i = h[cyp]; i; i = nxt[i]) if (to[i] == val) return i;
	return typ ? nxt[++tot] = h[cyp], to[tot] = val, h[cyp] = tot : 0;
}

typedef long long LL;
const int MK = 200005;

int N, K, Q, V[6], C;
inline void lowbit(int x, int &y, int &z) {
	int s = 1, t = C;
	while (t) { if (x % V[t] == 0) x /= V[t], s *= V[t]; --t; }
	y = x % K, z = y * s;
}
int ltrs[MK][30], ntrs[MK][30];
LL lsum[MK][30], nsum[MK][30];
int arr[NUMS];

int main() {
	scanf("%d%d%d", &N, &Q, &K);
	for (LL x = K; x <= N; x *= x) V[++C] = x;
	for (int i = 1; i < K; ++i) if ((i & -i) >= (K & -K))
		ltrs[i * 2 % K][0] = lsum[i * 2 % K][0] = i,
		ntrs[i][0] = i * 2 % K, nsum[i][0] = i;
	for (int j = 0; j < 29; ++j)
		for (int i = 1; i < K; ++i) if ((i & -i) >= (K & -K))
			ltrs[i][j + 1] = ltrs[ltrs[i][j]][j],
			lsum[i][j + 1] = lsum[i][j] + lsum[ltrs[i][j]][j],
			ntrs[i][j + 1] = ntrs[ntrs[i][j]][j],
			nsum[i][j + 1] = nsum[i][j] + nsum[ntrs[i][j]][j];
	for (int i = 1; i <= Q; ++i) {
		int op, x, y, z, v, d;
		scanf("%d%d", &op, &x);
		if (op == 1) {
			scanf("%d", &v);
			while (x <= N) {
				lowbit(x, y, z);
				if ((y & -y) >= (K & -K)) {
					int id = 0, X = x, Y = y, w = z / y;
					for (int j = 29; j >= 0; --j)
						if (lsum[Y][j] < X / w)
							id |= 1 << j,
							X -= lsum[Y][j] * w,
							Y = ltrs[Y][j];
					++id;
					for (int j = 0; x <= N; ++j) if (id >> j & 1) {
						arr[Hasher(x, 1)] ^= v;
						x += nsum[y][j] * w;
						y = ntrs[y][j];
						id += 1 << j;
					}
					break;
				}
				arr[Hasher(x, 1)] ^= v;
				x += z;
			}
		} else {
			int Ans = 0;
			while (x) {
				lowbit(x, y, z);
				if ((y & -y) >= (K & -K)) {
					int id = 0, X = x, Y = y, w = z / y;
					for (int j = 29; j >= 0; --j)
						if (lsum[Y][j] < X / w)
							id |= 1 << j,
							X -= lsum[Y][j] * w,
							Y = ltrs[Y][j];
					++id;
					X = x, Y = y;
					for (int j = 0; id; ++j, id >>= 1) if (id & 1) {
						if ((d = Hasher(X, 0))) Ans ^= arr[d];
						X -= lsum[Y][j] * w;
						Y = ltrs[Y][j];
					}
				} else if ((d = Hasher(x, 0))) Ans ^= arr[d];
				x -= z;
			}
			printf("%d\n", Ans);
		}
	}
	return 0;
}

---

##546. 「LibreOJ β Round #7」网格图

详细题解请见：LOJ 546: 「LibreOJ β Round #7」网格图。

#include <cstdio>
#include <algorithm>
#include <vector>

const int Inf = 0x3f3f3f3f;
const int MK = 50005, MS = 2200005;

int N, M, K, Q, Sx, Sy, cnt;
struct dot { int x, y; } obs[MK];
inline bool cmp(dot p, dot q) { return p.x == q.x ? p.y < q.y : p.x < q.x; }
int xdx[MK * 2], xdy[MK * 2], xcx, xcy;
std::vector<int> vecx[MK * 2], idx[MK * 2], vecy[MK * 2], idy[MK * 2];
int typ[MK * 6], rc[MK * 6], lb[MK * 6], rb[MK * 6];
int pjx[MK * 2], pjy[MK * 2];
inline int gIdX(int x, int y) { return idx[x][std::lower_bound(vecx[x].begin(), vecx[x].end(), y) - vecx[x].begin()]; }
inline int gIdY(int x, int y) { return idy[y][std::lower_bound(vecy[y].begin(), vecy[y].end(), x) - vecy[y].begin()]; }

void Init() {
	scanf("%d%d%d%d", &N, &M, &K, &Q);
	for (int i = 1, x, y; i <= K + 1; ++i) {
		scanf("%d%d", &x, &y);
		if (i <= K) obs[i].x = x, obs[i].y = y;
		else obs[0].x = x, obs[0].y = y;
		xdx[++xcx] = x, xdy[++xcy] = y;
		if (x > 1) xdx[++xcx] = x - 1;
		if (y > 1) xdy[++xcy] = y - 1;
	} xdx[++xcx] = N, xdy[++xcy] = M;
	std::sort(xdx + 1, xdx + xcx + 1), N = xcx = std::unique(xdx + 1, xdx + xcx + 1) - xdx - 1;
	std::sort(xdy + 1, xdy + xcy + 1), M = xcy = std::unique(xdy + 1, xdy + xcy + 1) - xdy - 1;
	for (int i = 0; i <= K; ++i) {
		obs[i].x = std::lower_bound(xdx + 1, xdx + xcx + 1, obs[i].x) - xdx;
		obs[i].y = std::lower_bound(xdy + 1, xdy + xcy + 1, obs[i].y) - xdy;
	} Sx = obs[0].x, Sy = obs[0].y;
	std::sort(obs + 1, obs + K + 1, cmp);
	for (int i = 1, x, y, p; i <= K; ++i) {
		x = obs[i].x, y = obs[i].y;
		p = vecx[x].empty() ? 0 : vecx[x].back();
		if (y - p >= 2) {
			idx[x].push_back(++cnt);
			typ[cnt] = 1, rc[cnt] = x;
			lb[cnt] = p + 1, rb[cnt] = y - 1;
		} else idx[x].push_back(0);
		p = vecy[y].empty() ? 0 : vecy[y].back();
		if (x - p >= 2) {
			idy[y].push_back(++cnt);
			typ[cnt] = 2, rc[cnt] = y;
			lb[cnt] = p + 1, rb[cnt] = x - 1;
		} else idy[y].push_back(0);
		vecx[x].push_back(y);
		vecy[y].push_back(x);
	}
	for (int i = 1, p; i <= N; ++i) {
		p = vecx[i].empty() ? 0 : vecx[i].back();
		if (p < M) {
			idx[i].push_back(++cnt);
			typ[cnt] = 1, rc[cnt] = i;
			lb[cnt] = p + 1, rb[cnt] = M;
		} else idx[i].push_back(0);
		vecx[i].push_back(M + 1);
	}
	for (int i = 1, p; i <= M; ++i) {
		p = vecy[i].empty() ? 0 : vecy[i].back();
		if (p < N) {
			idy[i].push_back(++cnt);
			typ[cnt] = 2, rc[cnt] = i;
			lb[cnt] = p + 1, rb[cnt] = N;
		} else idy[i].push_back(0);
		vecy[i].push_back(N + 1);
	}
}

#define mid ((l + r) >> 1)
int rtx[MK * 2], rty[MK * 2];
int rdx[MK], rdy[MK], rcx, rcy, nds;
int ls[MS], rs[MS];
std::vector<int> *id;
void Build(int &rt, int l, int r) {
	if (l == r) { rt = id[l][0]; return ; }
	rt = ++nds;
	Build(ls[rt], l, mid), Build(rs[rt], mid + 1, r);
}
void Mdf(int &rt, int l, int r, int p, int x) {
	if (l == r) { rt = x; return ; }
	++nds, ls[nds] = ls[rt], rs[nds] = rs[rt], rt = nds;
	if (p <= mid) Mdf(ls[rt], l, mid, p, x);
	else Mdf(rs[rt], mid + 1, r, p, x);
}

void Link() {
	nds = cnt;
	id = idy, Build(rdx[0], 1, M);
	for (int i = 1; i <= N; ++i) {
		for (auto v : vecx[i]) if (v <= M) {
			int id = idy[v][++pjx[v]];
			if (id) Mdf(rdx[rcx + 1] = rdx[rcx], 1, M, v, id), ++rcx;
		} rtx[i] = rdx[rcx];
	}
	id = idx, Build(rdy[0], 1, N);
	for (int i = 1; i <= M; ++i) {
		for (auto v : vecy[i]) if (v <= N) {
			int id = idx[v][++pjy[v]];
			if (id) Mdf(rdy[rcy + 1] = rdy[rcy], 1, N, v, id), ++rcy;
		} rty[i] = rdy[rcy];
	}
}

int vis[MS], dis[MS], que[MS * 2], ql, qr;
void Ins(int rt, int l, int r, int a, int b, int x) {
	if (!rt || r < a || b < l) return ;
	if (a <= l && r <= b) {
		if (dis[rt] > x + 1) dis[rt] = x + 1, que[++qr] = rt;
		return ;
	}
	Ins(ls[rt], l, mid, a, b, x);
	Ins(rs[rt], mid + 1, r, a, b, x);
}
void BFS() {
	for (int i = 1; i <= nds; ++i) dis[i] = Inf;
	int qwqx = gIdX(Sx, Sy), qwqy = gIdY(Sx, Sy);
	ql = MS + 1, qr = MS;
	dis[qwqx] = dis[qwqy] = 0;
	que[++qr] = qwqx, que[++qr] = qwqy;
	while (ql <= qr) {
		int u = que[ql++], d = dis[u];
		if (vis[u]) continue;
		vis[u] = 1;
		if (u <= cnt) {
			Ins((typ[u] == 1 ? rtx : rty)[rc[u]], 1, (typ[u] == 1 ? M : N), lb[u], rb[u], d);
		} else {
			if (ls[u] && dis[ls[u]] > d) dis[ls[u]] = d, que[--ql] = ls[u];
			if (rs[u] && dis[rs[u]] > d) dis[rs[u]] = d, que[--ql] = rs[u];
		}
	}
}

int main() {
	Init();
	Link();
	BFS();
	while (Q--) {
		int x, y;
		scanf("%d%d", &x, &y);
		x = std::lower_bound(xdx + 1, xdx + xcx + 1, x) - xdx;
		y = std::lower_bound(xdy + 1, xdy + xcy + 1, y) - xdy;
		int vx = gIdX(x, y), vy = gIdY(x, y);
		printf("%d\n", dis[vx] == Inf ? -1 : std::min(dis[vx], dis[vy]));
	}
	return 0;
}

---

##556. 「Antileaf's Round」咱们去烧菜吧

详细题解请见：LOJ 556: 「Antileaf's Round」咱们去烧菜吧。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 998244353;
const int G = 3, iG = 332748118;
const int MS = 1 << 18;
const int MN = 100005;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

inline int gInv(int b) { return qPow(b, Mod - 2); }

int Inv[MS], Fac[MS], iFac[MS];

inline void Init(int N) {
	Fac[0] = 1;
	for (int i = 1; i < N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;
	iFac[N - 1] = gInv(Fac[N - 1]);
	for (int i = N - 1; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;
	for (int i = 1; i < N; ++i) Inv[i] = (LL)Fac[i - 1] * iFac[i] % Mod;
}

int Sz, InvSz, R[MS];

inline int getB(int N) { int Bt = 0; while (1 << Bt < N) ++Bt; return Bt; }

inline void InitFNTT(int N) {
	int Bt = getB(N);
	if (Sz == (1 << Bt)) return ;
	Sz = 1 << Bt, InvSz = Mod - (Mod - 1) / Sz;
	for (int i = 1; i < Sz; ++i) R[i] = R[i >> 1] >> 1 | (i & 1) << (Bt - 1);
}

inline void FNTT(int *A, int Ty) {
	for (int i = 0; i < Sz; ++i) if (R[i] < i) std::swap(A[R[i]], A[i]);
	for (int j = 1, j2 = 2; j < Sz; j <<= 1, j2 <<= 1) {
		int wn = qPow(~Ty ? G : iG, (Mod - 1) / j2), w, X, Y;
		for (int i = 0, k; i < Sz; i += j2) {
			for (k = 0, w = 1; k < j; ++k, w = (LL)w * wn % Mod) {
				X = A[i + k], Y = (LL)w * A[i + j + k] % Mod;
				A[i + k] -= (A[i + k] = X + Y) >= Mod ? Mod : 0;
				A[i + j + k] += (A[i + j + k] = X - Y) < 0 ? Mod : 0;
			}
		}
	}
	if (!~Ty) for (int i = 0; i < Sz; ++i) A[i] = (LL)A[i] * InvSz % Mod;
}

inline void PolyInv(int *_A, int N, int *_B) {
	static int A[MS], B[MS], tA[MS], tB[MS];
	for (int i = 0; i < N; ++i) A[i] = _A[i];
	for (int i = N, B = getB(N); i < 1 << B; ++i) A[i] = 0;
	B[0] = gInv(A[0]);
	for (int L = 1; L < N; L <<= 1) {
		int L2 = L << 1, L4 = L << 2;
		InitFNTT(L4);
		for (int i = 0; i < L2; ++i) tA[i] = A[i];
		for (int i = L2; i < Sz; ++i) tA[i] = 0;
		for (int i = 0; i < L; ++i) tB[i] = B[i];
		for (int i = L; i < Sz; ++i) tB[i] = 0;
		FNTT(tA, 1), FNTT(tB, 1);
		for (int i = 0; i < Sz; ++i) tB[i] = tB[i] * (2 - (LL)tA[i] * tB[i] % Mod + Mod) % Mod;
		FNTT(tB, -1);
		for (int i = 0; i < L2; ++i) B[i] = tB[i];
	}
	for (int i = 0; i < N; ++i) _B[i] = B[i];
}

inline void PolyLn(int *_A, int N, int *_B) {
	static int tA[MS], tB[MS];
	for (int i = 1; i < N; ++i) tA[i - 1] = (LL)_A[i] * i % Mod;
	PolyInv(_A, N - 1, tB);
	InitFNTT(N + N - 3);
	for (int i = N - 1; i < Sz; ++i) tA[i] = 0;
	for (int i = N - 1; i < Sz; ++i) tB[i] = 0;
	FNTT(tA, 1), FNTT(tB, 1);
	for (int i = 0; i < Sz; ++i) tA[i] = (LL)tA[i] * tB[i] % Mod;
	FNTT(tA, -1);
	_B[0] = 0;
	for (int i = 1; i < N; ++i) _B[i] = (LL)tA[i - 1] * Inv[i] % Mod;
}

inline void PolyExp(int *_A, int N, int *_B) {
	static int A[MS], B[MS], tA[MS], tB[MS];
	for (int i = 0; i < N; ++i) A[i] = _A[i];
	for (int i = N, B = getB(N); i < 1 << B; ++i) A[i] = 0;
	B[0] = 1;
	for (int L = 1; L < N; L <<= 1) {
		int L2 = L << 1, L4 = L << 2;
		for (int i = L; i < L2; ++i) B[i] = 0;
		PolyLn(B, L2, tA);
		InitFNTT(L4);
		for (int i = 0; i < L2; ++i) tA[i] = (!i + A[i] - tA[i] + Mod) % Mod;
		for (int i = L2; i < Sz; ++i) tA[i] = 0;
		for (int i = 0; i < L; ++i) tB[i] = B[i];
		for (int i = L; i < Sz; ++i) tB[i] = 0;
		FNTT(tA, 1), FNTT(tB, 1);
		for (int i = 0; i < Sz; ++i) tA[i] = (LL)tA[i] * tB[i] % Mod;
		FNTT(tA, -1);
		for (int i = 0; i < L2; ++i) B[i] = tA[i];
	}
	for (int i = 0; i < N; ++i) _B[i] = B[i];
}

int N, M, buk[MN];
int A[MS], B[MS];

int main() {
	Init(MS);
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; ++i) {
		int A, B;
		scanf("%d%d", &A, &B);
		if (!A) continue;
		if (!B) B = N;
		if (A <= N) ++buk[A];
		if (B + 1 <= N / A) --buk[A * (B + 1)];
	}
	Init(MS);
	for (int i = 1; i <= N; ++i) if (buk[i]) {
		if (buk[i] < 0) buk[i] += Mod;
		for (int j = i, k = 1; j <= N; j += i, ++k)
			A[j] = (A[j] + (LL)buk[i] * Inv[k]) % Mod;
	}
	PolyExp(A, N + 1, B);
	for (int i = 1; i <= N; ++i) printf("%d\n", B[i]);
	return 0;
}

---

##2030. 「SDOI2016」储能表

比较有难度的二进制数位 DP。

答案可以表示为 \(\sum_{0\le i<n}\sum_{0\le j<m}(i\:\mathrm{xor}\:j)[(i\:\mathrm{xor}\:j)>k]-k\sum_{0\le i<n}\sum_{0\le j<m}[(i\:\mathrm{xor}\:j)>k]\)。

使用 \(\mathrm{g}[b][x=0/1][y=0/1][z=0/1]\) 表示从高到低考虑到第 \(b\) 位，\(x=0\) 表示考虑的数 \(i\) 当前小于 \(n\)，\(x=1\) 表示等于 \(n\)，\(y=0\) 表示考虑的数 \(j\) 当前小于 \(m\)，\(y=1\) 表示等于 \(m\)，\(z=0\) 表示 \((i\:\mathrm{xor}\:j)\) 当前大于 \(k\)，\(z=0\) 表示等于 \(k\)。在此条件下的 \((i\:\mathrm{xor}\:j)\) 之和。

类似可以定义 \(\mathrm{f}[b][x=0/1][y=0/1][z=0/1]\) 表示同样条件下的满足条件的个数。

则答案等于 \(\mathrm{g}[0][0][0][0]-k(\mathrm{f}[0][0][0][0])\)。

转移时枚举上一位的 \(x,y,z\)，以及 \(i,j\) 在这一位的值，由此计算出这一位的 \(x,y,z\) 进行转移，注意判断是否合法。

#include <cstdio>
#include <cstring>

typedef long long LL;
const int B = 59;

LL N, M, K; int P;
inline void A(int &x, int y) { x += y; if (x >= P) x -= P; }

int f[61][2][2][2], g[61][2][2][2];
LL DP() {
	memset(f, 0, sizeof f);
	memset(g, 0, sizeof g);
	f[B + 1][1][1][1] = 1;
	for (int i = B; ~i; --i) {
		int n = N >> i & 1;
		int m = M >> i & 1;
		int k = K >> i & 1;
		#define F(i) for (int i = 0; i < 2; ++i)
		F(ln) F(nn) if (!ln || n || !nn)
		F(lm) F(nm) if (!lm || m || !nm)
		F(lk) if (!lk || !k || (nn ^ nm)) {
			int nk = nn ^ nm;
			int nnn = ln & (n == nn), nnm = lm & (m == nm), nnk = lk & (k == nk);
			A(f[i][nnn][nnm][nnk], f[i + 1][ln][lm][lk]);
			A(g[i][nnn][nnm][nnk], (g[i + 1][ln][lm][lk] + ((nk ? 1ll : 0ll) << i) % P * f[i + 1][ln][lm][lk]) % P);
		}
	}
	return (g[0][0][0][0] - (LL)K % P * f[0][0][0][0] % P + P) % P;
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld%lld%d", &N, &M, &K, &P);
		printf("%lld\n", DP());
	}
	return 0;
}

---

##2083. 「NOI2016」优秀的拆分

参考自 AcFunction 的博客。

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MN = 30005;

struct SA {
	char Str[MN];
	int N, SA[MN], rk[MN], SA2[MN];
	int Sig, Buk[MN], Tmp[MN];
	int Height[MN];
	inline void RSort() {
		for (int i = 1; i <= Sig; ++i) Buk[i] = 0;
		for (int i = 1; i <= N; ++i) ++Buk[rk[i]];
		for (int i = 1; i <= Sig; ++i) Buk[i] += Buk[i - 1];
		for (int i = N; i >= 1; --i) SA[Buk[rk[SA2[i]]]--] = SA2[i];
	}
	inline void BuildSA(int _N) {
		N = _N, Sig = 26;
		for (int i = 1; i <= N; ++i) rk[i] = Str[i] - 'a' + 1, SA2[i] = i;
		rk[N + 1] = 0, RSort();
		for (int j = 1; j < N; j <<= 1) {
			int P = 0;
			for (int i = 1; i <= j; ++i) SA2[++P] = N - j + i;
			for (int i = 1; i <= N; ++i) if (SA[i] > j) SA2[++P] = SA[i] - j;
			RSort();
			Tmp[SA[1]] = P = 1;
			for (int i = 2; i <= N; ++i) {
				if (rk[SA[i]] != rk[SA[i - 1]] || rk[SA[i] + j] != rk[SA[i - 1] + j]) ++P;
				Tmp[SA[i]] = P;
			}
			for (int i = 1; i <= N; ++i) rk[i] = Tmp[i];
			Sig = P;
			if (Sig == N) break;
		}
	}
	inline void GetHeight() {
		int k = 0;
		for (int i = 1; i <= N; ++i) {
			if (rk[i] == 1) { k = Height[1] = 0; continue; }
			if (k) --k;
			int j = SA[rk[i] - 1];
			while (i + k <= N && j + k <= N && Str[i + k] == Str[j + k]) ++k;
			Height[rk[i]] = k;
		}
	}

	int BLCP[MN][15], Bt;
	inline void InitST() {
		for (int i = 1; i <= N; ++i) BLCP[i][0] = Height[i];
		while (2 << Bt <= N) ++Bt;
		for (int j = 1; j <= Bt; ++j)
			for (int i = 1 << j; i <= N; ++i)
				BLCP[i][j] = std::min(BLCP[i][j - 1], BLCP[i - (1 << (j - 1))][j - 1]);
	}
	inline int LCP(int x, int y) {
		if (x == y) return N + 1;
		if (x < 1 || x > N || y < 0 || y > N) return 0;
		x = rk[x], y = rk[y];
		if (x > y) std::swap(x, y);
		int j = 31 - __builtin_clz(y - x);
		return std::min(BLCP[y][j], BLCP[x + (1 << j)][j]);
	}
} SA[2];

int N, A[MN], B[MN];

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%s", SA[0].Str + 1), N = strlen(SA[0].Str + 1);
		for (int i = 1; i <= N; ++i) SA[1].Str[i] = SA[0].Str[N - i + 1];
		SA[0].BuildSA(N), SA[0].GetHeight(), SA[0].InitST();
		SA[1].BuildSA(N), SA[1].GetHeight(), SA[1].InitST();
		for (int i = 1; i <= N; ++i) A[i] = B[i] = 0;
		for (int Len = 1; Len << 1 <= N; ++Len) {
			for (int i = Len; i + Len <= N; i += Len) {
				int lcp = std::min(SA[0].LCP(i + 1, i + Len + 1), Len - 1);
				int lcs = std::min(SA[1].LCP(N - i + 1, N - i - Len + 1), Len);
				if (lcp + lcs >= Len) {
					++B[i - lcs + 1], --B[i + lcp - Len + 2];
					++A[i - lcs + Len * 2], --A[i + lcp + Len + 1];
				}
			}
		}
		for (int i = 1; i <= N; ++i) A[i] += A[i - 1], B[i] += B[i - 1];
		long long Ans = 0;
		for (int i = 1; i < N; ++i) Ans += (long long)A[i] * B[i + 1];
		printf("%lld\n", Ans);
	}
	return 0;
}

---

##2085. 「NOI2016」循环之美

详细题解请见：LOJ 2085: 洛谷 P1587: bzoj 4652: 「NOI2016」循环之美。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>

typedef long long LL;
const int MK = 2005;
const int S = 31622;
const int MN23 = 1000005;
const int MP = 78505;
const int MD = 25;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

bool ip[MN23];
int p[MP], pc;
int mu[MN23], Smu[MN23];

inline void Init(int N) {
	mu[1] = 1;
	for (int i = 2; i <= N; ++i) {
		if (!ip[i]) p[++pc] = i, mu[i] = -1;
		for (int j = 1; j <= pc && p[j] * i <= N; ++j) {
			ip[p[j] * i] = 1;
			if (i % p[j]) mu[p[j] * i] = -mu[i];
			else break;
		}
	}
	for (int i = 1; i <= N; ++i) Smu[i] = Smu[i - 1] + mu[i];
}

int N, M, K, N23;
int A[MK], Vl[MD], cd;

std::map<int, LL> mp[MD];

LL Sum(int N, int K) {
	if (!N) return 0;
	if (K == 1 && N <= N23) return Smu[N];
	if (mp[K].count(N)) return mp[K][N];
	if (K > 1) {
		LL Ans = 0;
		for (int j = 1; j <= K; ++j)
			if (Vl[K] % Vl[j] == 0 && mu[Vl[j]])
				Ans += Sum(N / Vl[j], j);
		return mp[K][N] = Ans;
	}
	LL Ans = 1;
	for (int i = 2, j; i <= N; i = j + 1) {
		j = N / (N / i);
		Ans -= (j - i + 1) * Sum(N / i, 1);
	}
	return mp[1][N] = Ans;
}

LL Ans;

int main() {
	scanf("%d%d%d", &N, &M, &K);
	for (int i = 1; i <= K; ++i) A[i] = A[i - 1] + (gcd(i, K) == 1);
	Init(N23 = std::max((int)pow(N, 2./3), K));
	for (int i = 1; i <= K; ++i) if (K % i == 0 && (mu[i] || i == K)) Vl[++cd] = i;
	for (int i = 1, kN, kM, j; i <= N && i <= M; i = j + 1) {
		kN = N / i, kM = M / i;
		j = std::min(N / kN, M / kM);
		Ans = Ans + kN * ((LL)kM / K * A[K] + A[kM % K]) * (Sum(j, cd) - Sum(i - 1, cd));
	}
	printf("%lld\n", Ans);
	return 0;
}

---

##2086. 「NOI2016」区间

把 \(n\) 个区间按照长度排序，双指针扫描，在扫描范围内的区间加入线段树贡献。

在线段树里 check 最大值是否大于等于 \(m\)，是的话更新答案。

#include <cstdio>
#include <algorithm>

const int MN = 500005;
const int MS = 1 << 21 | 7;
const int Inf = 0x3f3f3f3f;

int N, M, Ans = Inf;
int l[MN], r[MN], len[MN], p[MN];
int D[MN * 2], C;

inline bool cmp(int i, int j) { return len[i] < len[j]; }

int Mx[MS], Tg[MS];
void Add(int i, int l, int r, int a, int b, int x) {
	if (r < a || b < l) return ;
	if (a <= l && r <= b) { Mx[i] += x, Tg[i] += x; return ; }
	Mx[i << 1] += Tg[i], Tg[i << 1] += Tg[i];
	Mx[i << 1 | 1] += Tg[i], Tg[i << 1 | 1] += Tg[i];
	Tg[i] = 0;
	int mid = (l + r) >> 1;
	Add(i << 1, l, mid, a, b, x);
	Add(i << 1 | 1, mid + 1, r, a, b, x);
	Mx[i] = std::max(Mx[i << 1], Mx[i << 1 | 1]);
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; ++i) {
		scanf("%d%d", &l[i], &r[i]), len[i] = r[i] - l[i];
		p[i] = i, D[++C] = l[i], D[++C] = r[i] + 1;
	}
	std::sort(p + 1, p + N + 1, cmp);
	std::sort(D + 1, D + C + 1);
	C = std::unique(D + 1, D + C + 1) - D - 1;
	for (int i = 1; i <= N; ++i)
		l[i] = std::lower_bound(D + 1, D + C + 1, l[i]) - D,
		r[i] = std::lower_bound(D + 1, D + C + 1, r[i] + 1) - D - 1;
	--C;
	int j = 1;
	for (int i = 1; i <= N; ++i) {
		Add(1, 1, C, l[p[i]], r[p[i]], 1);
		while (Mx[1] >= M) {
			Ans = std::min(Ans, len[p[i]] - len[p[j]]);
			Add(1, 1, C, l[p[j]], r[p[j]], -1), ++j;
		}
	}
	printf("%d\n", Ans == Inf ? -1 : Ans);
	return 0;
}

---

##2131. 「NOI2015」寿司晚宴

转化为两人选取的寿司不能有共同的质因子。

考虑到一个寿司中最多出现一个 \(\ge 23\) 的质因子：

把比 \(23\) 小的共 \(8\) 个质数在两人手中的集合作为 DP 状态，其他质数作为 DP 阶段。

如果两个寿司有着共同的 \(\ge 23\) 的质因子，则它们应该在同一阶段考虑。

同一阶段中的寿司必须只能被一个人品尝，据此可以进行转移。

若没有 \(\ge 23\) 的质因子，则这个寿司自成一个阶段。

#include <cstdio>
#include <vector>

#define F(a) for (int a = 0; a < S; ++a)

const int MN = 505, S = 256;
const int p[8] = {2, 3, 5, 7, 11, 13, 17, 19};

int N, P, mp[MN], tot;
std::vector<int> V[MN];

unsigned f[S][S], g[S][S], h[S][S], Ans;

int main() {
	scanf("%d%d", &N, &P);
	for (int i = 2; i <= N; ++i) {
		int x = i, s = 0;
		for (int j = 0; j < 8; ++j)
			while (x % p[j] == 0) x /= p[j], s |= 1 << j;
		V[x == 1 ? ++tot : mp[x] ? mp[x] : mp[x] = ++tot].push_back(s);
	}
	f[0][0] = 1;
	for (int i = 1; i <= tot; ++i) {
		F(j) F(k) g[j][k] = h[j][k] = f[j][k];
		for (auto v : V[i])
			for (int j = S - 1; ~j; --j)
				F(k) if (!(v & k))
					(g[j | v][k] += g[j][k]) %= P,
					(h[k][j | v] += h[k][j]) %= P;
		F(j) F(k) f[j][k] = (P + g[j][k] + h[j][k] - f[j][k]) % P;
	}
	F(j) F(k) (Ans += f[j][k]) %= P;
	printf("%d\n", Ans);
	return 0;
}

---

##2143. 「SHOI2017」组合数问题

记答案为 \(f(nk,r)\)，则有 \(f(n,r)\equiv f(n,r-1\bmod k)+f(n,r)\pmod{p}\)。

记 \(a_n=[f(n,0),f(n,1),\cdots,f(n,k-1)]^T\) 是一个 \(k\) 维向量。

则显然转移可以描述为矩阵的形式 \(a_{n+1}=Aa_n\)。

\(A\) 是一个循环矩阵，乘法可以表示为第一行的循环卷积的形式。

\(k\) 这么小，就没必要用 FFT 了，直接暴力卷积。

#include <cstdio>
#include <cstring>

typedef long long LL;
const int MK = 50;

int K, R, M;
LL N;

struct Seq {
	int A[MK];
	Seq() { memset(A, 0, sizeof A); }
	inline friend Seq operator *(Seq p1, Seq p2) {
		Seq A;
		for (int i = 0; i < K; ++i)
			for (int j = 0, k = i; j < K; ++j, k -= (++k >= K ? K : 0))
				A.A[k] = (A.A[k] + (LL)p1.A[i] * p2.A[j]) % M;
		return A;
	}
	inline friend Seq qPow(Seq b, LL e) {
		Seq a; a.A[0] = 1;
		for (; e; e >>= 1, b = b * b)
			if (e & 1) a = a * b;
		return a;
	}
} A, B;

int main() {
	scanf("%lld%d%d%d", &N, &M, &K, &R);
	N *= K;
	++A.A[0], ++A.A[K != 1];
	B = qPow(A, N);
	printf("%d\n", B.A[R]);
	return 0;
}

---

##2146. 「SHOI2017」寿司餐厅

详细题解请见：洛谷 P3749: LOJ 2146: [SHOI2017]寿司餐厅。

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;
const LL Inf = 0x7fffffffffffffff;

namespace DinicFlow {
	const int MN = 6060, MM = 16055;

	int N, S, T;
	int h[MN], iter[MN], nxt[MM * 2], to[MM * 2], tot = 1; LL w[MM * 2];
	inline void ins(int u, int v, LL x) { nxt[++tot] = h[u], to[tot] = v, w[tot] = x, h[u] = tot; }
	inline void insw(int u, int v, LL x) { ins(u, v, x); ins(v, u, 0); }

	int lv[MN], que[MN], l, r;

	inline bool Lvl() {
		memset(lv, 0, sizeof(lv));
		lv[S] = 1;
		que[l = r = 1] = S;
		while (l <= r) {
			int u = que[l++];
			for (int i = h[u]; i; i = nxt[i]) if (w[i] && !lv[to[i]]) {
				lv[to[i]] = lv[u] + 1;
				que[++r] = to[i];
			}
		}
		return lv[T] != 0;
	}

	LL Flow(int u, LL f) {
		if (u == T) return f;
		LL d = 0, s = 0;
		for (int &i = iter[u]; i; i = nxt[i]) if (w[i] && lv[to[i]] == lv[u] + 1) {
			d = Flow(to[i], std::min(f, w[i]));
			f -= d, s += d;
			w[i] -= d, w[i ^ 1] += d;
			if (!f) break;
		}
		return s;
	}

	inline LL Dinic() {
		LL Ans = 0;
		while (Lvl()) {
			memcpy(iter + 1, h + 1, N * sizeof(h[0]));
			Ans += Flow(S, Inf);
		}
		return Ans;
	}
}

const int MN = 105;

int N, M, A[MN], MxA;
int F[MN][MN], Id[MN][MN], cnt;
LL Ans = 0;

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]), MxA = std::max(MxA, A[i]);
	DinicFlow::S = 1, DinicFlow::T = 2;
	cnt = 2;
	for (int i = 1; i <= N; ++i) for (int j = i; j <= N; ++j) {
		scanf("%d", &F[i][j]), Id[i][j] = ++cnt;
	}
	for (int i = 1; i <= N; ++i) for (int j = i; j <= N; ++j) {
		int cost = F[i][j];
		if (i == j) {
			if (M) DinicFlow::insw(Id[i][j], cnt + A[i], Inf);
			cost -= A[i];
		}
		else {
			DinicFlow::insw(Id[i][j], Id[i + 1][j], Inf);
			DinicFlow::insw(Id[i][j], Id[i][j - 1], Inf);
		}
		if (cost > 0) DinicFlow::insw(1, Id[i][j], cost), Ans += cost;
		if (cost < 0) DinicFlow::insw(Id[i][j], 2, -cost);
	}
	if (M) for (int i = 1; i <= MxA; ++i) DinicFlow::insw(++cnt, 2, i * i);
	DinicFlow::N = cnt;
	printf("%lld\n", Ans - DinicFlow::Dinic());
	return 0;
}

---

##2173. 「FJOI2016」建筑师

详细题解请见：洛谷 P4609: [FJOI2016] 建筑师。

#include <cstdio>

typedef long long LL;
const int mod = 1000000007;

int S[50005][205], C[205][105];

void Init() {
	S[0][0] = 1;
	for (int i = 1; i <= 50000; ++i) {
		for (int j = 1; j <= i && j <= 200; ++j) {
			S[i][j] = (S[i - 1][j - 1] + (LL)(i - 1) * S[i - 1][j]) % mod;
		}
	}

	C[0][0] = 1;
	for (int i = 1; i <= 200; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= i && j <= 100; ++j)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
	}
}

int main() {
	Init();
	int T;
	scanf("%d", &T);
	while (T--) {
		int n, A, B;
		scanf("%d%d%d", &n, &A, &B);
		printf("%lld\n", (LL)S[n - 1][A + B - 2] * C[A + B - 2][A - 1] % mod);
	}
	return 0;
}

---

##2182. 「SDOI2015」寻宝游戏

详细题解请见：洛谷 P3320: bzoj 3991: LOJ 2182: [SDOI2015]寻宝游戏。

#include <cstdio>
#include <set>

typedef long long LL;
const int MN = 100005;

int N, M;
int h[MN], nxt[MN * 2], to[MN * 2], w[MN * 2], tot;
inline void ins(int x, int y, int z) {
	nxt[++tot] = h[x], to[tot] = y, w[tot] = z, h[x] = tot;
}

int dfn[MN], idf[MN], dfc;
int dep[MN], faz[MN][17];
LL dis[MN];

void DFS(int u, int fz) {
	dfn[u] = ++dfc; idf[dfc] = u; dep[u] = dep[faz[u][0] = fz] + 1;
	for (int j = 1; 1 << j < dep[u]; ++j) faz[u][j] = faz[faz[u][j - 1]][j - 1];
	for (int i = h[u]; i; i = nxt[i]) if (to[i] != fz) dis[to[i]] = dis[u] + w[i], DFS(to[i], u);
}

inline int lca(int x, int y) {
	if (dep[x] < dep[y]) std::swap(x, y);
	for (int d = dep[x] - dep[y], j = 0; d; d >>= 1, ++j)
		if (d & 1) x = faz[x][j];
	if (x == y) return x;
	for (int j = 16; ~j; --j) if (faz[x][j] != faz[y][j])
		x = faz[x][j], y = faz[y][j];
	return faz[x][0];
}

inline LL dist(int x, int y) { return dis[x] + dis[y] - 2 * dis[lca(x, y)]; }

bool vis[MN];
std::set<int> st;
std::set<int>::iterator it;
LL Ans;

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1, x, y, z; i < N; ++i) {
		scanf("%d%d%d", &x, &y, &z);
		ins(x, y, z), ins(y, x, z);
	}
	DFS(1, 0);
	for (int m = 1, x, y, z; m <= M; ++m) {
		scanf("%d", &x);
		x = dfn[x];
		if (!vis[idf[x]]) st.insert(x);
		y = idf[(it = st.lower_bound(x)) == st.begin() ? *--st.end() : *--it];
		z = idf[(it = st.upper_bound(x)) == st.end() ? *st.begin() : *it];
		if (vis[idf[x]]) st.erase(x);
		x = idf[x];
		LL d = dist(x, y) + dist(x, z) - dist(y, z);
		if (!vis[x]) vis[x] = 1, Ans += d;
		else vis[x] = 0, Ans -= d;
		printf("%lld\n", Ans);
	}
	return 0;
}

---

##2244. 「NOI2014」起床困难综合症

记录每一位的真值表，从高到低贪心。

#include<cstdio>

int N, M, Ans;
char str[5];

int main() {
	int x, a1 = 0, a2 = 0x7fffffff;
	scanf("%d%d", &N, &M);
	while (N--) {
		scanf("%s%d", str, &x);
		if (*str == 'A') a1 &= x, a2 &= x;
		if (*str == 'X') a1 ^= x, a2 ^= x;
		if (*str == 'O') a1 |= x, a2 |= x;
	}
	for (int j = 29; ~j; --j) {
		if (a1 >> j & 1) Ans |= 1 << j;
		else if (a2 >> j & 1 && M >= (1 << j)) Ans |= 1 << j, M -= 1 << j;
	}
	printf("%d", Ans);
	return 0;
}

---

##2245. 「NOI2014」魔法森林

固定一种守护精灵的数量，相当于求动态加边的最小生成树中 \(1\) 到 \(n\) 路径上的最大值。

加入一条边时若两点原来不连通直接 link 即可，否则和这条链上的边权最大值进行比较，若比它大则不加入，若比它小则删除那条边加入这条边，LCT 维护即可。

#include <cstdio>
#include <algorithm>

const int MN = 150005;
const int INF = 0x3f3f3f3f;

int c[MN][2], f[MN], s[MN], v[MN], r[MN];

#define iv inline void
#define ii inline int
#define lc c[x][0]
#define rc c[x][1]
ii nrt(int x) { return c[f[x]][0] == x || c[f[x]][1] == x; }
iv upd(int x) { s[x] = v[x] > v[s[lc]] && v[x] > v[s[rc]] ? x : v[s[lc]] > v[s[rc]] ? s[lc] : s[rc] ; }
iv rv(int x) { lc ^= rc ^= lc ^= rc, r[x] ^= 1; }
iv psd(int x) { if (r[x]) { if (lc) rv(lc); if (rc) rv(rc); r[x] = 0; } }
iv rtt(int x) {
	int y = f[x], z = f[y], d = c[y][1] == x, a = c[x][!d];
	if (nrt(y)) c[z][c[z][1] == y] = x;
	c[x][!d] = y, c[y][d] = a;
	if (a) f[a] = y;
	f[x] = z, f[y] = x;
	upd(y);
}
iv splay(int x) {
	static int st[MN], t;
	int y = x, z;
	st[t = 1] = y;
	while (nrt(y)) st[++t] = y = f[y];
	while (t) psd(st[t--]);
	while (nrt(x)) {
		y = f[x], z = f[y];
		if (nrt(y)) rtt((c[y][1] == x) ^ (c[z][1] == y) ? x : y);
		rtt(x);
	} upd(x);
}
iv acs(int x) { for (int y = 0; x; x = f[y = x]) splay(x), rc = y, upd(x); }
iv mkrt(int x) { acs(x), splay(x), rv(x); }
ii fdrt(int x) { acs(x), splay(x); while(lc) x = lc; splay(x); return x; }
iv fdpt(int x, int y) { mkrt(x), acs(y), splay(y); }
iv link(int x, int y) { mkrt(x), f[x] = y; }
iv cut(int x, int y) { mkrt(x), acs(y), splay(y), f[x] = c[y][0] = 0, upd(y); }

int N, M, S[MN], T[MN], A[MN], B[MN], P[MN], V[MN], Ans = INF;

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; ++i) v[i] = 0, s[i] = i;
	v[0] = -1;
	for (int i = 1; i <= M; ++i) scanf("%d%d%d%d", &S[i], &T[i], &A[i], &B[i]), P[i] = i;
	std::sort(&P[1], &P[M] + 1, [](int i, int j) { return A[i] < A[j]; } );
	for (int I = 1; I <= M; ++I) {
		int i = P[I], x = M + S[i], y = M + T[i];
		if (x == y) continue;
		v[i] = B[i], s[i] = i;
		mkrt(x);
		if (fdrt(y) != x) link(x, i), link(y, i);
		else {
			fdpt(x, y);
			int id = s[y];
			if (B[id] > B[i]) {
				cut(M + S[id], id), cut(M + T[id], id);
				link(x, i), link(y, i);
			}
		}
		mkrt(M + 1);
		if (fdrt(M + N) == M + 1) {
			fdpt(M + 1, M + N);
			Ans = std::min(Ans, v[s[M + N]] + A[i]);
		}
	}
	printf("%d\n", Ans == INF ? -1 : Ans);
	return 0;
}

---

##2249. 「NOI2014」购票

详细题解请见：LOJ 2249: 洛谷 P2305: 「NOI2014」购票。

#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long LL;
const int MN = 200005;
const int MS = 2100005;
const LL Inf = 0x7fffffffffffffff;

int N, faz[MN];
std::vector<int> G[MN];
LL wgh[MN], dep[MN], dis[MN], p[MN], q[MN], b[MN], len[MN];
LL stds[MN], tds;
LL f[MN], *X = dis, *Y = f;
inline double Slope(int i, int j) {
	return X[i] == X[j] ? 1e60 : (double)(Y[j] - Y[i]) / (X[j] - X[i]);
}

int stkp[MS], valp[MS], tpp[MS];
int *istk[MN], *ival[MN], *itp[MN], it[MN];
inline void Push(int id, int u) {
	int t = it[id], tp = itp[id][t], *stk = istk[id];
	while (tp > 0 && Slope(stk[tp - 1], stk[tp]) >= Slope(stk[tp], u)) --tp;
	++t, ival[id][t] = stk[itp[id][t] = ++tp], stk[tp] = u, it[id] = t;
}
inline void Pop(int id) {
	istk[id][itp[id][it[id]]] = ival[id][it[id]];
	--it[id];
}
inline int chk(int id, LL slp) {
	int t = it[id], tp = itp[id][t], *stk = istk[id];
	if (!~tp) return -1;
	int lb = 0, rb = tp - 1, x = tp, mid;
	while (lb <= rb) {
		mid = (lb + rb) >> 1;
		if (Slope(stk[mid], stk[mid + 1]) <= slp) lb = mid + 1;
		else x = mid, rb = mid - 1;
	}
	return stk[x];
}
inline void PushAll(int i, int u) { for (; i <= N; i += i & -i) Push(i, u); }
inline void PopAll(int i) { for (; i <= N; i += i & -i) Pop(i); }
inline void GetDp(int u) {
	f[u] = Inf;
	int i = std::lower_bound(stds + 1, stds + tds + 1, dis[u] - len[u]) - stds;
	for (i = N - i + 1; i; i -= i & -i) {
		int v = chk(i, p[u]);
		if (~v) f[u] = std::min(f[u], f[v] - dis[v] * p[u] + b[u]);
	}
}

void DFS(int u) {
	dep[u] = dep[faz[u]] + 1;
	dis[u] = dis[faz[u]] + wgh[u];
	stds[++tds] = dis[u];
	b[u] = dis[u] * p[u] + q[u];
	GetDp(u);
	PushAll(N - dep[u], u);
	for (auto v : G[u]) DFS(v);
	PopAll(N - dep[u]);
	--tds;
}

int main() {
	scanf("%d%*d", &N);
	istk[1] = stkp, itp[1] = tpp, ival[1] = valp, itp[1][it[1] = 0] = -1;
	for (int i = 2; i <= N; ++i) {
		int lenl = ((i - 1) & (1 - i)) + 1;
		istk[i] = istk[i - 1] + lenl;
		itp[i] = itp[i - 1] + lenl;
		ival[i] = ival[i - 1] + lenl;
		itp[i][it[i] = 0] = -1;
	}
	for (int i = 2; i <= N; ++i) {
		scanf("%d%lld%lld%lld%lld", &faz[i], &wgh[i], &p[i], &q[i], &len[i]);
		G[faz[i]].push_back(i);
	}
	PushAll(N, 1), stds[tds = 1] = 0;
	for (auto u : G[1]) DFS(u);
	for (int i = 2; i <= N; ++i) printf("%lld\n", f[i]);
	return 0;
}

---

##2305. 「NOI2017」游戏

考虑没有 x 的地图类型怎么做，每张地图有两种选择，还有限制，是典型的 2-SAT 模型。

有了 x 的限制，那就枚举每个 x 变成 a 还是 b，不用枚举变成 c 的情况，因为已经被包含了。

复杂度 \(\mathcal{O}(n2^d)\)。

在 UOJ 上要加一个计时器，不然会被卡超时。

#include <cstdio>
#include <algorithm>
#include <ctime>

const int MN = 50005;
const int MM = 100005;

int N, M, D, pos[MN], C, flag;
char str[MN]; int s[MN];
int eu[MM], ev[MM], ef[MM], eg[MM];
int h[MN * 2], to[MM * 2], nxt[MM * 2], tot;
inline void ins(int x, int y) { nxt[++tot] = h[x], to[tot] = y, h[x] = tot; }

int instk[MN * 2], stk[MN * 2], tp;
int dfn[MN * 2], low[MN * 2], dfc;
int bel[MN * 2], bcn;
void Tarjan(int u) {
	low[u] = dfn[u] = ++dfc;
	stk[++tp] = u, instk[u] = 1;
	for (int i = h[u]; i; i = nxt[i]) {
		if (!dfn[to[i]]) Tarjan(to[i]), low[u] = std::min(low[u], low[to[i]]);
		else if (instk[to[i]]) low[u] = std::min(low[u], dfn[to[i]]);
	}
	if (dfn[u] == low[u]) {
		++bcn;
		for (int x = 0; x != u; --tp) {
			bel[x = stk[tp]] = bcn;
			instk[x] = 0;
		}
	}
}

int Ans[MN];
inline void Go() {
	for (int i = 1; i <= N * 2; ++i) h[i] = 0;
	tot = 0;
	for (int i = 1; i <= M; ++i) {
		int u = eu[i], v = ev[i], f = ef[i], g = eg[i];
		int u1 = u * 2 - 1, u2 = u * 2;
		int v1 = v * 2 - 1, v2 = v * 2;
		if (s[u] == f) continue;
		else if (s[v] == g) {
			if ((s[u] + 1) % 3 == f) ins(u1, u2);
			else ins(u2, u1);
		}
		else {
			int o = (s[u] + 1) % 3 == f;
			int p = (s[v] + 1) % 3 == g;
			ins(o ? u1 : u2, p ? v1 : v2);
			ins(p ? v2 : v1, o ? u2 : u1);
		}
	}
	for (int i = 1; i <= N * 2; ++i) dfn[i] = low[i] = 0;
	dfc = bcn = 0;
	for (int i = 1; i <= N * 2; ++i)
		if (!dfn[i]) Tarjan(i);
	for (int i = 1; i <= N; ++i)
		if (bel[i * 2 - 1] == bel[i * 2]) return ;
		else if (bel[i * 2 - 1] < bel[i * 2]) Ans[i] = 1;
		else Ans[i] = 2;
	for (int i = 1; i <= N; ++i) putchar((s[i] + Ans[i]) % 3 + 'A');
	flag = 1;
}

int main() {
	scanf("%d%d", &N, &D);
	scanf("%s", str + 1);
	for (int i = 1; i <= N; ++i)
		if ((s[i] = str[i] - 'a') == 23) pos[++C] = i;
	scanf("%d", &M);
	for (int i = 1; i <= M; ++i) {
		int u, v; char f[3], g[3];
		scanf("%d%s%d%s", &u, f, &v, g);
		eu[i] = u, ev[i] = v;
		ef[i] = *f - 'A', eg[i] = *g - 'A';
	}
	for (int S = 0; S < 1 << D; ++S) {
		for (int i = 0; i < D; ++i)
			s[pos[i + 1]] = S >> i & 1;
		if (Go(), flag) return 0;
		if (clock() >= CLOCKS_PER_SEC * .9) break;
	}
	return printf("-1"), 0;
}

---

##2319. 「NOIP2017」列队

详细题解请见：题解 P3960 【列队】。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define F(i,a,b) for(int i=a;i<=b;++i)
#define dF(i,a,b) for(int i=a;i>=b;--i)
#define F2(i,a,b) for(int i=a;i<b;++i)
#define getchar() (SS==TT&&(TT=(SS=BB)+fread(BB,1,1<<15,stdin),TT==SS)?EOF:*SS++)
#define RR register
char BB[1<<15],*SS=BB,*TT=BB;
inline int read(){
    RR int x;RR bool f;RR char c;
    for (f=0;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
using namespace std;
int q,I[300010];
long long n,m,a[300010],b[300010];
inline bool cmp(int p1,int p2){return a[p1]==a[p2]?p1<p2:a[p1]<a[p2];}
int h[300010],len[300010],len2[300010],bit[900010];
long long arr[900010];
long long Ans[300010];
inline void Ins(int*array,int siz,int i,int x){for(;i<=siz;array[i]+=x,i+=i&-i);}
inline int binary(int*array,int siz,int x){
    int l=1,r,mid,sum,ans;
    while(l<=siz&&array[l]<x) l<<=1, ans=l;
    r=l; sum=array[l>>=1];
    while(l<r-1){
        mid=l+r>>1;
        if(mid>siz||array[mid]+sum>=x) r=mid, ans=mid;
        else l=mid, sum+=array[l];
    } ans=r;
    return ans;
}
int stk[300001],top;
int main(){
    n=read(), m=read(), q=read();
    F(i,1,q) a[i]=read(), b[i]=read(), I[i]=i;
    sort(I+1,I+q+1,cmp);
    F(i,1,m-1) Ins(bit,m-1,i,1);
    F(i,1,n) len[i]=m-1;
    F(i,1,q){
        if(a[I[i-1]]!=a[I[i]])
            while(top) Ins(bit,m-1,stk[top--],1);
        if(b[I[i]]>len[a[I[i]]]) continue;
        int pos=binary(bit,m-1,b[I[i]]);
        Ans[I[i]]=(a[I[i]]-1)*m+pos;
        Ins(bit,m-1,pos,-1);
        stk[++top]=pos;
        --len[a[I[i]]];
    }
    int iter=0;
    F(i,1,n){
        while(iter<=q&&a[I[iter]]<i) ++iter;
        h[i]=iter-1;
    }
    h[n+1]=q;
    memset(bit,0,sizeof bit);
    F(i,1,n) len[i]=0, len2[i]=m-1; len[n+1]=n;
    F(i,1,n) Ins(bit+h[n+1],n+q,i,1), arr[q+i]=i*m;
    F(i,1,q){
        if(Ans[i]){
            int pos=binary(bit+h[n+1],n+q,a[i]);
            Ins(bit+h[n+1],n+q,pos,-1);
            Ins(bit+h[n+1],n+q,++len[n+1],1);
            arr[h[n+1]+len[n+1]]=Ans[i];
            Ins(bit+h[a[i]],h[a[i]+1]-h[a[i]],++len[a[i]],1);
            arr[h[a[i]]+len[a[i]]]=arr[h[n+1]+pos];
            --len2[a[i]];
        }
        else{
            int pos=binary(bit+h[n+1],n+q,a[i]);
            Ins(bit+h[n+1],n+q,pos,-1);
            Ins(bit+h[n+1],n+q,++len[n+1],1);
            if(b[i]!=m){
                int pos2=binary(bit+h[a[i]],h[a[i]+1]-h[a[i]],b[i]-len2[a[i]]);
                Ins(bit+h[a[i]],h[a[i]+1]-h[a[i]],pos2,-1);
                Ans[i]=arr[h[a[i]]+pos2];
                Ins(bit+h[a[i]],h[a[i]+1]-h[a[i]],++len[a[i]],1);
                arr[h[a[i]]+len[a[i]]]=arr[h[n+1]+pos];
            } else Ans[i]=arr[h[n+1]+pos];
            arr[h[n+1]+len[n+1]]=Ans[i];
        }
    }
    F(i,1,q) printf("%lld\n",Ans[i]);
    return 0;
}

---

##2484. 「CEOI2017」Palindromic Partitions

详细题解请见：洛谷 P4656: LOJ 2484: [CEOI2017]Palindromic Partitions。

#include <cstdio>
#include <cstring>

typedef unsigned long long UL;
const int B = 79;

int T, N;
char str[1000005];

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%s", str); N = strlen(str);
		UL s1 = 0, s2 = 0, b = 1;
		int ans = 0;
		for (int i = 0; i < N / 2; ++i) {
			s1 = s1 * B + str[i];
			s2 = s2 + str[N - i - 1] * b;
			b = b * B;
			if (s1 == s2) {
				ans += 2;
				s1 = s2 = 0, b = 1;
			}
		}
		if (N % 2 || s1) ++ans;
		printf("%d\n", ans);
	}
	return 0;
}

---

##2483. 「CEOI2017」Building Bridges

详细题解请见：LOJ 2483: 洛谷 P4655: 「CEOI2017」Building Bridges。

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;
const int MN = 100005;

int N, p[MN], tmp[MN];
LL h[MN], w[MN], f[MN], X[MN], Y[MN];

inline double Slope(int i, int j) {
	if (X[i] == X[j]) return 1e50 * (Y[j] - Y[i]);
	return (double)(Y[j] - Y[i]) / (X[j] - X[i]);
}

int que[MN], l, r;
void Solve(int lb, int rb) {
	if (lb == rb) { Y[lb] += f[lb]; return ; }
	int mid = (lb + rb) >> 1;
	Solve(lb, mid);
	for (int i = lb; i <= rb; ++i) p[i] = i;
	std::sort(p + lb, p + rb + 1, [](int i, int j) { return h[i] < h[j]; });
	l = 1, r = 0;
	for (int i = lb; i <= rb; ++i) if (p[i] <= mid) {
		while (l < r && Slope(que[r - 1], que[r]) >= Slope(que[r], p[i])) --r;
		que[++r] = p[i];
	}
	for (int i = lb; i <= rb; ++i) if (p[i] > mid) {
		while (l < r && Slope(que[l], que[l + 1]) <= 2 * h[p[i]]) ++l;
		f[p[i]] = std::min(f[p[i]], f[que[l]] + (h[p[i]] - h[que[l]]) * (h[p[i]] - h[que[l]]) + w[p[i] - 1] - w[que[l]]);
	}
	Solve(mid + 1, rb);
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%lld", &h[i]);
	for (int i = 1; i <= N; ++i) scanf("%lld", &w[i]), w[i] += w[i - 1];
	for (int i = 1; i <= N; ++i) p[i] = i, X[i] = h[i], Y[i] = h[i] * h[i] - w[i];
	memset(f, 0x7f, sizeof f);
	f[1] = 0, Solve(1, N);
	printf("%lld\n", f[N]);
	return 0;
}

---

##2562. 「SDOI2018」战略游戏

详细题解请见：【算法学习】圆方树。

#include <cstdio>
#include <vector>
#include <algorithm>

const int MN = 100005;

int N, M, Q, cnt;
std::vector<int> G[MN], T[MN * 2];

int dfn[MN * 2], low[MN], dfc;
int stk[MN], tp;
void Tarjan(int u) {
	low[u] = dfn[u] = ++dfc;
	stk[++tp] = u;
	for (auto v : G[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = std::min(low[u], low[v]);
			if (low[v] == dfn[u]) {
				++cnt;
				for (int x = 0; x != v; --tp) {
					x = stk[tp];
					T[cnt].push_back(x);
					T[x].push_back(cnt);
				}
				T[cnt].push_back(u);
				T[u].push_back(cnt);
			}
		}
		else low[u] = std::min(low[u], dfn[v]);
	}
}

int dep[MN * 2], faz[MN * 2][18], dis[MN * 2];
void DFS(int u, int fz) {
	dfn[u] = ++dfc;
	dep[u] = dep[faz[u][0] = fz] + 1;
	dis[u] = dis[fz] + (u <= N);
	for (int j = 0; j < 17; ++j)
		faz[u][j + 1] = faz[faz[u][j]][j];
	for (auto v : T[u]) if (v != fz) DFS(v, u);
}
int LCA(int x, int y) {
	if (dep[x] < dep[y]) std::swap(x, y);
	for (int j = 0, d = dep[x] - dep[y]; d; ++j, d >>= 1)
		if (d & 1) x = faz[x][j];
	if (x == y) return x;
	for (int j = 17; ~j; --j)
		if (faz[x][j] != faz[y][j])
			x = faz[x][j], y = faz[y][j];
	return faz[x][0];
}

int main() {
	int Ti; scanf("%d", &Ti);
	while (Ti--) {
		scanf("%d%d", &N, &M);
		for (int i = 1; i <= N; ++i) {
			G[i].clear();
			dfn[i] = low[i] = 0;
		}
		for (int i = 1; i <= N * 2; ++i) T[i].clear();
		for (int i = 1, x, y; i <= M; ++i) {
			scanf("%d%d", &x, &y);
			G[x].push_back(y);
			G[y].push_back(x);
		}
		cnt = N;
		dfc = 0, Tarjan(1), --tp;
		dfc = 0, DFS(1, 0);
		scanf("%d", &Q);
		while (Q--) {
			static int S, A[MN];
			scanf("%d", &S);
			int Ans = -2 * S;
			for (int i = 1; i <= S; ++i) scanf("%d", &A[i]);
			std::sort(A + 1, A + S + 1, [](int i, int j) { return dfn[i] < dfn[j]; });
			for (int i = 1; i <= S; ++i) {
				int u = A[i], v = A[i % S + 1];
				Ans += dis[u] + dis[v] - 2 * dis[LCA(u, v)];
			}
			if (LCA(A[1], A[S]) <= N) Ans += 2;
			printf("%d\n", Ans / 2);
		}
	}
	return 0;
}

---

##2567. 「APIO2016」划艇

详细题解请见：LOJ 2567: 洛谷 P3643: bzoj 4584: 「APIO2016」划艇。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 505;

int N, lb[MN], rb[MN], lp[MN * 2], len[MN * 2], cnt;
int Inv[MN], C[MN], f[MN], Ans;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
		scanf("%d%d", &lb[i], &rb[i]),
		lp[++cnt] = lb[i],
		lp[++cnt] = rb[i] + 1;
	std::sort(lp + 1, lp + cnt + 1);
	cnt = std::unique(lp + 1, lp + cnt + 1) - lp - 2;
	for (int i = 1; i <= cnt; ++i) len[i] = lp[i + 1] - lp[i];
	for (int i = 1; i <= N; ++i)
		lb[i] = std::lower_bound(lp + 1, lp + cnt + 1, lb[i]) - lp,
		rb[i] = std::lower_bound(lp + 1, lp + cnt + 1, rb[i] + 1) - lp - 1;
	Inv[1] = 1, C[0] = 1, f[0] = 1;
	for (int i = 2; i <= N; ++i) Inv[i] = (LL)(Mod - Mod / i) * Inv[Mod % i] % Mod;
	for (int i = 1; i <= cnt; ++i) {
		int l = len[i];
		for (int j = 1; j <= N; ++j)
			C[j] = (LL)C[j - 1] * (l + j - 1) % Mod * Inv[j] % Mod;
		for (int j = N; j >= 1; --j) if (lb[j] <= i && i <= rb[j]) {
			for (int k = j, a = 0; k >= 1; --k) {
				if (lb[k] <= i && i <= rb[k]) ++a;
				f[j] = (f[j] + (LL)f[k - 1] * C[a]) % Mod;
			}
		}
	}
	for (int i = 1; i <= N; ++i) Ans = (Ans + f[i]) % Mod;
	printf("%d\n", Ans);
	return 0;
}

---

##2587. 「APIO2018」铁人两项

详细题解请见：【算法学习】圆方树。

#include <cstdio>
#include <vector>
#include <algorithm>

const int MN = 100005;

int N, M, cnt;
std::vector<int> G[MN], T[MN * 2];
long long Ans;

int dfn[MN], low[MN], dfc, num;
int stk[MN], tp;

int wgh[MN * 2];

void Tarjan(int u) {
	low[u] = dfn[u] = ++dfc;
	stk[++tp] = u;
	++num;
	for (auto v : G[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = std::min(low[u], low[v]);
			if (low[v] == dfn[u]) {
				wgh[++cnt] = 0;
				for (int x = 0; x != v; --tp) {
					x = stk[tp];
					T[cnt].push_back(stk[tp]);
					T[stk[tp]].push_back(cnt);
					++wgh[cnt];
				}
				T[cnt].push_back(u);
				T[u].push_back(cnt);
				++wgh[cnt];
			}
		}
		else low[u] = std::min(low[u], dfn[v]);
	}
}

int vis[MN * 2], siz[MN * 2];

void DFS(int u, int fz) {
	vis[u] = 1;
	siz[u] = (u <= N);
	for (auto v : T[u]) if (v != fz) {
		DFS(v, u);
		Ans += 2ll * wgh[u] * siz[u] * siz[v];
		siz[u] += siz[v];
	}
	Ans += 2ll * wgh[u] * siz[u] * (num - siz[u]);
}

int main() {
	scanf("%d%d", &N, &M);
	for (int u = 1; u <= N; ++u) wgh[u] = -1;
	cnt = N;
	for (int i = 1; i <= M; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int u = 1; u <= N; ++u) if (!dfn[u]) {
		num = 0;
		Tarjan(u), --tp;
		DFS(u, 0);
	}
	printf("%lld\n", Ans);
	return 0;
}

---

##2718. 「NOI2018」归程

先用 Dijkstra 算法求出 \(1\) 号点到每个点的最短路。

考虑单个询问怎么做，从 \(v\) 开始只走海拔大于 \(p\) 的边，必然形成一个子图，求这个子图中最短路的最小值。

如果有多个询问，需要快速获取这个值。考虑原图以 \(a\) 为权值的最大生成树，则刚刚的子图在其中是一个连通子树。

而限制了海拔下限则意味着我们考虑的图是 Kruskal 求最小生成树的过程中的一个阶段。

我们是有办法把每个阶段记录下来的，只需要重建一棵 Kruskal 重构树，其中每个有连边的阶段会新建一个节点，并成为代表上一个阶段两个被连接的联通块的节点的父亲。

这样，再在 Kruskal 重构树上倍增寻找最浅的合并时海拔大于 \(p\) 的祖先，查询其子树内距离的最小值即可。由于是静态树，子树内最小值可以直接预处理求出。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

const int MN = 200005;
const int MM = 400005;
const int Inf = 0x3f3f3f3f;

int N, M, cnt;
int eu[MM], ev[MM], el[MM], ea[MM], ep[MM];
int fa[MN * 2]; int ff(int x) { return fa[x] ? fa[x] = ff(fa[x]) : x; }
struct edg {
    int to, w;
    edg() {}
    edg(int to, int w) : to(to), w(w) {}
    inline friend bool operator <(edg i, edg j) { return i.w > j.w; }
};
std::vector<edg> G[MN];
int faz[MN * 2][18], wgh[MN * 2];

std::priority_queue<edg> pq;
int dis[MN * 2], vis[MN];
void Dijkstra() {
	for (int i = 1; i <= N; ++i)
		dis[i] = Inf, vis[i] = 0;
    dis[1] = 0; pq.push(edg(1, 0));
    while (!pq.empty()) {
        edg e = pq.top(); pq.pop();
        int u = e.to, d = e.w;
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto p : G[u]) {
            if (dis[p.to] > d + p.w) {
                dis[p.to] = d + p.w;
                pq.push(edg(p.to, dis[p.to]));
            }
        }
    }
}

int main() {
	freopen("return.in", "r", stdin);
	freopen("return.out", "w", stdout);
    int T; scanf("%d", &T);
    for (int t = 1; t <= T; ++t) {
        scanf("%d%d", &N, &M);
        for (int i = 1; i <= N; ++i) G[i].clear();
        for (int i = 1; i <= N * 2; ++i) fa[i] = 0;
        for (int i = 1; i <= M; ++i) {
            scanf("%d%d%d%d", &eu[i], &ev[i], &el[i], &ea[i]), ep[i] = i;
            G[eu[i]].push_back(edg(ev[i], el[i]));
            G[ev[i]].push_back(edg(eu[i], el[i]));
        }
        Dijkstra();
        std::sort(ep + 1, ep + M + 1, [](int i, int j) { return ea[i] > ea[j]; });
        cnt = N;
        for (int i = 1; i <= M; ++i) {
            int u = eu[ep[i]], v = ev[ep[i]], a = ea[ep[i]];
            if (ff(u) != ff(v)) {
                u = ff(u), v = ff(v);
                ++cnt;
                fa[u] = fa[v] = cnt;
                faz[u][0] = faz[v][0] = cnt;
                wgh[cnt] = a;
                dis[cnt] = std::min(dis[u], dis[v]);
            }
        }
        for (int i = cnt; i >= 1; --i)
            for (int j = 1; j <= 17; ++j)
                faz[i][j] = faz[faz[i][j - 1]][j - 1];
        int Q, K, S, lastans = 0;
        scanf("%d%d%d", &Q, &K, &S);
        for (int q = 1; q <= Q; ++q) {
        	int v, p;
        	scanf("%d%d", &v, &p);
        	v = (v + K * lastans - 1) % N + 1;
        	p = (p + K * lastans) % (S + 1);
        	for (int j = 17; ~j; --j)
        		if (faz[v][j] && wgh[faz[v][j]] > p)
        			v = faz[v][j];
        	printf("%d\n", lastans = dis[v]);
		}
    }
    return 0;
}

---

##2719. 「NOI2018」冒泡排序

详细题解请见：咕了。

#include <cstdio>
#include <cstring>

typedef long long LL;
const int Mod = 998244353;
const int MN = 600005;

int Inv[MN * 2], Fac[MN * 2], iFac[MN * 2];
inline void Init(int N) {
	Inv[1] = 1;
	for (int i = 2; i <= N; ++i)
		Inv[i] = (LL)(Mod - Mod / i) * Inv[Mod % i] % Mod;
	Fac[0] = iFac[0] = 1;
	for (int i = 1; i <= N; ++i)
		Fac[i] = (LL)Fac[i - 1] * i % Mod,
		iFac[i] = (LL)iFac[i - 1] * Inv[i] % Mod;
}
inline int Binom(int N, int M) {
	if (M < 0 || M > N) return 0;
	return (LL)Fac[N] * iFac[M] % Mod * iFac[N - M] % Mod;
}

int T, N;
bool usd[MN];

int main() {
	freopen("inverse.in", "r", stdin);
	freopen("inverse.out", "w", stdout);
	Init(1200000);
	scanf("%d", &T);
	for (int t = 1; t <= T; ++t) {
		scanf("%d", &N);
		memset(usd + 1, 0, N + 1);
		int mx = 0, mn = 1, Ans = 0;
		for (int i = 1, x; i <= N; ++i) {
			scanf("%d", &x);
			usd[x] = 1;
			int lm = mx < x ? x : mx;
			Ans = ((LL)Ans + Binom(2 * N - i - lm, N - i + 1) - Binom(2 * N - i - lm, N - i + 2) + Mod) % Mod;
			if (mx < x) mx = x;
			else if (x != mn) { while (++i <= N) scanf("%d", &x); break; }
			while (usd[mn]) ++mn;
		}
		printf("%d\n", Ans);
	}
	return 0;
}

---

##2721. 「NOI2018」屠龙勇士

首先确定攻击每条巨龙时选择的剑的攻击力，这可以直接使用 std::multiset 简单地得出。

对于第 \(i\) 条巨龙，假设剑的攻击力为 \(atk_i\)，则需要满足存在非负整数 \(k\) 使得 \(a_i-atk_ix+p_ik=0\) 才能杀死巨龙。

这相当于 \(atk_ix\equiv a_i\pmod{p_i}\) 且 \(atk_ix\ge a_i\)。

先不考虑后面的条件，对于前面的条件，我们 ExCRT 合并即可。

对于后面的条件，即为 \(x\ge\lceil\frac{a_i}{atk_i}\rceil\)，将所有 \(\lceil\frac{a_i}{atk_i}\rceil\) 取个 \(\max\)，算一下即可。

注意乘法爆 long long，请用快速乘。

#include <cstdio>
#include <set>

typedef long long LL;
const int MN = 100005;

LL mul(LL a, LL b, LL m) { return (a * b - (LL)((long double)a / m * b) * m + m) % m; }
LL exgcd(LL a, LL b, LL &x, LL &y) {
	if (!b) return x = 1, y = 0, a;
	LL d = exgcd(b, a % b, y, x);
	return y -= a / b * x, d;
}

int N, M;
LL a[MN], m[MN];
int atk[MN]; std::multiset<LL> st;

inline bool Combine(LL &a1, LL &m1, LL a2, LL m2) {
	LL k1, k2, g = exgcd(m1, m2, k1, k2);
	if ((a2 - a1) % g) return 0;
	a1 += mul(mul(k1, (a2 - a1) / g, m2), m1, m1 / g * m2);
	return a1 %= m1 *= m2 / g, 1;
}

inline LL ExCRT() {
	LL x, y, d, MnX = 0;
	for (int i = 1; i <= N; ++i) {
		if (MnX < (a[i] - 1) / atk[i] + 1) MnX = (a[i] - 1) / atk[i] + 1;
		d = exgcd(atk[i], m[i], x, y);
		if (a[i] % d) return -1;
		a[i] /= d, m[i] /= d;
		a[i] = mul(a[i], x, m[i]);
	}
	LL P = 0, Q = 1;
	for (int i = 1; i <= N; ++i)
		if (!Combine(P, Q, a[i], m[i])) return -1;
	P = MnX / Q * Q + P;
	if (P < MnX) P += Q;
	return P;
}

int main() {
	freopen("dragon.in", "r", stdin);
	freopen("dragon.out", "w", stdout);
	int T; scanf("%d", &T);
	while (T--) {
		st.clear();
		scanf("%d%d", &N, &M);
		for (int i = 1; i <= N; ++i) scanf("%lld", &a[i]);
		for (int i = 1; i <= N; ++i) scanf("%lld", &m[i]);
		for (int i = 1; i <= N; ++i) scanf("%d", &atk[i]);
		for (int i = 1, x; i <= M; ++i) scanf("%d", &x), st.insert(x);
		for (int i = 1; i <= N; ++i) {
			auto it = st.upper_bound(a[i]);
			if (it != st.begin()) --it;
			st.insert(atk[i]);
			atk[i] = *it;
			st.erase(it);
		}
		printf("%lld\n", ExCRT());
	}
	return 0;
}

---

##2816. 「eJOI2018」元素周期表

详细题解请见：洛谷 P5089: CodeForces #500 (Div. 1) B / 1012B : Chemical table。

#include <cstdio>
#include <vector>

const int MN = 400005;

int N, M, Q, S;
int vis[MN];
std::vector<int> G[MN];

void DFS(int u) {
	vis[u] = 1;
	for (int i : G[u])
		if (!vis[i]) DFS(i);
}

int main() {
	scanf("%d%d%d", &N, &M, &Q);
	for (int i = 1; i <= Q; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		y += N;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for (int i = 1; i <= N + M; ++i)
		if (!vis[i]) ++S, DFS(i);
	printf("%d", S - 1);
	return 0;
}

---

##2983. 「WC2019」数树

详细题解请见：洛谷 P5206: bzoj 5475: LOJ 2983: [WC2019] 数树。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

typedef long long LL;
const int MN = 100005;
const LL Mod = 998244353;

inline LL qPow(LL b, int e) {
	LL a = 1;
	for (; e; b = b * b % Mod, e >>= 1)
		if (e & 1) a = a * b % Mod;
	return a;
}

int N, op;
LL Y;

namespace Solver0 {
	inline LL solve() {
		if (op == 0) return 1;
		if (op == 1) return qPow(N, N - 2);
		if (op == 2) return qPow(N, 2 * (N - 2));
		return 0;
	}
}

namespace Solver1 {
	typedef std::pair<int, int> pii;
	std::set<pii> S;

	inline LL solve() {
		for (int i = 1, x, y; i < N; ++i) {
			scanf("%d%d", &x, &y);
			if (x > y) std::swap(x, y);
			S.insert(std::make_pair(x, y));
		}
		int cnt = N;
		for (int i = 1, x, y; i < N; ++i) {
			scanf("%d%d", &x, &y);
			if (x > y) std::swap(x, y);
			cnt -= S.count(std::make_pair(x, y));
		}
		return qPow(Y, cnt);
	}
}

namespace Solver2 {
	int h[MN], nxt[MN * 2], to[MN * 2], tot;
	inline void ins(int x, int y) {
		nxt[++tot] = h[x], to[tot] = y, h[x] = tot;
	}

	LL K, f[MN], g[MN];
	void DFS(int u, int fz) {
		f[u] = 1, g[u] = K;
		for (int i = h[u]; i; i = nxt[i]) if (to[i] != fz) {
			DFS(to[i], u);
			g[u] = (f[u] * g[to[i]] + g[u] * f[to[i]] + g[u] * g[to[i]]) % Mod;
			f[u] = (f[u] * f[to[i]] + f[u] * g[to[i]]) % Mod;
		}
	}

	inline LL solve() {
		for (int i = 1, x, y; i < N; ++i) {
			scanf("%d%d", &x, &y);
			ins(x, y), ins(y, x);
		}
		K = (LL)N * Y % Mod * qPow(1 - Y, Mod - 2) % Mod;
		LL coef = qPow(1 - Y, N) * qPow(N, Mod - 3) % Mod;
		DFS(1, 0);
		return g[1] * coef % Mod;
	}
}

namespace Solver3 {
	const int MS = 1 << 19;
	const int G = 3, iG = 332748118;
	int Sz = 0, R[MS]; LL InvSz;
	LL Inv[MS], Fac[MS], iFac[MS];

	inline void Init() {
		Inv[1] = 1;
		for (int i = 2; i < MS; ++i) Inv[i] = -(Mod / i) * Inv[Mod % i] % Mod;
		Fac[0] = iFac[0] = 1;
		for (int i = 1; i < MS; ++i) {
			Fac[i] = Fac[i - 1] * i % Mod;
			iFac[i] = iFac[i - 1] * Inv[i] % Mod;
		}
	}

	inline void InitFNTT(int n) {
		int Bt = 0;
		for (; 1 << Bt < n; ++Bt) ;
		if ((1 << Bt) == Sz) return ;
		Sz = 1 << Bt, InvSz = -(Mod - 1) / Sz;
		for (int i = 1; i < Sz; ++i) R[i] = R[i >> 1] >> 1 | (i & 1) << (Bt - 1);
	}

	inline void FNTT(LL *A, int Type) {
		for (int i = 0; i < Sz; ++i) if (R[i] < i) std::swap(A[R[i]], A[i]);
		for (int j = 1, j2 = 2; j < Sz; j <<= 1, j2 <<= 1) {
			LL gn = qPow(~Type ? G : iG, (Mod - 1) / j2), g;
			for (int i = 0, k; i < Sz; i += j2) {
				for (k = 0, g = 1; k < j; ++k, g = g * gn % Mod) {
					LL X = A[i + k], Y = g * A[i + j + k] % Mod;
					A[i + k] = (X + Y) % Mod, A[i + j + k] = (X - Y) % Mod;
				}
			}
		}
		if (Type == -1) for (int i = 0; i < Sz; ++i) A[i] = A[i] * InvSz % Mod;
	}

	inline void PolyInv(LL *A, int N, LL *B) {
		B[0] = qPow(A[0], Mod - 2);
		static LL tA[MS], tB[MS];
		for (int L = 1; L < N; L <<= 1) {
			int L2 = L << 1, L4 = L << 2;
			InitFNTT(L4);
			for (int i = 0; i < L2; ++i) tA[i] = A[i];
			for (int i = L2; i < Sz; ++i) tA[i] = 0;
			for (int i = 0; i < L; ++i) tB[i] = B[i];
			for (int i = L; i < Sz; ++i) tB[i] = 0;
			FNTT(tA, 1), FNTT(tB, 1);
			for (int i = 0; i < Sz; ++i) tB[i] = (2 - tA[i] * tB[i]) % Mod * tB[i] % Mod;
			FNTT(tB, -1);
			for (int i = 0; i < L2; ++i) B[i] = tB[i];
		}
	}

	inline void PolyLn(LL *A, int N, LL *B) {
		static LL tA[MS], tB[MS];
		PolyInv(A, N, tB);
		InitFNTT(N * 2);
		for (int i = 1; i < N; ++i) tA[i - 1] = A[i] * i % Mod;
		for (int i = N - 1; i < Sz; ++i) tA[i] = 0;
		for (int i = N; i < Sz; ++i) tB[i] = 0;
		FNTT(tA, 1), FNTT(tB, 1);
		for (int i = 0; i < Sz; ++i) tA[i] = tA[i] * tB[i] % Mod;
		FNTT(tA, -1);
		B[0] = 0;
		for (int i = 1; i < N; ++i) B[i] = tA[i - 1] * Inv[i] % Mod;
	}

	inline void PolyExp(LL *A, int N, LL *B) {
		B[0] = 1;
		static LL tA[MS], tB[MS];
		for (int L = 1; L < N; L <<= 1) {
			int L2 = L << 1, L4 = L << 2;
			PolyLn(B, L2, tA);
			InitFNTT(L4);
			for (int i = 0; i < L2; ++i) tA[i] = (!i + A[i] - tA[i]) % Mod;
			for (int i = L2; i < Sz; ++i) tA[i] = 0;
			for (int i = 0; i < L2; ++i) tB[i] = B[i];
			for (int i = L2; i < Sz; ++i) tB[i] = 0;
			FNTT(tA, 1), FNTT(tB, 1);
			for (int i = 0; i < Sz; ++i) tA[i] = tA[i] * tB[i] % Mod;
			FNTT(tA, -1);
			for (int i = 0; i < L2; ++i) B[i] = tA[i];
		}
	}

	inline LL solve() {
		Init();
		LL K = (LL)N * N % Mod * Y % Mod * qPow(1 - Y, Mod - 2) % Mod;
		LL coef = qPow(1 - Y, N) * qPow(N, Mod - 5) % Mod;
		static LL A[MS], B[MS];
		A[0] = 0;
		for (int i = 1; i <= N; ++i) A[i] = K * qPow(i, i) % Mod * iFac[i] % Mod;
		PolyExp(A, N + 1, B);
		return coef * (B[N] * Fac[N] % Mod) % Mod;
	}
}

int main() {
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	scanf("%d%lld%d", &N, &Y, &op);
	if (Y == 1) printf("%lld\n", Solver0::solve());
	else if (op == 0) printf("%lld\n", (Solver1::solve() + Mod) % Mod);
	else if (op == 1) printf("%lld\n", (Solver2::solve() + Mod) % Mod);
	else if (op == 2) printf("%lld\n", (Solver3::solve() + Mod) % Mod);
	return 0;
}

---

##3043. 「ZJOI2019」线段树

详细题解请见：LOJ 3043: 洛谷 P5280: 「ZJOI2019」线段树。

#include <cstdio>

typedef long long LL;
const int Mod = 998244353;
const int Inv2 = 499122177;
const int MS = 1 << 18;

inline int Add(int x, int y) {
	return (x += y) >= Mod ? x - Mod : x;
}

int N, M;

int f[MS], g[MS], Sf[MS], T[MS];
inline void P(int i, int x) {
	g[i] = ((LL)g[i] * x + 1 - x + Mod) % Mod;
	T[i] = (LL)T[i] * x % Mod;
}
inline void Upd(int i, int Ty) {
	if (Ty) Sf[i] = f[i];
	else Sf[i] = Add(f[i], Add(Sf[i << 1], Sf[i << 1 | 1]));
}
inline void Psd(int i) {
	P(i << 1, T[i]);
	P(i << 1 | 1, T[i]);
	T[i] = 1;
}
void Build(int i, int l, int r) {
	T[i] = 1;
	if (l != r) {
		Build(i << 1, l, (l + r) >> 1);
		Build(i << 1 | 1, ((l + r) >> 1) + 1, r);
	}
}
void Mdf(int i, int l, int r, int a, int b) {
	if (r < a || b < l) {
		f[i] = (LL)(f[i] + g[i]) * Inv2 % Mod;
		Upd(i, l == r);
		return ;
	}
	if (a <= l && r <= b) {
		f[i] = (LL)(f[i] + 1) * Inv2 % Mod;
		Upd(i, l == r);
		P(i, Inv2);
		return ;
	}
	Psd(i);
	f[i] = (LL)f[i] * Inv2 % Mod;
	g[i] = (LL)g[i] * Inv2 % Mod;
	Mdf(i << 1, l, (l + r) >> 1, a, b);
	Mdf(i << 1 | 1, ((l + r) >> 1) + 1, r, a, b);
	Upd(i, 0);
}

int main() {
	scanf("%d%d", &N, &M);
	Build(1, 1, N);
	for (int m = 1, C = 1; m <= M; ++m) {
		int op, l, r;
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d%d", &l, &r);
			Mdf(1, 1, N, l, r);
			C = Add(C, C);
		}
		else printf("%lld\n", (LL)C * Sf[1] % Mod);
	}
	return 0;
}

---

##3045. 「ZJOI2019」开关

详细题解请见：LOJ 3045: 洛谷 P5326: 「ZJOI2019」开关。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 998244353, Inv2 = (Mod + 1) / 2;
const int MN = 105, MP = 50005;

inline void Add(int &x, LL y) { x = (x + y) % Mod; }
inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}
inline int gInv(int b) { return qPow(b, Mod - 2); }

int N, s[MN], p[MN], sump;
int _a[2][MP * 2], _b[2][MP * 2], *a[2] = {_a[0] + MP, _a[1] + MP}, *b[2] = {_b[0] + MP, _b[1] + MP};
int Ans;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d", &s[i]), s[i] = s[i] ? -1 : 1;
	b[0][0] = a[0][0] = 1;
	for (int i = 1; i <= N; ++i) {
		scanf("%d", &p[i]);
		for (int j = -sump - p[i]; j <= sump + p[i]; ++j) b[1][j] = a[1][j] = 0;
		for (int j = -sump; j <= sump; ++j)
			Add(a[1][j + p[i]], (LL)Inv2 * a[0][j]),
			Add(a[1][j - p[i]], s[i] * (LL)Inv2 * a[0][j]),
			Add(b[1][j + p[i]], (LL)Inv2 * b[0][j]),
			Add(b[1][j - p[i]], (LL)Inv2 * b[0][j]);
		sump += p[i];
		std::swap(a[0], a[1]), std::swap(b[0], b[1]);
	}
	int isump = gInv(sump), *A = a[0], *B = b[0];
	for (int j = -sump; j < sump; ++j)
		Add(Ans, ((LL)A[j] * B[sump] - (LL)B[j] * A[sump]) % Mod * gInv((LL)j * isump % Mod - 1));
	Ans = (LL)Ans * qPow(B[sump], Mod - 3) % Mod;
	printf("%d\n", (Ans + Mod) % Mod);
	return 0;
}

---

##3049. 「十二省联考 2019」字符串问题

详细题解请见：LOJ 3049: 洛谷 P5284: 「十二省联考 2019」字符串问题。

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

typedef long long LL;
const int MN = 200005;
const int MS = 4200005;

char str[MN];
int N, Sig, rk[MN], SA[MN], SA2[MN], buk[MN], tmp[MN];
int Height[MN];
inline void getHeight() {
	for (int i = 1, k = 0; i <= N; ++i) {
		if (rk[i] == 1) { Height[rk[i]] = k = 0; continue; }
		if (k) --k;
		int j = SA[rk[i] - 1];
		while (i + k <= N && j + k <= N && str[i + k] == str[j + k]) ++k;
		Height[rk[i]] = k;
	}
}
inline void RSort() {
	for (int i = 1; i <= Sig; ++i) buk[i] = 0;
	for (int i = 1; i <= N; ++i) ++buk[rk[i]];
	for (int i = 1; i <= Sig; ++i) buk[i] += buk[i - 1];
	for (int i = N; i >= 1; --i) SA[buk[rk[SA2[i]]]--] = SA2[i];
}
inline void getSA(char *str) {
	Sig = 127, rk[N + 1] = 0;
	for (int i = 1; i <= N; ++i) rk[i] = str[i], SA2[i] = i;
	RSort();
	for (int j = 1; j <= N; j <<= 1) {
		int p = 0;
		for (int i = N - j + 1; i <= N; ++i) SA2[++p] = i;
		for (int i = 1; i <= N; ++i) if (SA[i] > j) SA2[++p] = SA[i] - j;
		RSort();
		tmp[SA[1]] = p = 1;
		for (int i = 2; i <= N; ++i) {
			int lst = SA[i - 1], now = SA[i];
			if (rk[lst] != rk[now] || rk[lst + j] != rk[now + j]) ++p;
			tmp[SA[i]] = p;
		}
		for (int i = 1; i <= N; ++i) rk[i] = tmp[i];
		if ((Sig = p) == N) break;
	}
	getHeight();
}

int Lg[MN];
inline void Log(int N) {
	Lg[0] = -1;
	for (int i = 1; i <= N; ++i) Lg[i] = Lg[i >> 1] + 1;
}
int ST[MN][18];
inline void InitST() {
	for (int i = 2; i <= N; ++i) ST[i][0] = Height[i];
	for (int j = 1; j <= Lg[N - 1]; ++j) {
		for (int i = 1; i <= 1 << j; ++i) ST[i][j] = 0;
		for (int i = 1 << j | 1; i <= N; ++i)
			ST[i][j] = std::min(ST[i - (1 << (j - 1))][j - 1], ST[i][j - 1]);
	}
}

int NA, la[MN], ra[MN];
int NB, lb[MN], rb[MN];
struct sub {
	int lb, len, typ, id;
	sub() {}
	sub(int lb, int len, int typ, int id) : lb(lb), len(len), typ(typ), id(id) {}
	inline friend bool operator <(sub i, sub j) {
		return i.len == j.len ? i.typ < j.typ : i.len > j.len;
	}
} substrs[MN * 2];

int d[MS];
std::vector<int> G[MS];
inline void addEdge(int x, int y) { ++d[y]; G[x].push_back(y); }

int rt[MN], lc[MS], rc[MS], wgh[MS], cnt;
void Mdf(int &rt, int l, int r, int p, int x) {
	lc[++cnt] = lc[rt], rc[cnt] = rc[rt];
	if (rt) addEdge(cnt, rt);
	wgh[rt = cnt] = 0;
	if (l == r) { addEdge(rt, x); return ; }
	int mid = (l + r) >> 1;
	if (p <= mid) Mdf(lc[rt], l, mid, p, x), addEdge(rt, lc[rt]);
	else Mdf(rc[rt], mid + 1, r, p, x), addEdge(rt, rc[rt]);
}
void Edg(int rt, int l, int r, int a, int b, int x) {
	if (!rt || r < a || b < l) return ;
	if (a <= l && r <= b) { addEdge(x, rt); return ; }
	int mid = (l + r) >> 1;
	Edg(lc[rt], l, mid, a, b, x);
	Edg(rc[rt], mid + 1, r, a, b, x);
}

int que[MS], l, r;
LL f[MS];

int main() {
	int T; scanf("%d", &T);
	Log(200000);
	while (T--) {
		scanf("%s", str + 1);
		N = strlen(str + 1);
		getSA(str);
		InitST();
		scanf("%d", &NA);
		for (int i = 1; i <= NA; ++i)
			scanf("%d%d", &la[i], &ra[i]),
			substrs[i] = sub(rk[la[i]], ra[i] - la[i] + 1, 0, i);
		scanf("%d", &NB);
		for (int i = 1; i <= NB; ++i)
			scanf("%d%d", &lb[i], &rb[i]),
			substrs[NA + i] = sub(rk[lb[i]], rb[i] - lb[i] + 1, 1, i);
		std::sort(substrs + 1, substrs + NA + NB + 1);
		cnt = NA + NB;
		for (int i = 1; i <= NA; ++i) wgh[i] = ra[i] - la[i] + 1;
		for (int i = 1; i <= NB; ++i) wgh[NA + i] = 0;
		for (int i = 1, gen = 0; i <= NA + NB; ++i) {
			sub p = substrs[i];
			if (!p.typ) ++gen, Mdf(rt[gen] = rt[gen - 1], 1, N, p.lb, p.id);
			else {
				int Lb = p.lb, Rb = p.lb;
				for (int j = Lg[p.lb - 1]; ~j; --j)
					if (ST[Lb][j] >= p.len) Lb -= 1 << j;
				for (int j = Lg[N - p.lb]; ~j; --j)
					if (Rb + (1 << j) <= N && ST[Rb + (1 << j)][j] >= p.len) Rb += 1 << j;
				Edg(rt[gen], 1, N, Lb, Rb, NA + p.id);
			}
		}
		int M; scanf("%d", &M);
		for (int i, j; M--; ) {
			scanf("%d%d", &i, &j);
			addEdge(i, NA + j);
		}
		LL Ans = 0;
		l = 1, r = 0;
		for (int i = 1; i <= cnt; ++i) {
			f[i] = wgh[i];
			if (!d[i]) que[++r] = i;
		}
		while (l <= r) {
			int u = que[l++];
			Ans = std::max(Ans, f[u]);
			for (auto v : G[u]) {
				f[v] = std::max(f[v], f[u] + wgh[v]);
				if (!--d[v]) que[++r] = v;
			}
		}
		if (r != cnt) puts("-1");
		else printf("%lld\n", Ans);
		for (int i = 1; i <= cnt; ++i) d[i] = 0, G[i].clear();
	}
	return 0;
}

---

##3089. 「BJOI2019」奥术神杖

详细题解请见：LOJ 3089: 洛谷 P5319: 「BJOI2019」奥术神杖。

#include <cstdio>
#include <cmath>

typedef double f64;
const int MN = 1505, Sig = 10;
const f64 eps = 1e-6, inf = 1e99;

int N, M;
char T[MN];

char str[MN];
int ch[MN][Sig], fail[MN], sum[MN], cnt;
f64 val[MN];

inline void Insert(char *s, f64 v) {
	int now = 0;
	for (; *s; ++s) {
		if (!ch[now][*s & 15]) ch[now][*s & 15] = ++cnt;
		now = ch[now][*s & 15];
	} ++sum[now], val[now] += v;
}

int que[MN], l, r;
void BuildAC() {
	fail[0] = -1;
	que[l = r = 1] = 0;
	while (l <= r) {
		int u = que[l++];
		for (int i = 0; i < Sig; ++i) {
			if (ch[u][i]) {
				int x = fail[u];
				while (~x && !ch[x][i]) x = fail[x];
				if (~x) fail[ch[u][i]] = ch[x][i];
				que[++r] = ch[u][i];
			}
			else if (~fail[u]) ch[u][i] = ch[fail[u]][i];
		}
	}
	for (int i = 2; i <= r; ++i)
		sum[que[i]] += sum[fail[que[i]]],
		val[que[i]] += val[fail[que[i]]];
}

f64 f[MN][MN];
int g[MN][MN][2];
char AT[MN];
inline f64 DP(f64 V) {
	for (int j = 0; j <= cnt; ++j) val[j] -= sum[j] * V;
	for (int i = 0; i <= N; ++i)
		for (int j = 0; j <= cnt; ++j)
			f[i][j] = -inf;
	f[0][0] = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= cnt; ++j) {
			if (f[i][j] == -inf) continue;
			if (T[i] == '.') {
				for (int k = 0; k < Sig; ++k) {
					int _j = ch[j][k];
					if (f[i + 1][_j] < f[i][j] + val[_j])
						f[i + 1][_j] = f[i][j] + val[_j],
						g[i + 1][_j][0] = j,
						g[i + 1][_j][1] = k;
				}
			}
			else {
				int _j = ch[j][T[i] & 15];
				if (f[i + 1][_j] < f[i][j] + val[_j])
					f[i + 1][_j] = f[i][j] + val[_j],
					g[i + 1][_j][0] = j,
					g[i + 1][_j][1] = T[i] & 15;
			}
		}
	}
	for (int j = 0; j <= cnt; ++j) val[j] += sum[j] * V;
	int ans = 0;
	for (int j = 1; j <= cnt; ++j)
		if (f[N][j] > f[N][ans]) ans = j;
	for (int i = N, j = ans; i >= 1; --i)
		AT[i - 1] = g[i][j][1] | 48,
		j = g[i][j][0];
	return f[N][ans];
}

int main() {
	scanf("%d%d", &N, &M);
	scanf("%s", T);
	for (int i = 1; i <= M; ++i) {
		f64 v;
		scanf("%s%lf", str, &v);
		Insert(str, log(v));
	}
	BuildAC();
	f64 l = 0, r = log(1e9 + 5), mid, ans = 0;
	while (r - l > eps) {
		mid = (l + r) / 2;
		if (DP(mid) > 0) ans = mid, l = mid;
		else r = mid;
	}
	DP(ans);
	printf("%s\n", AT);
	return 0;
}

---

##3093. 「BJOI2019」光线

详细题解请见：LOJ 3093: 洛谷 P5323: 「BJOI2019」光线。

#include <cstdio>

typedef long long LL;
const int Mod = 1000000007;
const int Inv100 = 570000004;

inline LL Inv(LL b) {
	LL a = 1;
	for (int e = Mod - 2; e; e >>= 1, b = b * b % Mod)
		if (e & 1) a = a * b % Mod;
	return a;
}

int N;
LL P, Q;

int main() {
	scanf("%d", &N);
	P = 1, Q = 0;
	while (N--) {
		LL a, b;
		scanf("%lld%lld", &a, &b);
		a = a * Inv100 % Mod, b = b * Inv100 % Mod;
		LL W = Inv((1 - Q * b % Mod + Mod) % Mod);
		Q = (b + a * a % Mod * Q % Mod * W) % Mod;
		P = P * a % Mod * W % Mod;
	}
	printf("%lld\n", P);
	return 0;
}

---

##3101. 「JSOI2019」精准预测

离散化，2-SAT 建图，建出来发现是天然的 DAG，传递闭包直接 bitset 整上，为了防止 MLE 需要分块做 bitset。

#include <cstdio>
#include <vector>
#include <bitset>
#include <map>

const int MN = 50005, MM = 100005, MS = 500005, B = 1 << 14;

int T, N, M, tot;
std::map<int, int> Id[2][MN];
inline int gId(int o, int i, int t) {
	int &x = Id[o][i][t];
	return x ? x : x = ++tot;
}
int deg[MS];
std::vector<int> G[MS];
inline void Add(int x, int y) {
	G[x].push_back(y), ++deg[y];
}
int que[MS], l, r;
std::bitset<B> V[MS], Del;
int GG[MN], Ans[MN];

int main() {
	scanf("%d%d%d", &T, &N, &M);
	for (int i = 1; i <= N; ++i) gId(0, i, T + 1), gId(1, i, T + 1);
	for (int i = 1; i <= M; ++i) {
		int op, t, u, v;
		scanf("%d%d%d%d", &op, &t, &u, &v);
		if (op) Add(gId(0, u, t), gId(1, v, t)), Add(gId(0, v, t), gId(1, u, t));
		else Add(gId(1, u, t), gId(1, v, t + 1)), Add(gId(0, v, t + 1), gId(0, u, t));
	}
	for (int o = 0; o <= 1; ++o) for (int i = 1; i <= N; ++i) {
		int lst = 0;
		for (auto p : Id[o][i]) {
			int now = p.second;
			if (lst) {
				if (o) Add(lst, now);
				else Add(now, lst);
			}
			lst = now;
		}
	}
	l = 1;
	for (int u = 1; u <= tot; ++u) if (!deg[u]) que[++r] = u;
	while (l <= r) {
		int u = que[l++];
		for (int v : G[u]) if (!--deg[v]) que[++r] = v;
	}
	for (int u = 1; u <= N; ++u) Ans[u] = N - 1;
	for (int i = 1; i <= N; i += B) {
		for (int u = 1; u <= tot; ++u) V[u].reset();
		Del.reset();
		for (int j = 0; j < B && i + j <= N; ++j)
			V[gId(1, i + j, T + 1)].set(j);
		for (int j = r; j >= 1; --j) {
			int u = que[j];
			for (int v : G[u]) V[u] |= V[v];
		}
		for (int j = 0; j < B && i + j <= N; ++j)
			if (V[gId(0, i + j, T + 1)].test(j))
				GG[i + j] = 1, Del.set(j);
		for (int u = 1; u <= N; ++u) Ans[u] -= (V[gId(0, u, T + 1)] | Del).count();
	}
	for (int i = 1; i <= N; ++i) printf("%d ", GG[i] ? 0 : Ans[i]);
	return 0;
}

---

##3119. 「CTS2019 | CTSC2019」随机立方体

详细题解请见：LOJ 3119: 洛谷 P5400: 「CTS2019 | CTSC2019」随机立方体。

#include <cstdio>

typedef long long LL;
const int Mod = 998244353;
const int MN = 5000005;

void exgcd(int a, int b, int &x, int &y) {
	if (!b) x = 1, y = 0;
	else exgcd(b, a % b, y, x), y -= a / b * x;
}
inline int Inv(int a) {
	int x, y;
	exgcd(a < 0 ? a + Mod : a, Mod, x, y);
	return x;
}

int Invs[MN];
inline void Init(int N) {
	Invs[1] = 1;
	for (int i = 2; i <= N; ++i)
		Invs[i] = -(LL)(Mod / i) * Invs[Mod % i] % Mod;
}

int N, M, L, Q, K, Ans;
int Vals[MN], iVals[MN];

inline int R(int x) { return (LL)(N - x) * (M - x) % Mod * (L - x) % Mod; }

int main() {
	Init(5000000);
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d%d", &N, &M, &L, &K), Ans = 0;
		Q = N < M ? N < L ? N : L : M < L ? M : L;
		iVals[0] = 1;
		for (int i = 1; i <= Q; ++i)
			Vals[i] = R(0) - R(i),
			iVals[i] = (LL)iVals[i - 1] * Vals[i] % Mod;
		int iV = Inv(iVals[Q]);
		for (int i = Q; i >= 1; --i)
			iVals[i] = (LL)iV * iVals[i - 1] % Mod,
			iV = (LL)iV * Vals[i] % Mod;
		int C = 0, S = 1;
		for (int i = 1; i <= Q; ++i) {
			S = (LL)S * R(i - 1) % Mod * iVals[i] % Mod;
			if (i == K) C = 1;
			if (i > K) C = -(LL)C * i % Mod * Invs[i - K] % Mod;
			Ans = (Ans + (LL)C * S) % Mod;
		}
		printf("%d\n", Ans < 0 ? Ans + Mod : Ans);
	}
	return 0;
}

---

##3120. 「CTS2019 | CTSC2019」珍珠

详细题解请见：LOJ 3120: 洛谷 P5401: 「CTS2019 | CTSC2019」珍珠。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 998244353, Inv2 = (Mod + 1) / 2;
const int G = 3, iG = 332748118;
const int MS = 1 << 18;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

inline int gInv(int b) { return qPow(b, Mod - 2); }

int Inv[MS], Fac[MS], iFac[MS];

inline void Init(int N) {
	Fac[0] = 1;
	for (int i = 1; i < N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;
	iFac[N - 1] = gInv(Fac[N - 1]);
	for (int i = N - 1; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;
	for (int i = 1; i < N; ++i) Inv[i] = (LL)Fac[i - 1] * iFac[i] % Mod;
}

int Sz, InvSz, R[MS];

inline int getB(int N) { int Bt = 0; while (1 << Bt < N) ++Bt; return Bt; }

inline void InitFNTT(int N) {
	int Bt = getB(N);
	if (Sz == (1 << Bt)) return ;
	Sz = 1 << Bt, InvSz = Mod - (Mod - 1) / Sz;
	for (int i = 1; i < Sz; ++i) R[i] = R[i >> 1] >> 1 | (i & 1) << (Bt - 1);
}

inline void FNTT(int *A, int Ty) {
	for (int i = 0; i < Sz; ++i) if (R[i] < i) std::swap(A[R[i]], A[i]);
	for (int j = 1, j2 = 2; j < Sz; j <<= 1, j2 <<= 1) {
		int wn = qPow(~Ty ? G : iG, (Mod - 1) / j2), w, X, Y;
		for (int i = 0, k; i < Sz; i += j2) {
			for (k = 0, w = 1; k < j; ++k, w = (LL)w * wn % Mod) {
				X = A[i + k], Y = (LL)w * A[i + j + k] % Mod;
				A[i + k] -= (A[i + k] = X + Y) >= Mod ? Mod : 0;
				A[i + j + k] += (A[i + j + k] = X - Y) < 0 ? Mod : 0;
			}
		}
	}
	if (!~Ty) for (int i = 0; i < Sz; ++i) A[i] = (LL)A[i] * InvSz % Mod;
}

inline void PolyConv(int *_A, int N, int *_B, int M, int *_C) {
	static int A[MS], B[MS];
	InitFNTT(N + M - 1);
	for (int i = 0; i < N; ++i) A[i] = _A[i];
	for (int i = N; i < Sz; ++i) A[i] = 0;
	for (int i = 0; i < M; ++i) B[i] = _B[i];
	for (int i = M; i < Sz; ++i) B[i] = 0;
	FNTT(A, 1), FNTT(B, 1);
	for (int i = 0; i < Sz; ++i) A[i] = (LL)A[i] * B[i] % Mod;
	FNTT(A, -1);
	for (int i = 0; i < N + M - 1; ++i) _C[i] = A[i];
}

int D, N, M;
int A[MS], B[MS], Ans;

int main() {
	scanf("%d%d%d", &D, &N, &M);
	if (M + M <= N - D) return printf("%d\n", qPow(D, N)), 0;
	if (M + M > N) return puts("0"), 0;
	Init(D + 1);
	for (int i = 0; i <= D; ++i) A[i] = (LL)qPow((D - i - i + Mod) % Mod, N) * (i & 1 ? Mod - iFac[i] : iFac[i]) % Mod;
	for (int i = 0; i <= D; ++i) B[i] = iFac[i];
	PolyConv(A, D + 1, B, D + 1, A);
	for (int i = 0; i <= D; ++i) A[i] = (LL)A[i] * Fac[D] % Mod * Fac[i] % Mod * iFac[D - i] % Mod * qPow(Inv2, i) % Mod;
	for (int i = 0; i <= D; ++i) B[D - i] = i & 1 ? Mod - iFac[i] : iFac[i];
	PolyConv(A, D + 1, B, D + 1, A);
	for (int i = 0; i <= N - M - M; ++i) Ans = (Ans + (LL)A[D + i] * iFac[i]) % Mod;
	printf("%d\n", Ans);
	return 0;
}

---

##3153. 「JOI Open 2019」三级跳

详细题解请见：JOI Open 2019 题解。

#include <cstdio>
#include <algorithm>
#include <vector>

typedef long long LL;
const int Inf = 0x3f3f3f3f;
const int MN = 500005, MQ = 500005, MS = 1 << 20 | 7;

void chkmx(LL &x, LL y) { x = x < y ? y : x; }

int N, Q;
LL A[MN];
int stk[MN], tp;
std::vector<int> V[MN], W[MN];
int qr[MQ]; LL Ans[MQ];

#define li (i << 1)
#define ri (li | 1)
#define mid ((l + r) >> 1)
#define ls li, l, mid
#define rs ri, mid + 1, r
LL v2[MS], v3[MS], tg[MS];
inline void P(int i, LL x) { chkmx(tg[i], x), chkmx(v3[i], x + v2[i]); }
inline void Pushdown(int i) { if (tg[i]) P(li, tg[i]), P(ri, tg[i]), tg[i] = 0; }
void Build(int i, int l, int r) {
	if (l == r) return v2[i] = v3[i] = A[l], void();
	Build(ls), Build(rs);
	v2[i] = v3[i] = std::max(v2[li], v2[ri]);
}
void Mdf(int i, int l, int r, int a, int b, LL x) {
	if (r < a || b < l) return ;
	if (a <= l && r <= b) return P(i, x);
	Pushdown(i), Mdf(ls, a, b, x), Mdf(rs, a, b, x);
	v3[i] = std::max(v3[li], v3[ri]);
}
LL Qur(int i, int l, int r, int a, int b) {
	if (r < a || b < l) return 0;
	if (a <= l && r <= b) return v3[i];
	Pushdown(i);
	return std::max(Qur(ls, a, b), Qur(rs, a, b));
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]);
	A[stk[tp = 1] = 0] = Inf;
	for (int i = 1; i <= N; ++i) {
		while (A[stk[tp]] < A[i]) V[stk[tp--]].push_back(i);
		if (stk[tp]) V[stk[tp]].push_back(i);
		stk[++tp] = i;
	} while (tp) --tp;
	scanf("%d", &Q);
	for (int i = 1, x; i <= Q; ++i) scanf("%d%d", &x, &qr[i]), W[x].push_back(i);
	Build(1, 1, N);
	for (int i = N - 2; i >= 1; --i) {
		for (int j : V[i]) if (j + j - i <= N) Mdf(1, 1, N, j + j - i, N, A[i] + A[j]);
		for (int j : W[i]) Ans[j] = Qur(1, 1, N, i + 2, qr[j]);
	}
	for (int i = 1; i <= Q; ++i) printf("%lld\n", Ans[i]);
	return 0;
}

---

##3154. 「JOI Open 2019」汇款

详细题解请见：JOI Open 2019 题解。

#include <cstdio>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 1000005;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}
inline int gInv(int b) { return qPow(b, Mod - 2); }

int N, A[MN], B[MN], X[MN];
int xk[MN], xb[MN];
int ok;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d%d", &A[i], &B[i]);
	ok = 1;
	for (int i = 1; i <= N; ++i) if (A[i] != B[i]) ok = 0;
	if (ok) return puts("Yes"), 0;
	xk[N] = 1, xb[N] = 0;
	for (int i = N - 1; i >= 1; --i) {
		xk[i] = 2 * xk[i + 1];
		if (xk[i] >= Mod) xk[i] -= Mod;
		xb[i] = (2ll * xb[i + 1] + B[i + 1] - A[i + 1] + Mod) % Mod;
	}
	X[N] = (2ll * xb[1] + B[1] - A[1] + Mod) * gInv((1 + 2 * (Mod - xk[1])) % Mod) % Mod;
	for (int i = 1; i < N; ++i) X[i] = ((LL)xk[i] * X[N] + xb[i]) % Mod;
	ok = 1;
	for (int i = 1; i <= N; ++i)
		if (X[(i + N - 2) % N + 1] - 2ll * X[i] != B[i] - A[i]) ok = 0;
	if (!ok) return puts("No"), 0;
	ok = 0;
	for (int i = 1; i <= N; ++i) if (B[i]) ok = 1;
	if (!ok) return puts("No"), 0;
	puts("Yes");
	return 0;
}

---

##3155. 「JOI Open 2019」病毒实验

详细题解请见：JOI Open 2019 题解。

#include <cstdio>
#include <algorithm>

const int MK = 100005, MN = 805, MS = 640005;
const char dir[5] = "NSWE";
const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int K, S[MK * 2], N, M, A[MN][MN], tim[16];
void Init() {
	static char Str[MK];
	scanf("%d%d%d%s", &K, &N, &M, Str + 1);
	for (int i = 1; i <= K; ++i)
		for (int j = 0; j < 4; ++j)
			if (Str[i] == dir[j]) S[i] = S[K + i] = j;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j) {
			scanf("%d", &A[i][j]);
			if (A[i][j] == 0) A[i][j] = 100001;
		}
	for (int d = 1; d < 16; ++d) {
		int lst = 0, mxl = 0;
		for (int i = 1; i <= 2 * K; ++i) {
			if (d >> S[i] & 1) mxl = std::max(mxl, ++lst);
			else lst = 0;
		}
		if (mxl == 2 * K) mxl = 100000;
		tim[d] = mxl;
	}
}

int bx[MN][MN], by[MN][MN], tx[MN][MN], ty[MN][MN];

int col[MN][MN], tot, qx[MS], qy[MS], lb, rb;
inline bool chk(int x, int y) {
	int stat = 0;
	for (int d = 0; d < 4; ++d) {
		int nx = x + dx[d], ny = y + dy[d];
		if (nx < 1 || nx > N || ny < 1 || ny > M) continue;
		if (col[nx][ny] == tot) stat |= 1 << d;
	}
	return A[x][y] <= tim[stat];
}
inline bool BFS(int sx, int sy) {
	if (A[sx][sy] > 100000) {
		tx[sx][sy] = sx;
		ty[sx][sy] = sy;
		rb = N * M + 1;
		return 0;
	}
	col[sx][sy] = ++tot;
	lb = rb = 1, qx[1] = sx, qy[1] = sy;
	while (lb <= rb) {
		int x = qx[lb], y = qy[lb]; ++lb;
		for (int d = 0; d < 4; ++d) {
			int nx = x + dx[d], ny = y + dy[d];
			if (nx < 1 || nx > N || ny < 1 || ny > M) continue;
			if (col[nx][ny] == tot) continue;
			if (!chk(nx, ny)) continue;
			int nbx = bx[nx][ny], nby = by[nx][ny];
			if (nbx != sx || nby != sy) {
				int ntx = tx[nbx][nby], nty = ty[nbx][nby];
				if (ntx) {
					tx[sx][sy] = ntx, ty[sx][sy] = nty;
					return 1;
				}
				tx[sx][sy] = tx[nbx][nby] = nbx;
				ty[sx][sy] = ty[nbx][nby] = nby;
				return 1;
			}
			col[nx][ny] = tot;
			++rb, qx[rb] = nx, qy[rb] = ny;
		}
	}
	tx[sx][sy] = sx;
	ty[sx][sy] = sy;
	return 0;
}

int ans, cnt;

int main() {
	Init();
	ans = N * M + 1;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			bx[i][j] = i, by[i][j] = j;
	while (1) {
		int ok = 0;
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= M; ++j)
				tx[i][j] = ty[i][j] = 0;
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= M; ++j) {
				int x = bx[i][j], y = by[i][j];
				if (tx[x][y]) continue;
				int ret = BFS(x, y);
				if (ret) ok = 1;
			}
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= M; ++j) {
				int bi = bx[i][j], bj = by[i][j];
				bx[i][j] = tx[bi][bj];
				by[i][j] = ty[bi][bj];
			}
		if (!ok) break;
	}
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			tx[i][j] = ty[i][j] = 0;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j) {
			int x = bx[i][j], y = by[i][j];
			if (tx[x][y]) continue;
			BFS(x, y);
			if (ans > rb) cnt = ans = rb;
			else if (ans == rb) cnt += rb;
		}
	printf("%d\n%d\n", ans, cnt);
	return 0;
}

---

##6268. 分拆数

写出分拆数 \(f_n\) 的普通生成函数 \(F(x)\)，可以得到：\(\displaystyle F(x)=\prod_{i=1}^{\infty}\sum_{j=1}^{\infty}x^{ij}\)。

\[\begin{aligned}\ln F(x)&=\sum_{i=1}^{\infty}\ln\sum_{j=0}^{\infty}x^{ij}\\&=\sum_{i=1}^{\infty}\ln\frac{1}{1-x^i}\\&=\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}\frac{x^{ij}}{j}\\F(x)&=\exp\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}\frac{x^{ij}}{j}\end{aligned}
\]

调和级数将系数插入多项式，最后多项式 \(\mathrm{Exp}\) 即可。复杂度 \(\mathcal{O}(n\log n)\)。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 998244353;
const int G = 3, iG = 332748118;
const int MS = 1 << 18;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

inline int gInv(int b) { return qPow(b, Mod - 2); }

int Inv[MS], Fac[MS], iFac[MS];

inline void Init(int N) {
	Fac[0] = 1;
	for (int i = 1; i < N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;
	iFac[N - 1] = gInv(Fac[N - 1]);
	for (int i = N - 1; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;
	for (int i = 1; i < N; ++i) Inv[i] = (LL)Fac[i - 1] * iFac[i] % Mod;
}

int Sz, InvSz, R[MS];

inline int getB(int N) { int Bt = 0; while (1 << Bt < N) ++Bt; return Bt; }

inline void InitFNTT(int N) {
	int Bt = getB(N);
	if (Sz == (1 << Bt)) return ;
	Sz = 1 << Bt, InvSz = Mod - (Mod - 1) / Sz;
	for (int i = 1; i < Sz; ++i) R[i] = R[i >> 1] >> 1 | (i & 1) << (Bt - 1);
}

inline void FNTT(int *A, int Ty) {
	for (int i = 0; i < Sz; ++i) if (R[i] < i) std::swap(A[R[i]], A[i]);
	for (int j = 1, j2 = 2; j < Sz; j <<= 1, j2 <<= 1) {
		int wn = qPow(~Ty ? G : iG, (Mod - 1) / j2), w, X, Y;
		for (int i = 0, k; i < Sz; i += j2) {
			for (k = 0, w = 1; k < j; ++k, w = (LL)w * wn % Mod) {
				X = A[i + k], Y = (LL)w * A[i + j + k] % Mod;
				A[i + k] -= (A[i + k] = X + Y) >= Mod ? Mod : 0;
				A[i + j + k] += (A[i + j + k] = X - Y) < 0 ? Mod : 0;
			}
		}
	}
	if (!~Ty) for (int i = 0; i < Sz; ++i) A[i] = (LL)A[i] * InvSz % Mod;
}

inline void PolyInv(int *_A, int N, int *_B) {
	static int A[MS], B[MS], tA[MS], tB[MS];
	for (int i = 0; i < N; ++i) A[i] = _A[i];
	for (int i = N, B = getB(N); i < 1 << B; ++i) A[i] = 0;
	B[0] = gInv(A[0]);
	for (int L = 1; L < N; L <<= 1) {
		int L2 = L << 1, L4 = L << 2;
		InitFNTT(L4);
		for (int i = 0; i < L2; ++i) tA[i] = A[i];
		for (int i = L2; i < Sz; ++i) tA[i] = 0;
		for (int i = 0; i < L; ++i) tB[i] = B[i];
		for (int i = L; i < Sz; ++i) tB[i] = 0;
		FNTT(tA, 1), FNTT(tB, 1);
		for (int i = 0; i < Sz; ++i) tB[i] = tB[i] * (2 - (LL)tA[i] * tB[i] % Mod + Mod) % Mod;
		FNTT(tB, -1);
		for (int i = 0; i < L2; ++i) B[i] = tB[i];
	}
	for (int i = 0; i < N; ++i) _B[i] = B[i];
}

inline void PolyLn(int *_A, int N, int *_B) {
	static int tA[MS], tB[MS];
	for (int i = 1; i < N; ++i) tA[i - 1] = (LL)_A[i] * i % Mod;
	PolyInv(_A, N - 1, tB);
	InitFNTT(N + N - 3);
	for (int i = N - 1; i < Sz; ++i) tA[i] = 0;
	for (int i = N - 1; i < Sz; ++i) tB[i] = 0;
	FNTT(tA, 1), FNTT(tB, 1);
	for (int i = 0; i < Sz; ++i) tA[i] = (LL)tA[i] * tB[i] % Mod;
	FNTT(tA, -1);
	_B[0] = 0;
	for (int i = 1; i < N; ++i) _B[i] = (LL)tA[i - 1] * Inv[i] % Mod;
}

inline void PolyExp(int *_A, int N, int *_B) {
	static int A[MS], B[MS], tA[MS], tB[MS];
	for (int i = 0; i < N; ++i) A[i] = _A[i];
	for (int i = N, B = getB(N); i < 1 << B; ++i) A[i] = 0;
	B[0] = 1;
	for (int L = 1; L < N; L <<= 1) {
		int L2 = L << 1, L4 = L << 2;
		for (int i = L; i < L2; ++i) B[i] = 0;
		PolyLn(B, L2, tA);
		InitFNTT(L4);
		for (int i = 0; i < L2; ++i) tA[i] = (!i + A[i] - tA[i] + Mod) % Mod;
		for (int i = L2; i < Sz; ++i) tA[i] = 0;
		for (int i = 0; i < L; ++i) tB[i] = B[i];
		for (int i = L; i < Sz; ++i) tB[i] = 0;
		FNTT(tA, 1), FNTT(tB, 1);
		for (int i = 0; i < Sz; ++i) tA[i] = (LL)tA[i] * tB[i] % Mod;
		FNTT(tA, -1);
		for (int i = 0; i < L2; ++i) B[i] = tA[i];
	}
	for (int i = 0; i < N; ++i) _B[i] = B[i];
}

int N, A[MS];

int main() {
	Init(MS);
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
		for (int j = i, k = 1; j <= N; j += i, ++k)
			A[j] -= (A[j] += Inv[k]) >= Mod ? Mod : 0;
	PolyExp(A, N + 1, A);
	for (int i = 1; i <= N; ++i) printf("%d\n", A[i]);
	return 0;
}

---

##6277. 数列分块入门 1

经典的使用分块或数据结构解决的问题之一。使用差分-前缀和技巧和树状数组可以通过此题。

#include <cstdio>

const int MN = 50005;

int N, A[MN], B[MN];

inline void Add(int i, int x) { for (; i <= N; i += i & -i) B[i] += x; }
inline int Qur(int i) { int a = 0; for (; i; i -= i & -i) a += B[i]; return a; }

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
		scanf("%d", &A[i]);
		Add(i, A[i] - A[i - 1]);
	}
	for (int i = 1; i <= N; ++i) {
		int opt, l, r, c;
		scanf("%d%d%d%d", &opt, &l, &r, &c);
		if (opt == 0) Add(l, c), Add(r + 1, -c);
		if (opt == 1) printf("%d\n", Qur(r));
	}
	return 0;
}

---

##6278. 数列分块入门 2

直接使用分块。

对于每一个块维护整块加的值以及这个块排序后的序列便于二分查找排名。

#include <cstdio>
#include <cmath>
#include <algorithm>

typedef long long LL;

const int MN = 50005, S = 300, D = 175;

int N, T, bel[MN], sz[D];
LL A[MN], B[MN], C[D], *st[D];

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]), B[i] = A[i];
	for (int i = 1; i <= N; ++i) bel[i] = (i - 1) / S + 1;
	T = bel[N];
	for (int i = 1; i <= T; ++i) {
		st[i] = &B[(i - 1) * S + 1];
		if (i < T) sz[i] = S;
		else sz[i] = N - (i - 1) * S;
		C[i] = 0;
		std::sort(st[i], st[i] + sz[i]);
	}
	for (int i = 1; i <= N; ++i) {
		int opt, l, r; LL c;
		scanf("%d%d%d%lld", &opt, &l, &r, &c);
		if (opt) {
			int Ans = 0;
			c *= c;
			if (bel[l] == bel[r]) {
				for (int i = l; i <= r; ++i)
					if (A[i] + C[bel[l]] < c) ++Ans;
			}
			else {
				for (int i = bel[l] + 1; i <= bel[r] - 1; ++i)
					Ans += std::lower_bound(st[i], st[i] + sz[i], c - C[i]) - st[i];
				for (int i = l; bel[i] == bel[l]; ++i)
					if (A[i] + C[bel[l]] < c) ++Ans;
				for (int i = r; bel[i] == bel[r]; --i)
					if (A[i] + C[bel[r]] < c) ++Ans;
			}
			printf("%d\n", Ans);
		}
		else {
			if (bel[l] == bel[r]) {
				for (int i = l; i <= r; ++i)
					A[i] += c;
				for (int i = (bel[l] - 1) * S + 1; i <= N && i <= bel[l] * S; ++i)
					B[i] = A[i] += C[bel[l]];
				C[bel[l]] = 0;
				std::sort(st[bel[l]], st[bel[l]] + sz[bel[l]]);
			}
			else {
				for (int i = bel[l] + 1; i <= bel[r] - 1; ++i)
					C[i] += c;
				for (int i = l; i <= N && i <= bel[l] * S; ++i)
					A[i] += c;
				for (int i = (bel[l] - 1) * S + 1; i <= N && i <= bel[l] * S; ++i)
					B[i] = A[i] += C[bel[l]];
				C[bel[l]] = 0;
				std::sort(st[bel[l]], st[bel[l]] + sz[bel[l]]);
				for (int i = (bel[r] - 1) * S + 1; i <= r; ++i)
					A[i] += c;
				for (int i = (bel[r] - 1) * S + 1; i <= N && i <= bel[r] * S; ++i)
					B[i] = A[i] += C[bel[r]];
				C[bel[r]] = 0;
				std::sort(st[bel[r]], st[bel[r]] + sz[bel[r]]);
			}
		}
	}
	return 0;
}

---

##6279. 数列分块入门 3

直接使用分块。

对于每一个块维护整块加的值以及这个块排序后的序列便于二分查找前驱。

#include <cstdio>
#include <cmath>
#include <algorithm>

typedef long long LL;

const int MN = 100005, S = 420, D = 240;

int N, T, bel[MN], sz[D];
LL A[MN], B[MN], C[D], *st[D];

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]), B[i] = A[i];
	for (int i = 1; i <= N; ++i) bel[i] = (i - 1) / S + 1;
	T = bel[N];
	for (int i = 1; i <= T; ++i) {
		st[i] = &B[(i - 1) * S + 1];
		if (i < T) sz[i] = S;
		else sz[i] = N - (i - 1) * S;
		C[i] = 0;
		std::sort(st[i], st[i] + sz[i]);
	}
	for (int i = 1; i <= N; ++i) {
		int opt, l, r; LL c;
		scanf("%d%d%d%lld", &opt, &l, &r, &c);
		if (opt) {
			LL Ans = -1;
			if (bel[l] == bel[r]) {
				for (int i = l; i <= r; ++i)
					if (A[i] + C[bel[l]] < c) Ans = std::max(Ans, A[i] + C[bel[l]]);
			}
			else {
				for (int i = bel[l] + 1; i <= bel[r] - 1; ++i) {
					int pos = std::lower_bound(st[i], st[i] + sz[i], c - C[i]) - st[i] - 1;
					if (pos >= 0) Ans = std::max(Ans, st[i][pos] + C[i]);
				}
				for (int i = l; bel[i] == bel[l]; ++i)
					if (A[i] + C[bel[l]] < c) Ans = std::max(Ans, A[i] + C[bel[l]]);
				for (int i = r; bel[i] == bel[r]; --i)
					if (A[i] + C[bel[r]] < c) Ans = std::max(Ans, A[i] + C[bel[r]]);
			}
			printf("%lld\n", Ans);
		}
		else {
			if (bel[l] == bel[r]) {
				for (int i = l; i <= r; ++i)
					A[i] += c;
				for (int i = (bel[l] - 1) * S + 1; i <= N && i <= bel[l] * S; ++i)
					B[i] = A[i] += C[bel[l]];
				C[bel[l]] = 0;
				std::sort(st[bel[l]], st[bel[l]] + sz[bel[l]]);
			}
			else {
				for (int i = bel[l] + 1; i <= bel[r] - 1; ++i)
					C[i] += c;
				for (int i = l; i <= N && i <= bel[l] * S; ++i)
					A[i] += c;
				for (int i = (bel[l] - 1) * S + 1; i <= N && i <= bel[l] * S; ++i)
					B[i] = A[i] += C[bel[l]];
				C[bel[l]] = 0;
				std::sort(st[bel[l]], st[bel[l]] + sz[bel[l]]);
				for (int i = (bel[r] - 1) * S + 1; i <= r; ++i)
					A[i] += c;
				for (int i = (bel[r] - 1) * S + 1; i <= N && i <= bel[r] * S; ++i)
					B[i] = A[i] += C[bel[r]];
				C[bel[r]] = 0;
				std::sort(st[bel[r]], st[bel[r]] + sz[bel[r]]);
			}
		}
	}
	return 0;
}

---

##6280. 数列分块入门 4

经典的使用分块或数据结构解决的问题之一。使用差分-前缀和技巧和树状数组解决。

#include <cstdio>

typedef long long LL;
const int MN = 50005;

int N;
LL b1[MN], b2[MN];
inline void Add(LL *b, int i, LL x) { for(; i <= N; i += i & -i) b[i] += x; }
inline LL Qur(LL *b, int i) { LL a = 0; for (; i; i -= i & -i) a += b[i]; return a; }

inline void Add(int l, int r, LL x) {
	Add(b1, l, x), Add(b1, r + 1, -x);
	Add(b2, l, x * l), Add(b2, r + 1, -x * (r + 1));
}
inline LL Qur(int l, int r) {
	return (r + 1) * Qur(b1, r) - Qur(b2, r) - l * Qur(b1, l - 1) + Qur(b2, l - 1);
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
		int x;
		scanf("%d", &x);
		Add(i, i, x);
	}
	for (int i = 1; i <= N; ++i) {
		int opt, l, r, c;
		scanf("%d%d%d%d", &opt, &l, &r, &c);
		if (opt) ++c, printf("%lld\n", (Qur(l, r) % c + c) % c);
		else Add(l, r, c);
	}
	return 0;
}

---

##6288. 猫咪

详细题解请见：IOI 2020 集训队作业胡扯「101, 150」：cf700E。

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MN = 200005;

struct SuffixArray {
	int N, Sig, Str[MN], SA[MN], rk[MN];
	int SA2[MN], Tmp[MN];
	int Height[MN];

	inline void RSort() {
		static int Buk[MN];
		for (int i = 1; i <= Sig; ++i) Buk[i] = 0;
		for (int i = 1; i <= N; ++i) ++Buk[rk[i]];
		for (int i = 1; i <= Sig; ++i) Buk[i] += Buk[i - 1];
		for (int i = N; i >= 1; --i) SA[Buk[rk[SA2[i]]]--] = SA2[i];
	}
	inline void BuildSA() {
		for (int i = 1; i <= N; ++i) rk[i] = Str[i], SA2[i] = i;
		rk[N + 1] = 0;
		Sig = 26, RSort();
		for (int j = 1; j < N; j <<= 1) {
			int P = 0;
			for (int i = 1; i <= j; ++i) SA2[++P] = N - j + i;
			for (int i = 1; i <= N; ++i) if (SA[i] > j) SA2[++P] = SA[i] - j;
			RSort();
			Tmp[SA[1]] = P = 1;
			for (int i = 2; i <= N; ++i) {
				if (rk[SA[i]] != rk[SA[i - 1]] || rk[SA[i] + j] != rk[SA[i - 1] + j]) ++P;
				Tmp[SA[i]] = P;
			}
			for (int i = 1; i <= N; ++i) rk[i] = Tmp[i];
			Sig = P;
			if (Sig == N) break;
		}
	}
	inline void GetHeight() {
		int k = 0;
		for (int i = 1; i <= N; ++i) {
			if (rk[i] == 1) k = Height[1] = 0;
			else {
				if (k) --k;
				int j = SA[rk[i] - 1];
				while (i + k <= N && j + k <= N && Str[i + k] == Str[j + k]) ++k;
				Height[rk[i]] = k;
			}
		}
	}

	int Lg[MN], BLCP[MN][18], Bt;
	inline void InitST() {
		Lg[0] = -1;
		for (int i = 1; i <= N; ++i) Lg[i] = Lg[i >> 1] + 1, BLCP[i][0] = Height[i];
		while (2 << Bt <= N) ++Bt;
		for (int j = 1; j <= Bt; ++j)
			for (int i = 1 << j; i <= N; ++i)
				BLCP[i][j] = std::min(BLCP[i][j - 1], BLCP[i - (1 << (j - 1))][j - 1]);
	}
	inline int LCP(int x, int y) {
		if (x == y) return N + 1;
		x = rk[x], y = rk[y];
		if (x > y) std::swap(x, y);
		int j = Lg[y - x];
		return std::min(BLCP[y][j], BLCP[x + (1 << j)][j]);
	}
	inline void GetRange(int pos, int k, int &lb, int &rb) {
		int lj = 0;
		while (pos > 1 << lj && BLCP[pos][lj] >= k) ++lj;
		for (--lj, lb = pos; lj >= 0; --lj)
			if (lb > 1 << lj && BLCP[lb][lj] >= k)
				lb -= 1 << lj;
		int rj = 0;
		while (N - pos >= 1 << rj && BLCP[pos + (1 << rj)][rj] >= k) ++rj;
		for (--rj, rb = pos; rj >= 0; --rj)
			if (N - rb >= 1 << rj && BLCP[rb + (1 << rj)][rj] >= k)
				rb += 1 << rj;
	}
} SA;

struct dat {
	int k, x;
	dat() {}
	dat(int _k, int _x) : k(_k), x(_x) {}
	void z() { k = x = 0; }
	void z(int _k, int _x) { k = _k, x = _x; }
	bool t() { return k || x; }
	friend bool operator < (dat p, dat q) {
		return p.k == q.k ? p.x > q.x : p.k < q.k;
	}
};

const int MS = 1 << 19 | 7;

int N, Ans; char Str[MN];

#define li (i << 1)
#define ri (li | 1)
#define mid ((l + r) >> 1)
#define ls li, l, mid
#define rs ri, mid + 1, r
dat val[MS]; int mnv[MS];
inline void P(int i, dat v) { val[i] = std::max(val[i], v); }
inline void Pushdown(int i) { if (val[i].t()) P(li, val[i]), P(ri, val[i]), val[i].z(); }
void Build(int i, int l, int r) {
	mnv[i] = N + 1;
	if (l == r) return val[i].z(1, 0);
	Build(ls), Build(rs);
	val[i].z();
}
void Mdf1(int i, int l, int r, int a, int b, dat v) {
	if (r < a || b < l) return ;
	if (a <= l && r <= b) return P(i, v);
	Pushdown(i);
	Mdf1(ls, a, b, v), Mdf1(rs, a, b, v);
}
dat Qur1(int i, int l, int r, int p) {
	if (l == r) return val[i];
	Pushdown(i);
	return p <= mid ? Qur1(ls, p) : Qur1(rs, p);
}
void Mdf2(int i, int l, int r, int p, int v) {
	if (l == r) return mnv[i] = v, void();
	p <= mid ? Mdf2(ls, p, v) : Mdf2(rs, p, v);
	mnv[i] = std::min(mnv[li], mnv[ri]);
}
int Qur2(int i, int l, int r, int a, int b) {
	if (r < a || b < l) return N + 1;
	if (a <= l && r <= b) return mnv[i];
	return std::min(Qur2(ls, a, b), Qur2(rs, a, b));
}

int main() {
	scanf("%s", Str + 1), SA.N = N = strlen(Str + 1);
	for (int i = 1; i <= N; ++i) SA.Str[i] = Str[i] - 'a' + 1;
	SA.BuildSA(), SA.GetHeight(), SA.InitST();
	Build(1, 1, N);
	for (int i = N; i >= 1; --i) {
		int lb, rb, len;
		dat now = Qur1(1, 1, N, SA.rk[i]);
		Ans = std::max(Ans, now.k);
		if (now.k > 1) {
			SA.GetRange(SA.rk[i], now.x, lb, rb);
			len = Qur2(1, 1, N, lb, rb) - i + now.x;
		} else len = 1;
		SA.GetRange(SA.rk[i], len, lb, rb);
		Mdf1(1, 1, N, lb, rb, dat(now.k + 1, len));
		Mdf2(1, 1, N, SA.rk[i], i);
	}
	printf("%d\n", Ans);
	return 0;
}

---

##6577. 「ICPC World Finals 2019」瓷砖

详细题解请见：ICPC World Finals 2019 题解。

#include <cstdio>
#include <algorithm>
#include <set>

const int MN = 500005;

int N, Ans1[MN], Ans2[MN];
struct dat{ int p, h, id; dat() {} dat(int h, int id) : h(h), id(id) {} } a1[MN], a2[MN];
inline bool operator <(dat i, dat j) { return i.h == j.h ? i.id < j.id : i.h < j.h; }

std::set<dat> s1, s2;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d", &a1[i].p);
	for (int i = 1; i <= N; ++i) scanf("%d", &a1[i].h);
	for (int i = 1; i <= N; ++i) scanf("%d", &a2[i].p);
	for (int i = 1; i <= N; ++i) scanf("%d", &a2[i].h);
	for (int i = 1; i <= N; ++i) a1[i].id = a2[i].id = i;
	std::sort(a1 + 1, a1 + N + 1, [](dat i, dat j) { return i.p < j.p; });
	std::sort(a2 + 1, a2 + N + 1, [](dat i, dat j) { return i.p < j.p; });
	int cnt = 0;
	for (int i = 0; i <= N; ++i) {
		if (a1[i].p != a1[i + 1].p || a2[i].p != a2[i + 1].p) {
			if (s1.size() < s2.size()) {
				for (auto j : s1) {
					auto it = s2.lower_bound(dat(j.h, 1));
					if (it != s2.begin()) {
						--it, ++cnt;
						Ans1[cnt] = j.id;
						Ans2[cnt] = it->id;
						s2.erase(it);
					}
					else return puts("impossible"), 0;
				}
				s1.clear();
			}
			else {
				for (auto j : s2) {
					auto it = s1.upper_bound(dat(j.h, N));
					if (it != s1.end()) {
						++cnt;
						Ans2[cnt] = j.id;
						Ans1[cnt] = it->id;
						s1.erase(it);
					}
					else return puts("impossible"), 0;
				}
				s2.clear();
			}
			if (a1[i].p != a1[i + 1].p)
				for (int j = i + 1; j <= N && a1[j].p == a1[i + 1].p; ++j)
					s1.insert(a1[j]);
			if (a2[i].p != a2[i + 1].p)
				for (int j = i + 1; j <= N && a2[j].p == a2[i + 1].p; ++j)
					s2.insert(a2[j]);
		}
	}
	for (int i = 1; i <= N; ++i) printf("%d ", Ans1[i]); puts("");
	for (int i = 1; i <= N; ++i) printf("%d ", Ans2[i]); puts("");
	return 0;
}

---

##6578. 「ICPC World Finals 2019」美丽的桥梁

详细题解请见：ICPC World Finals 2019 题解。

#include <cstdio>
#include <cmath>
#include <algorithm>

typedef long long LL;
const LL Inf = 0x3f3f3f3f3f3f3f3f;
const int MN = 10005;

inline LL MySqrt(LL x) {
	LL y = sqrt(x);
	while (y * y > x) --y;
	while ((y + 1) * (y + 1) <= x) ++y;
	return y;
}

int N;
LL H, Alpha, Beta;
LL px[MN], py[MN];
LL f[MN];

int main() {
	scanf("%d%lld%lld%lld", &N, &H, &Alpha, &Beta);
	for (int i = 1; i <= N; ++i) scanf("%lld%lld", &px[i], &py[i]);
	f[1] = Alpha * (H - py[1]);
	for (int i = 2; i <= N; ++i) {
		f[i] = Inf;
		LL Lb = px[i] - 2 * (H - py[i]), Rb = px[i];
		for (int j = i - 1; j >= 1; --j) {
			LL C1 = px[i] - px[j], C2 = H - py[j];
			LL Sqrt = MySqrt(8 * C1 * C2);
			LL MIN = px[i] - 2 * (C1 + C2) - Sqrt;
			LL MAX = px[i] - 2 * (C1 + C2) + Sqrt;
			if (px[i] - px[j] <= 2 * (H - py[j])) MAX = px[j];
			Lb = std::max(Lb, MIN);
			Rb = std::min(Rb, MAX);
			if (Lb <= px[j] && px[j] <= Rb)
				f[i] = std::min(f[i], f[j] + Alpha * (H - py[i]) + Beta * (px[i] - px[j]) * (px[i] - px[j]));
		}
	}
	if (f[N] != Inf) printf("%lld\n", f[N]);
	else puts("impossible");
	return 0;
}

---

##6580. 「ICPC World Finals 2019」环状 DNA

详细题解请见：ICPC World Finals 2019 题解。

#include <cstdio>
#include <vector>

inline void getStr(int &Typ, int &Idt) {
	char ch; Idt = 0;
	while ((ch = getchar()) != 'e' && ch != 's') ;
	Typ = ch == 's' ? 1 : -1, ch = getchar();
	while (Idt = Idt * 10 + (ch ^ '0'), (ch = getchar()) >= '0' && ch <= '9') ;
}

const int MN = 1000005;
const int M = 1000000;

int N;
int Ty[MN], Id[MN], S[MN], Ans[MN];
std::vector<int> G[MN];

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
		getStr(Ty[i], Id[i]),
		G[Id[i]].push_back(i);
	for (int id = 1; id <= M; ++id) {
		int Sum = 0, Mn = 0;
		for (auto i : G[id]) {
			Sum += Ty[i];
			S[i] = Sum;
			if (Mn > Sum) Mn = Sum;
		}
		if (Sum) continue;
		for (int i = 0; i < (int)G[id].size(); ++i) {
			if (S[G[id][i]] == Mn) {
				if (i < (int)G[id].size() - 1)
					++Ans[G[id][i] + 1], --Ans[G[id][i + 1] + 1];
				else {
					++Ans[G[id][i] % N + 1], --Ans[G[id][0] + 1];
					if (G[id][i] != N) ++Ans[1];
				}
			}
		}
	}
	for (int i = 1; i <= N; ++i) Ans[i] += Ans[i - 1];
	int Ai = 1, Av = Ans[1];
	for (int i = 2; i <= N; ++i)
		if (Ans[i] > Av) Ai = i, Av = Ans[i];
	printf("%d %d\n", Ai, Av);
	return 0;
}

---

##6581. 「ICPC World Finals 2019」断头路探测者

详细题解请见：ICPC World Finals 2019 题解。

#include <cstdio>
#include <algorithm>
#include <vector>

const int MN = 500005;

int N, M;
std::vector<int> G[MN];
int d[MN];

int vis[MN], que[MN], l, r;

int Ans, A1[MN], A2[MN];

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
		++d[u], ++d[v];
	}
	for (int i = 1; i <= N; ++i)
		std::sort(G[i].begin(), G[i].end());
	l = 1, r = 0;
	for (int i = 1; i <= N; ++i)
		if (d[i] == 1) vis[i] = 1, que[++r] = i;
	while (l <= r) {
		int u = que[l++];
		for (auto v : G[u]) {
			if (!vis[v] && --d[v] == 1)
				vis[v] = 1, que[++r] = v;
		}
	}
	l = 1, r = 0;
	for (int i = 1; i <= N; ++i) vis[i] = 0;
	for (int i = 1; i <= N; ++i)
		if (d[i] > 1) vis[i] = 1, que[++r] = i;
	while (l <= r) {
		int u = que[l++];
		for (auto v : G[u]) {
			if (!vis[v])
				vis[v] = 1, que[++r] = v;
		}
	}
	for (int u = 1; u <= N; ++u) {
		for (auto v : G[u]) {
			if (!vis[u] && G[u].size() == 1)
				A1[++Ans] = u, A2[Ans] = v;
			if (vis[u] && d[u] > 1 && d[v] == 1)
				A1[++Ans] = u, A2[Ans] = v;
		}
	}
	printf("%d\n", Ans);
	for (int i = 1; i <= Ans; ++i)
		printf("%d %d\n", A1[i], A2[i]);
	return 0;
}

---

##6583. 「ICPC World Finals 2019」何以伊名始

详细题解请见：ICPC World Finals 2019 题解。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

const int MN = 1000005;

int N, Q;
int h[MN], nxt[MN], to[MN], w[MN], tot;
inline void Ins(int x, int y, int z) {
	nxt[++tot] = h[x], to[tot] = y, w[tot] = z, h[x] = tot;
}

char str[MN];
int ch[MN][26], fail[MN], cnt;
inline int Insert(char *str) {
	int now = 0;
	for (int i = 0; str[i]; ++i) {
		int c = str[i] - 'A';
		if (!ch[now][c]) ch[now][c] = ++cnt;
		now = ch[now][c];
	} return now;
}

std::vector<int> G[MN];
int que[MN], l, r;
void BuildAC() {
	fail[0] = -1;
	que[l = r = 1] = 0;
	while (l <= r) {
		int u = que[l++];
		for (int j = 0; j < 26; ++j) {
			if (ch[u][j]) {
				int to = fail[u];
				while (~to && !ch[to][j]) to = fail[to];
				fail[ch[u][j]] = ~to ? ch[to][j] : 0;
				que[++r] = ch[u][j];
			}
			else ch[u][j] = ~fail[u] ? ch[fail[u]][j] : 0;
		}
	}
	for (int i = 1; i <= cnt; ++i) G[fail[i]].push_back(i);
}

int ldf[MN], rdf[MN], dfc;
void DFS0(int u) {
	ldf[u] = ++dfc;
	for (auto v : G[u]) DFS0(v);
	rdf[u] = dfc;
}

int b[MN];
inline void Mdf(int i) { for (; i <= dfc; i += i & -i) ++b[i]; }
inline int Qur(int i) { int a = 0; for (; i; i -= i & -i) a += b[i]; return a; }
void Solve(int u, int now) {
	Mdf(ldf[now]);
	for (int i = h[u]; i; i = nxt[i])
		Solve(to[i], ch[now][w[i]]);
}

int Pos[MN];

int main() {
	scanf("%d%d", &N, &Q);
	for (int i = 1; i <= N; ++i) {
		int f; char ch[3];
		scanf("%s%d", ch, &f);
		Ins(f, i, *ch - 'A');
	}
	for (int i = 1; i <= Q; ++i) {
		scanf("%s", str);
		std::reverse(str, str + strlen(str));
		Pos[i] = Insert(str);
	}
	BuildAC();
	DFS0(0);
	Solve(0, 0);
	for (int i = 1; i <= Q; ++i)
		printf("%d\n", Qur(rdf[Pos[i]]) - Qur(ldf[Pos[i]] - 1));
	return 0;
}

---

##6584. 「ICPC World Finals 2019」Hobson 的火车

详细题解请见：ICPC World Finals 2019 题解。

#include <cstdio>
#include <vector>

const int MN = 500005;

int N, K, d[MN];
int inc[MN], vis[MN], ist[MN], stk[MN], tp;

int cid, Len[MN], Id[MN];
std::vector<int> C[MN], sum[MN];

void Circ(int u) {
	stk[++tp] = u, vis[u] = tp, ist[u] = 1;
	if (!vis[d[u]]) Circ(d[u]);
	else if (ist[d[u]]) {
		++cid;
		for (int i = vis[d[u]]; i <= tp; ++i)
			C[cid].push_back(stk[i]),
			inc[stk[i]] = cid,
			Id[stk[i]] = (int)C[cid].size() - 1;
		Len[cid] = C[cid].size();
		sum[cid].resize(Len[cid]);
	}
	--tp, ist[u] = 0;
}

std::vector<int> G[MN];
int tc[MN], dep[MN], S[MN];

void DFS(int u) {
	stk[++tp] = u, dep[u] = tp;
	tc[u] = tc[d[u]];
	++S[u];
	if (tp > K + 1) --S[stk[tp - K - 1]];
	for (auto v : G[u]) DFS(v), S[u] += S[v];
	--tp;
}

int main() {
	scanf("%d%d", &N, &K);
	for (int i = 1; i <= N; ++i) scanf("%d", &d[i]);
	for (int i = 1; i <= N; ++i) if (!vis[i]) Circ(i);
	for (int i = 1; i <= N; ++i) if (!inc[d[i]]) G[d[i]].push_back(i);
	for (int i = 1; i <= N; ++i) if (inc[i]) tc[i] = i;
	for (int i = 1; i <= N; ++i) if (!inc[i] && inc[d[i]]) DFS(i);
	for (int i = 1; i <= N; ++i) {
		if (dep[i] > K) continue;
		if (K - dep[i] + 1 >= Len[inc[tc[i]]])
			++sum[inc[tc[i]]][0];
		else {
			++sum[inc[tc[i]]][Id[tc[i]]];
			int ed = (Id[tc[i]] + K - dep[i] + 1) % Len[inc[tc[i]]];
			--sum[inc[tc[i]]][ed];
			if (ed < Id[tc[i]]) ++sum[inc[tc[i]]][0];
		}
	}
	for (int id = 1; id <= cid; ++id) {
		S[C[id][0]] = sum[id][0];
		for (int i = 1; i < Len[id]; ++i)
			sum[id][i] += sum[id][i - 1],
			S[C[id][i]] = sum[id][i];
	}
	for (int i = 1; i <= N; ++i) printf("%d\n", S[i]);
	return 0;
}