2024 年 2 月做题记录

前言

会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是构造题、结论题等比较 Ad-hoc 的题，标 + 的是思维含量比较高题。根据牛牛程度会增减数量。

CF868G El Toll Caves [!!+]

$\verb|tags: 数学, 数论, 概率论|$

首先最优策略在任意时刻任意两个洞穴被查看的次数之差一定不会超过 $2$，因此可以得到最优策略是第 $i$ 论查看 $ik$ 到 $ik + k - 1$ 之间的洞穴（模 $n$ 意义下）。

然后可以发现将洞穴每 $\gcd(n, k)$ 个切一段，每段内部的洞穴没有本质区别，因此可以将 $n, k$ 都除掉 $\gcd(n, k)$。

考虑设 $f _ i$ 表示宝藏在第 $i$ 个洞穴内时查看的期望次数，则有：

$$f _ i = \begin{cases} f _ {i - k} + 1 & k \le i < n \\ \frac{1}{2} + \frac{1}{2} (f _ {i - k + n} + 1) & 0 \le i < k \end{cases}$$

由于 $n, k$ 互质，而每个 $f _ i$ 只与 $f _ {(i - k) \bmod n}$ 有关，因此可以把所有 $f _ i$ 表示成 $a f _ 0 + b$ 的形式，然后在 $f _ 0$ 处解一元一次方程即可得到答案，我们就有了一个 $O(n)$ 求 $f _ i$ 的做法，最终答案即为 $\frac{1}{n} \sum _ {i = 0} ^ {n - 1} f _ i$

然后观察一下，发现我们相当于维护一个 $i$，维护系数 $a, b$ 表示当前 $f _ i = a f _ 0 + b$，每次 $i \gets i + k$，，若此时 $\lfloor\frac{i}{k}\rfloor$ 变化，则 $a \gets a / 2, b \gets b / 2$，然后无论是否变化都执行 $b \gets b + 1$，这样执行 $n$ 次就得到了 $f _ 0$。

发现这个过程可以表示为在直线 $y = \frac{k}{n} x$ 上走，经过横线就 $/ 2$，经过竖线就 $+ 1$，这个东西显然可以用万能欧几里得优化，同时维护所有 $f _ i$ 的和就可以得到答案了。

「省选联考 2021 A/B 卷」宝石 [!!]

$\verb|tags: 图论, 树, 二分, 数据结构|$

设 $w _ i$ 在 $P$ 中的位置为 $j$，用 ${f _ 1} _ {i, k}$ 表示从 $i$ 开始向根又往后走了 $2 ^ k$ 个宝石到达的位置最深是哪里，这样可以解决询问中 $u$ 到 $lca$ 之间的部分，对于 $lca$ 到 $v$ 之间的部分，我们二分答案，然后记 ${f _ 2} _ {i, k}$ 表示从 $i$ 开始向根又往前走了 $2 ^ k$ 个宝石到达的位置最深是哪里，就可以方便地 check。

然后剩下的问题就是询问根到某个点某个值最后出现的位置，用主席树或整体二分维护一下即可。

「省选联考 2020 A 卷」作业题 [!!]

$\verb|tags: 线性代数, 矩阵树, 数学, 数论, 多项式|$

一眼矩阵树，考虑没有 $\gcd$ 怎么做，常规做法是枚举边统计删掉这条边的数量然后容斥，但是复杂度已经达到 $O(n ^ 5)$，带上 $\gcd$ 就做不了了。
想办法用乘积来表示和，发现将边权设成多项式 $w _ i x + 1$，则 $\sum w$ 就是边权乘积的一次项系数。

然后 $\gcd$ 的话由 $\varphi * 1 = \mathrm{id}$，因此：

$$\begin{aligned} & \sum\limits _ T \left(\gcd \sum\limits _ {i = 1} ^ {n - 1} w _ {e _ i}\right) \\ = & \sum\limits _ T \left(\sum\limits _ {d | \gcd}\varphi(d) \sum\limits _ {i = 1} ^ {n - 1} w _ {e _ i}\right) \\ = & \sum\limits _ {d = 1} ^ {maxw} \varphi(d) \sum\limits _ {T, \forall i, d | w _ i} \sum\limits _ {i = 1} ^ {n - 1} w _ {e _ i} \end{aligned}$$

直接枚举 $d$ 然后算即可，这样复杂度就是 $O(maxw \cdot n ^ 3)$。
只计算边数达到 $n - 1$ 的情况，就可以优化到 $O(n ^ 2 \sum \sigma _ 0 (w _ i))$。

「省选联考 2020 B 卷」丁香之路 [!++]

$\verb|tags: 图论, 欧拉回路, 构造|$

考虑添加一条 $i$ 到 $s$ 的边变成一个回路，则只要每个点的度数均为偶数且非零度点连通即可。

考虑加边解决度数的问题，首先任意一条边 $(a, b)$ 都不优于 $(a, a + 1), (a + 1, a + 2), \ldots, (b - 1, b)$。然后考虑把度数为奇数的点扣出来，相邻两个匹配显然最优。

然后考虑把所有连通块连起来，可以发现最优情况是连成最小生成树，每条树边用两次。有用的边只有 $O(n)$ 条，暴力做是对的。

Toyota Programming Contest 2023 Spring Final G Git Gud [!++]

$\verb|tags: none|$

考虑连一条边对其他边的贡献。
连一条边会使一边的连通块所有点深度 $+ 1$，则这些点未连的边的贡献都会增加 $1$，因此定义一个连通块的权值为未连的边的数量，则连接一条边会增加权值较大的连通块的权值，然后合并后新连通块的权值为原权值之和 $- 2$。
可以将每个点的初始权值设为度数 $- 2$，这样合并就不需要减了，最后额外加上 $2 n - 2$ 即可。

观察发现一定是一个点一个点加到一个大连通块里最优。因此就变成了找一个根，然后按某种顺序遍历树，遍历到一个点就加到连通块里。考虑一个点若在 $t$ 时刻加入，则其权值会贡献 $n - t$ 次。
不妨改成 $n - t + 1$ 次，最后答案再 $+ 2$ 即可。然后考虑将点向父亲合并。
对于两个连通块 $A, B$，设其答案为 $aval, bval$，权值之和为 $asum, bsum$，连通块大小为 $asiz, bsiz$，则 $A$ 在 $B$ 前的贡献为 $aval + asum \times bsiz + bval$，$B$ 在 $A$ 前的贡献为 $bval + bsum \times asiz + aval$，稍作变换可以得到 $A$ 在 $B$ 前更优当且仅当 $\frac{asum}{asiz} > \frac{bsum}{bsiz}$，也就是每次选择平均权值最大的连通块与父亲合并更优。
那么直接用堆和并查集维护并计算贡献即可。

注意一个小细节：最开始考虑贡献的时候每条边都少算了 $1$ 的贡献，因此最后要加上 $n - 1$，也就是算完后总贡献要加上 $3 n - 1$。

// Think twice, code once.
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, deg[2005], ans;
struct graph {
	int tot, hd[2005];
	int nxt[4005], to[4005];

	void add(int u, int v) {
		nxt[++tot] = hd[u];
		hd[u] = tot;
		to[tot] = v;
		return ;
	}
} g;
int fa[2005];
struct node {
	int id, val, siz;
	
	node() = default;
	node(int _id, int _val, int _siz): id(_id), val(_val), siz(_siz) {}
	bool operator<(const node &x) const {return val * x.siz < x.val * siz;}
};
struct dsu {
	int fa[2005];
	
	void clear() {for (int i = 1; i < 2005; i++) fa[i] = i; return ;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {fa[find(x)] = find(y); return ;}
} d;
int val[2005], sum[2005], siz[2005];

void dfs(int now, int F) {
	fa[now] = F;
	for (int i = g.hd[now]; i; i = g.nxt[i])
		if (g.to[i] != F) dfs(g.to[i], now);
	return ;
}
int solve(int root) {
	dfs(root, 0);
	priority_queue<node> q;
	for (int i = 1; i <= n; i++) q.emplace(i, val[i] = sum[i] = deg[i], siz[i] = 1);
	d.clear();
	while (!q.empty()) {
		node now = q.top();
		q.pop();
		if (now.id == root || d.find(now.id) != now.id) continue;
		int to = d.find(fa[now.id]);
		val[to] += sum[to] * siz[now.id] + val[now.id];
		q.emplace(to, sum[to] += sum[now.id], siz[to] += siz[now.id]);
		d.merge(now.id, to);
	}
	return val[root] + 3 * n - 1;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		u++, v++;
		g.add(u, v), g.add(v, u);
		deg[u]++, deg[v]++;
	}
	for (int i = 1; i <= n; i++) deg[i] -= 2;
	for (int i = 1; i <= n; i++) ans = max(ans, solve(i));
	printf("%d\n", ans);
	return 0;
}

「SDOI/SXOI2022」小 N 的独立集

$\verb|tags: DP, 自动机|$

设 $dp _ {u, i, j}$ 表示以 $u$ 为根的子树，不选 $u$ 的最大权独立集为 $i$，选的最大权独立集为 $j$ 时的方案数，得到一个铁过不去的做法。
考虑转换状态，不妨令一个为强制 $u$ 不选，另一个为不钦定 $u$ 的状态的值，显然强制不选的答案最多会少 $k$。这样状态数就只有 $O(n k ^ 2)$，总时间复杂度为 $O(n ^ 2 k ^ 4)$。
可以发现还是有很多位置值是 $0$，我们在转移时只枚举有值的位置即可。

「AHOI2022」排列 [!]

$\verb|tags: 数学, 数论|$

$v(P)$ 就是 $P$ 所有置换环的长度的 $\mathrm{lcm}$。

则暴力想法是考虑枚举两个置换环然后算答案。经典 Trick：和为 $n$ 的序列的数的种类数为 $O(\sqrt{n})$，可以合并相同的数使枚举的复杂度降到 $O(n)$。

剩下的问题是维护 $\mathrm{lcm}$。首先质因数分解然后对每个质数求指数的最大值。我们需要实现删两个数加一个数维护 $\mathrm{lcm}$，可以用 multiset 维护质数的指数的可重集，这样就能通过乘除快速维护 $\mathrm{lcm}$ 了，通过预处理可以使这部分复杂度变成 $O(\log ^ 2 n)$，总复杂度就是 $O(n \log ^ 2 n)$。

「LNOI2022」串 [!*+]

$\verb|tags: 字符串, 自动机, SAM|$

过程相当于一个区间 $[l, r]$，每次变成 $[l + 1, r + 2]$，然后可以跳回到之前的某个相等的区间。
考虑最后一次向前跳，发现该串至少出现两次。另一方面，任意出现至少两次的子串一定可以作为最后一次向前跳的串。
证明考虑设其出现位置为 $[a, b], [c, d]$，将跳的过程倒过来，也就是每次 $[l, r]$ 变成 $[l - 1, r - 2]$，则从 $[c, d]$ 开始，一直左移，每次碰到 $a$ 就跳回 $c$，最后就可以把串变空。

于是对于任意出现至少两次的子串，设第一次出现是 $[l, r]$，其贡献为 $r - l + 1 + \lfloor\frac{n}{2}\rfloor$，这个东西直接用 SAM 求就好了。

「省选联考 2020 A 卷」组合数问题 [!!++]

$\verb|tags: 数学, 数论, 多项式|$

先把 $f(k)$ 写成下降幂多项式的形式，设为 $f(k) = \sum _ {i = 0} ^ m b _ i k ^ {\underline{i}}$。

下降幂和组合数乘起来有一个非常好的性质：

$$\binom{n}{k} \times k ^ {\underline{i}} = \binom{n - i}{k - i} \times n ^ {\underline{i}}$$

因此：

$$\begin{aligned} & \sum\limits _ {k = 0} ^ n f(k) \times x ^ k \times \binom{n}{k} \\ = & \sum\limits _ {k = 0} ^ n \sum\limits _ {i = 0} ^ m b _ i k ^ {\underline{i}} x ^ k \binom{n}{k} \\ = & \sum\limits _ {i = 0} ^ m b _ i n ^ {\underline{i}} \sum\limits _ {k = 0} ^ n \binom{n - i}{k - i} x ^ k \\ = & \sum\limits _ {i = 0} ^ m b _ i n ^ {\underline{i}} \sum\limits _ {k = 0} ^ {n - i} \binom{n - i}{k} x ^ {k + i} \\ = & \sum\limits _ {i = 0} ^ m b _ i n ^ {\underline{i}} x ^ i \sum\limits _ {k = 0} ^ {n - i} \binom{n - i}{k} x ^ k 1 ^ {n - i - k} \\ = & \sum\limits _ {i = 0} ^ m b _ i n ^ {\underline{i}} x ^ i (x + 1) ^ {n - i} \\ \end{aligned}$$

然后只要求出 $b _ i$ 就做完了。

因为有：

$$x ^ n = \sum\limits _ {i = 0} ^ n {n \brace i} x ^ {\underline{i}}$$

因此：

$$\begin{aligned} & \sum\limits _ {i = 0} ^ m a _ i k ^ i \\ = & \sum\limits _ {i = 0} ^ m a _ i \sum\limits _ {j = 0} ^ i {i \brace j} k ^ {\underline{j}} \\ = & \sum\limits _ {i = 0} k ^ {\underline{i}} \sum\limits _ {j = i} ^ m {j \brace i} a _ j \end{aligned}$$

所以 $b _ i = \sum _ {j = i} ^ m {j \brace i} a _ j$。

直接暴力求即可。

洛谷 P8147 [JRKSJ R4] Salieri [!!]

$\verb|tags: 字符串, 自动机, ACAM, 数据结构, 二分|$

对 $s$ 建出 AC 自动机，询问就是在 AC 自动机上跑，每走到一个状态就在 fail 树上该状态到根进行 $cnt \gets cnt + 1$。

考虑到很多点的 $cnt$ 是相同的，我们对经过的点求出虚树，这样虚树上一条边上的点的 $cnt$ 都是相同的。
考虑二分答案，相当于求 $cnt _ i \times val _ i \ge mid$ 的点的数量，移项得到 $val _ i \ge \frac{mid}{cnt _ i}$。用主席树维护即可。

洛谷 P8181 「EZEC-11」Circle [++]

$\verb|tags: 数学|$

容易发现 $J _ m(i) \equiv 1 \pmod{m}$，因此我们考虑 $\frac{J _ m(i) - 1}{m}$。

可以打表发现：
将 $i$ 按 ${} \bmod (m - 1)$ 分组，其中余 $k$ 的组可以分成若干段，第 $i$ 段的长度为 $k m ^ i$， 使得每段都是首项为 $0$ 公差为 $1$ 的等差数列。

考虑证明这个东西。
首先容易得到一个关于 $J _ m$ 的递推式：

$$J _ m(n) = \begin{cases} 1 & n < m \lor J _ m(n - m + 1) = n - m + 1, \\ J _ m(n - m + 1) + m & \mathrm{otherwise.} \end{cases}$$

因此对于 $\frac{J _ m(i) - 1}{m} \ne 0$ 的位置，在按 ${} \bmod (m - 1)$ 分组后其值就等于前一项 $+ 1$。于是我们只需证 $J _ m(i) = 1$ 的位置在 ${} \bmod (m - 1) = k$ 的组中每次出现的位置为 $(\sum _ {i = 0} ^ n k m ^ i) + 1 (n \in \{-1\} \cup \mathbb{N})$。
容易归纳证明 $J _ m (i) = 1$ 当且仅当 $i = a \cdot m ^ b (1 \le a < m, b \in \mathbb{N})$，并且有 $i \equiv a \pmod{(m - 1)}$。
考虑从在分组中出现的位置反推原位置：

$$\begin{aligned} & (m - 1) \sum\limits _ {i = 0} ^ n k m ^ i + k \\ = & \sum\limits _ {i = 1} ^ {n + 1} k m ^ i - \sum\limits _ {i = 0} ^ n k m ^ i + k \\ = & k m ^ {n + 1} - k + k \\ = & k m ^ {n + 1} \end{aligned}$$

容易发现与原位置中 $J _ m(i) = 0$ 的位置是一一对应的，得证。

然后考虑知道这个后怎么求解。
以下设 ${J _ m}'(i) = \frac{J _ m(i) - 1}{m}$，我们只需要求出 ${J _ m}'(i)$ 的和，然后再 $\times m + r - l + 1$ 即可得到答案。

首先容斥成 $\sum\limits _ {i = 1} ^ r {J _ m}'(i) - \sum\limits _ {i = 1} ^ {l - 1} {J _ m}'(i)$，然后问题就是求 $\sum\limits _ {i = 1} ^ n {J _ m}'(i)$。

首先一个朴素的暴力是枚举每一组，然后每组只会分割成 $O(\log _ m n)$ 段，所以直接暴力求解，时间复杂度是 $O(m \log n)$ 的。

然后考虑从小的组到大的组的变化，容易发现每段都会增加，因此段数是单调不降的，而且由于一组的段数很少，因此可以直接暴力枚举每次段数减少的分界点。
接下来就是考虑如何求段数相同的组的总和。
设有 $cnt + 1$ 个完整的段，这些完整段的总长为 $len = \sum _ {i = 0} ^ {cnt} m ^ i$ 乘上当前组的编号。
我们首先通过容斥将问题转化成求编号为 $1$ 到 $R$ 的组的总和。

对于完整的段，其答案为：

$$\begin{aligned} & \sum\limits _ {k = 1} ^ R \sum\limits _ {i = 0} ^ {cnt} \frac{(k m ^ i - 1) k m ^ i}{2} \\ = & \frac{1}{2} \sum\limits _ {k = 1} ^ R \left(\sum\limits _ {i = 0} ^ {cnt} k ^ 2 m ^ {2 i} - \sum\limits _ {i = 0} ^ {cnt} k m ^ i\right) \\ = & \frac{1}{2} \sum\limits _ {k = 1} ^ R (k ^ 2 \cdot sqr - k \cdot len) \\ = & \frac{1}{2} \left(sqr \cdot \frac{R (R + 1) (2 R + 1)}{6} - len \cdot \frac{R (R + 1)}{2}\right) \end{aligned}$$

其中 $sqr = \sum _ {i = 0} ^ {cnt} m ^ {2 i}$。

对于余下的不完整段：

$$\begin{aligned} & \sum\limits _ {k = 1} ^ R \frac{(n - k \cdot len - 1) (n - k \cdot len)}{2} \\ = & \frac{1}{2} \sum\limits _ {k = 1} ^ R (n - 1) n - (2 n - 1) k \cdot len + k ^ 2 len ^ 2 \\ = & \frac{1}{2} \left(R (n - 1) n - \frac{R (R + 1)}{2} (2 n - 1) len + \frac{R (R + 1) (2 R + 1)}{6} len ^ 2\right) \end{aligned}$$

然后注意处理一下完整段数为 $0$ 的情况。

另外，由于组的长度有 $\left\lfloor\frac{n}{m - 1}\right\rfloor$ 和 $\left\lfloor\frac{n}{m - 1}\right\rfloor + 1$ 两种，因此如果用 $f(n, r)$ 表示只考虑 $1$ 到 $r$ 这些组，每组长度为 $n$ 时的答案，则实际的答案为 $f(\left\lfloor\frac{n}{m - 1}\right\rfloor + 1, n \bmod (m - 1)) + f(\left\lfloor\frac{n}{m - 1}\right\rfloor, m - 1) - f(\left\lfloor\frac{n}{m - 1}\right\rfloor, n \bmod (m - 1))$。

// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)mod
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 998244353;

int T;
long long m, l, r;

namespace BruteForce1 { // Brute Force & Da Biao
	int J[10000005];

	void main() {
		for (int i = 1; i <= 10000000; i++) {
			if (i <= m) {J[i] = 0; continue;}
			int pos = J[i / m + i % m];
			if (!pos && i % m) J[i] = pos + i / m;
			else J[i] = m * pos - i % m;
		}
		int ans = 0;
		for (int i = l; i <= r; i++) {
			ans = (ans + m * J[i] + 1) % mod;
		}
		printf("%lld\n", ans);
		return ;
	}
}

namespace BruteForce3 { // O(m log n)
	int calc(long long n) {
		if (!n) return 0;
		int _ = n % mod;
		int ans = 0;
		for (int i = 1; i < m; i++) {
			long long k = n / (m - 1) + (i <= n % (m - 1));
			for (long long j = i; j <= k; j *= m)
				ans = (ans + (__int128)(j - 1) * j / 2) % mod, k -= j;
			ans = (ans + (__int128)(k - 1) * k / 2) % mod;
		}
		return ((long long)m * ans + _) % mod;
	}

	void main() {
		printf("%lld\n", (calc(r) - calc(l - 1) + mod) % mod);
		return ;
	}
}

namespace Sol { // O(log n)
	int inv2 = 499122177, inv6 = 166374059;

	int sum(long long x) {x %= mod; return x * (x + 1) % mod * inv2 % mod;}
	int sqrsum(long long x) {x %= mod; return x * (x + 1) % mod * (2 * x + 1) % mod * inv6 % mod;}
	int calc(long long n, long long r) {
		int ans = 0;
		if (!n || !r) return 0;
		int cnt = 0;
		long long len = 1;
		{
			long long _n = n - 1;
			for (long long j = 1; j <= _n / m; ) j *= m, _n -= j, cnt++, len += j;
		}
		long long lst = 0;
		for (int i = cnt; lst < r && i >= 0; i--) {
			len = 0;
			long long sqr = 0;
			for (long long j = 1, k = 0; k <= i; j *= m, k++)
				len += j, sqr = (sqr + (j % mod) * (j % mod)) % mod;
			if (len > n / (lst + 1)) continue;
			long long le = min(max(lst + 1, n / len), r);
			len %= mod;
			int res = 0;
			res = (sqrsum(le) - sqrsum(lst) + mod) % mod * sqr % mod;
			res = (res - (sum(le) - sum(lst) + mod) % mod * len % mod + mod) % mod;
			res = (long long)res * inv2 % mod;
			ans = (ans + res) % mod;
			res = 0;
			res = (sqrsum(le) - sqrsum(lst) + mod) % mod * len % mod * len % mod;
			res = (res -
				(sum(le) - sum(lst) + mod) % mod * ((2 * n - 1) % mod) % mod * len % mod +
				mod) % mod;
			res = (res + (le - lst + mod) % mod * ((n - 1) % mod) % mod * (n % mod) % mod) % mod;
			res = (long long)res * inv2 % mod;
			ans = (ans + res) % mod;
			if (i == 0 && le < r)
				ans = (ans + (n - 1) % mod * (n % mod) % mod * inv2 % mod * ((r - le) % mod)) % mod;
			lst = le;
		}
		return ans;
	}
	int calc(long long n) {
		if (!n) return 0;
		int ans =
			((calc(n / (m - 1) + 1, n % (m - 1)) + calc(n / (m - 1), m - 1)) % mod +
			mod - calc(n / (m - 1), n % (m - 1))) % mod;
		return ((m % mod) * ans + n) % mod;
	}

	void main() {
		printf("%lld\n", (calc(r) - calc(l - 1) + mod) % mod);
		return ;
	}
}

signed main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld%lld", &m, &l, &r);
		Sol::main();
	}
	return 0;
}

洛谷 P9867 [POI2021~2022R2] kon [!!+]

$\verb|tags: 图论, 树, 数据结构|$

感觉很牛牛。

首先对于前两种操作连一条 $x$ 到新点的边，形成一棵以 $1$ 为根的树，记两种边分别是 $\texttt{W}$ 边和 $\texttt{Z}$ 边。

则 $x, y$ 愿意和彼此跳舞时的形状为：$x$ 向上的一条 $\texttt{Z}$ 链，往上走一条 $\texttt{W}$ 边后到达的点在 $y$ 向上的 $\texttt{Z}$ 链上，或者反过来，并且所有经过的 $\texttt{Z}$ 边都在那条 $\texttt{W}$ 边之后加入，或者交换 $x, y$ 后满足上述条件。

然后考虑将 $\texttt{Z}$ 边当作 $0$，$\texttt{W}$ 边当作 $1$，跑 01bfs，这样以某个点为根的 $\texttt{Z}$ 边连通块的 bfs 序是一个连续的区间，且一个点的连续的 $\texttt{Z}$ 边儿子的 $\texttt{Z}$ 边连通块也是一个连续的区间。

我们考虑询问，相当于是“$x$ 向上的 $\texttt{Z}$ 链上每个点，在链上边前面的 $\texttt{W}$ 边儿子的 $\texttt{Z}$ 连通块”和“往上走一条 $\texttt{W}$ 边后到达的点的 $\texttt{Z}$ 连通块里这条 $\texttt{W}$ 边之后的点”中已经被加入的点的数量。

我们考虑在修改时维护第一种的贡献，询问时解决第二种的贡献，则第一种贡献需要支持区间修改单点查询，第二种贡献需要支持单点修改区间查询，用两个树状数组维护即可。

QOJ8047 DFS Order 4 [!!]

$\verb|tags: DP|$

首先容易想到将树用儿子兄弟表示法转换成二叉树，这样不改变 dfs 序。

然后考虑在二叉树和 dfs 序之间建立映射。
具体地，我们考虑让二叉树的节点在不改变 dfs 序的情况下尽量“靠左”，也就是对于每个子树，尝试将右儿子挂到左儿子的右链上，这要求左子树的右链底要小于右子树的根。

容易证明所有满足任意子树的左子树的右链底大于右子树根的二叉树与合法的 dfs 序一一对应（只有一个儿子时我们认为其是左儿子）。问题转化成数这样的二叉树的数量。

朴素想法是设 $dp _ {i, j}$ 表示大小为 $i$ 的二叉树，右链底的值为 $j$ 时的答案，可以得到一个 $O(n ^ 5)$ 的算法。

正解就考虑容斥，数不合法的，也就是右儿子大于左子树右链底的方案数。
我们设 $dp _ {i, j}$ 表示大小为 $i$ 的树，在右链底挂了一棵大小为 $j$ 的子树，但不确定该子树结构时的方案数，转移就考虑枚举左子树大小 $x$，则不合法的方案数就是 $f _ {x, i - 1 - x + j} \times f _ {i - 1 - x, j}$，总方案数为 $f _ {x, 0} \times f _ {i - 1 - x, j} \times \binom{i - 1 + j}{x}$。也就是：

$$dp _ {i, j} = dp _ {i - 1, 0} \times \binom{i - 1 + j}{i - 1} + \sum\limits _ {x = 1} ^ {i - 2} dp _ {x, 0} \times f _ {i - 1 - x, j} \times \binom{i - 1 + j}{x} - f _ {x, i - 1 - x + j} \times f _ {i - 1 - x, j}$$

前面额外加的是只有左子树的方案。

因为根只能有左儿子，因此最终答案就是 $dp _ {n - 1, 0}$。

UOJ450 【集训队作业2018】复读机 [!!]

$\verb|tags: 多项式, 生成函数|$

可以发现答案就是 $n!}) ^ k$。

$$\begin{aligned} & \sum\limits _ {i = 0} \frac{x ^ {id}}{(id)!} \\ = & \sum\limits _ {i = 0} [d | i] \frac{x ^ i}{i!} \\ = & \sum\limits _ {i = 0} \frac{1}{d} \sum\limits _ {j = 0} ^ {d - 1} \frac{x ^ i \omega _ d ^ {ji}}{i!} \\ = & \frac{1}{d} \sum\limits _ {j = 0} ^ {d - 1} \sum\limits _ {i = 0} \frac{x ^ i \omega _ d ^ {ji}}{i!} \\ = & \frac{1}{d} \sum\limits _ {j = 0} ^ {d - 1} e ^ {x \omega _ d ^ j} \end{aligned}$$

（第二步是单位根反演）

然后 $k$ 次就使用二项式反演暴力展开：

$$\begin{aligned} & (\frac{1}{d} \sum\limits _ {j = 0} ^ {d - 1} e ^ {x \omega _ d ^ j}) ^ k \\ = & \frac{1}{d ^ k} \sum\limits _ {\sum _ {i = 0} ^ {d - 1} a _ i = k} \binom{k}{a _ 0, a _ 1, \ldots, a _ {d - 1}} e ^ {x \sum _ {i = 0} ^ {d - 1} a _ i \omega _ d ^ i} \end{aligned}$$

由于我们只要 $n$ 次项系数，因此答案就是：

$$\frac{1}{d ^ k} \sum\limits _ {\sum _ {i = 0} ^ {d - 1} a _ i = k} \binom{k}{a _ 0, a _ 1, \ldots, a _ {d - 1}} \frac{1}{n!} (\sum _ {i = 0} ^ {d - 1} a _ i \omega _ d ^ i) ^ k$$

然后 $\frac{1}{n!}$ 就和外面约掉了，剩下的部分暴力算即可。

然后提一下如何求模意义下的单位根（为啥我现在才会这个东西啊），因为可以发现原根 $g$ 是模 $mod$ 意义下的 $\omega _ {\varphi(mod)} ^ 1$，因此 $\omega _ d ^ 1 \equiv g ^ {\frac{\varphi(mod)}{d}} \equiv g ^ {\frac{1}{d}} \pmod{mod}$。

洛谷 P8544 「Wdoi-2」禁断之门对面，是此世还是彼世 [!!]

$\verb|tags: 图论, 流, DP|$

相当于有 $t$ 个点在数轴上 $m$ 个位置上走，要走 $n$ 次，在 $i$ 时刻走过第 $j$ 个点会产生 $a _ i \times b _ j$ 的代价。

首先考虑同时满足性质 A 和 B 的情况，发现当 $m$ 为偶数时是相邻两个来回走，即每次 $2 i - 1$ 走到 $2 i$，$2 i$ 走到 $2 i - 1$。当 $m$ 为奇数时则会出现一个三元环。

然后猜想当不满足 $a _ i = 1$ 时也是每个点都在两个点之间来回走，发现确实是这样，因为考虑单独一轮时求出来的就是最优解，然后来回走可以保证每次走的都是最优解。

对于每个点从起点向终点连一条边，变成 $n$ 个点连 $m$ 跳边形成若干个环或链。
这个可以费用流解决，将点拆成两个，源点向入点连边，出点向汇点连边，入点向出点连代价为从入点走到出点的代价的边。

尝试模拟费用流发现不是很能做，考虑寻找一些性质。

可以发现对于一个大小超过 $3$ 的环，可以把前两个点单独扣出来组成一个二元环，剩下的不变，答案不会变劣，因此环的大小至多为 $3$。
更进一步地，容易发现一个环或一条链上的点一定是连续的。
现在答案里只会出现相邻两个点组成的二元环，相邻三个点组成的三元环和一段连续的点组成的链。以下用 $2 - 2, 2 - 3 - 2, 1 - 2 - 2 - 1$ 来表示这三种情况（对应图形中每个点产生的代价的系数）。

设 $dp _ {i, j, 0 / 1 / 2}$ 表示前 $i$ 个点连了 $j$ 条边，第 $i$ 个点连了 $0$ 或 $1$ 或 $2$ 条边时的答案，容易得到一个 $O(n ^ 2)$ 的 DP。

由于是费用流问题，因此答案关于流量也就是边的条数是凸的，可以用 wqs 二分优化，时间复杂度 $O(n \log n)$。

实际上，可以证明除了边数为 $1$ 的情况外，凸包上的点不会有 $1 - 2 - 2 -1$。
证明就考虑如果有奇数个 $2$，如 $1 - 2 - 2 - 2 - 1$，则形成偶数条边，可以调整成若干个二元环（$2 - 2 - 2 - 2 - 0$ 或 $0 - 2 - 2 - 2 - 2$），一定有一种调整方法使答案不劣。
而如果有偶数个 $2$，如 $1 - 2 - 2 - 1$，考虑 $1 - 2 - 2 - 1$ 第一次出现（只需保证在边数 $- 1$ 的情况下没有 $1 - 2 - 2 - 1$），则边数少一条的方案是 $0 - 2 - 2 - 0$，多一条的方案是 $2 - 2 - 2 - 2$，也就是这三个点在同一条直线上，那这个点就不在凸包上。

// Think twice, code once.
#include <set>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 7;

int T, n, m, num[500005];
long long sum, a[500005], b[500005], dp[500005];

pair<long long, int> check(long long limit) {
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = dp[1] = 0;
	num[0] = num[1] = 0;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1], num[i] = num[i - 1];
		long long cost = 2 * (b[i] + b[i - 1]) - 2 * limit;
		if (dp[i - 2] + cost < dp[i] || (dp[i - 2] + cost == dp[i] && num[i - 2] + 2 > num[i]))
			dp[i] = dp[i - 2] + cost, num[i] = num[i - 2] + 2;
		if (i > 2) {
			cost = 2 * (b[i] + b[i - 1] + b[i - 2]) + b[i - 1] - 3 * limit;
			if (dp[i - 3] + cost < dp[i] || (dp[i - 3] + cost  == dp[i] && num[i - 3] + 3 > num[i]))
				dp[i] = dp[i - 3] + cost, num[i] = num[i - 3] + 3;
		}
	}
	return make_pair(dp[n], num[n]);
}

int main() {
	scanf("%d%d%d", &T, &n, &m);
	for (int i = 1; i <= T; i++) scanf("%lld", &a[i]), sum += a[i];
	sum %= mod;
	for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);
	long long l = 0, r = 3e9;
	while (l < r) {
		long long mid = (l + r) >> 1;
		if (check(mid).second >= m) r = mid;
		else l = mid + 1;
	}
	long long ans = check(r).first + m * r;
	ans = ans % mod * sum % mod;
	printf("%lld\n", ans);
	return 0;
}

「集训队互测 2012」calc [!!+]

$\verb|tags: 多项式, 拉格朗日插值|$

给我这个多项式一点不会的菜狗带来了点小小的多项式震撼。

先转成求不降序列，最后 $\times n!$。

首先容易想到一个 dp：设 $dp _ {i, j}$ 表示长度为 $i$ 的序列，考虑了前 $j$ 种数的答案，则有 $dp _ {i, j} = dp _ {i, j - 1} + jdp _ {i - 1, j - 1}$

另一方面，发现答案也等于 $[x ^ n] \prod _ {i = 1} ^ k (1 + ix)$。

然后考虑求这个东西，发现怎么求都求不出来。

发现这个东西的 $n$ 次项系数就等于 $1, 2, 3, \ldots, k$ 中选 $n$ 个乘起来，然后所有方案的结果加起来。（其实就是回到了原问题）

可以将其看作 $k - (k - 1), \ldots k - 1, k$，那么一种方案的值就是一个关于 $k$ 的 $n$ 次多项式，总共有 $\binom{k}{n} = \frac{k ^ {\underline{n}}}{n!}$ 种方案，这也是一个关于 $k$ 的 $n$ 次多项式，因此答案是一个关于 $k$ 的 $2n$ 次多项式。

我们用上面的朴素 dp 求出 $k = n \sim 3n$ 时的值，然后就可以用拉格朗日插值求出结果了。

洛谷 P5387 [Cnoi2019] 人形演舞

$\verb|tags: 博弈论, 多项式, FWT|$

结论：对于 $n = 2 ^ k + m, 0 \le m < 2 ^ k$，$SG(n) = m + 1$。

证明考虑归纳，对于任意 $n$ 可以一次操作变成 $0$。然后考虑选择的 $y$，若 $y < 2 ^ k$，则 $n \mathbin{\mathrm{xor}} y$ 取遍 $[2 ^ k, n)$，因此 $SG(n) \ge n + 1$。若 $y \ge 2 ^ k$，则 $n \mathbin{\mathrm{xor}} y = m \mathbin{\mathrm{xor}} (y - 2 ^ k)$。设 $o = 2 ^ {\lfloor\log _ 2 m\rfloor}$，则显然有 $SG(m \mathbin{\mathrm{xor}} (y - 2 ^ k)) \le o \le m$。

然后考虑设 $f _ i$ 为 $SG = i$ 的数量，则整个游戏的 $SG$ 函数值为 $i$ 的方案数为 $[x ^ i] (\sum _ {i = 0} f _ i x ^ i) ^ {|V|}$，其中多项式乘法是异或卷积。然后直接 FWT 加快速幂就行了。

洛谷 P4318 完全平方数

$\verb|tags: 数学, 数论, 筛, 二分|$

一眼二分，转化为求 $\mu ^ 2$ 的前缀和。

方法一：

令 $x _ i$ 为最大的满足 $x _ i ^ 2 \mid i$ 的数，则：

$$\begin{aligned} & \sum\limits _ {i = 1} ^ n \mu ^ 2(i) \\ = & \sum\limits _ {i = 1} ^ n [x _ i = 1] \\ = & \sum\limits _ {i = 1} \sum\limits _ {d \mid x _ i} \mu(d) \\ = & \sum\limits _ {i = 1} \sum\limits _ {d ^ 2 \mid i} \mu(d) \\ = & \sum\limits _ {i = 1} ^ {\sqrt{n}} \mu(i) \left\lfloor\frac{n}{i ^ 2}\right\rfloor \end{aligned}$$

预处理根号内的莫比乌斯函数即可，时间复杂度为 $O(T \sqrt{k} \log k)$。

方法二：

有点菜，但是感觉很高妙。

构造 $g(n) = [\exists k \in \mathbb{N _ +}, n = k ^ 2]$。

$$(\mu ^ 2 * g)(n) = \sum\limits _ {d \mid n} \mu ^ 2(d) g\left(\frac{n}{d}\right) = 1(n)$$

因此，设 $S(n) = \sum _ {i = 1} ^ n \mu ^ 2(i)$，则有：

$$\begin{aligned} S(n) = & g(1) S(n) \\ = & \sum\limits _ {i = 1} ^ n (\mu ^ 2 * g)(i) - \sum\limits _ {i = 2} ^ n g(i) S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \\ = & n - \sum\limits _ {i = 2} ^ n g(i) S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \\ = & n - \sum\limits _ {i = 2} ^ {\sqrt{n}} S\left(\left\lfloor\frac{n}{i ^ 2}\right\rfloor\right) \end{aligned}$$

然后杜教筛即可。