2024 年 6 月做题记录

2024-06-20

题解/做题记录

14k 词

前言

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

CF1610I Mashtali vs AtCoder [**]

$\verb|tags: 博弈论|$

Green-Hackenbush：给定一张无向图，有一个根，两个人轮流操作，每次删掉一条边，然后删掉与根不连通的连通块，无法操作者输。

当图是树时即 AGC017D。结论为：

SG(u) = \mathop{\mathrm{xor}}\limits_{v \in \mathrm{son}(u)} (SG(v) + 1)

回到原问题：当有多个根时，可以把这些根缩成一个点。

Fusion Principle：在 Green-Hackenbush 中，可以把一个偶环缩成一个点，把一个奇环缩成一个点下面再挂一个点，原本环外连向环上的边都连到缩起来的点上，SG 函数值不变。

因此答案就是不在这些根所在虚树上的子树的 SG 函数的异或和再异或上虚树的边的奇偶性。

CF1515G Phoenix and Odometers [!!]

首先只能在自己的强连通分量里走，然后一个环走 $t$ 次相当于不走，因此起点并不重要，只需要关心其所在的强连通分量。

显然当且仅当该强连通分量所有环的长度与 $t$ 的 $\gcd$ 是 $s$ 的因子时才有解。

考虑抠出一些环使得它们的 $\gcd$ 是所有环的 $\gcd$ 。

我们建出正图和反图的 dfs 树，记正图上根到 $u$ 的路径长度为 $P(u)$ ，反图上是 $Q(u)$ ，然后对于每条边 $(u, v)$ ，加入 $P(u) + w(u, v) - Q(v)$ ，这样任意一个环都可以表示为其中某个子集的和。

实际上加入 $P(u) + w(u, v) - P(v)$ 也是可以的。
正确性考虑加入 $P(u) + w(u, v) + Q(v)$ 和 $P(u) + Q(u)$ 一样可以表示出任意一个环。然后对于一条边， $\gcd(P(u) + w(u, v) + Q(v), P(v) + Q(v)) = \gcd(P(u) + w(u, v) - P(v), P(v) + Q(v))$ 。然后 $P(u) + Q(u)$ 也会被某个边包括进去所以没必要加。

CF1693E Outermost Maximums [!!]

首先朴素的贪心，每次选择较小的一个操作。

然后从大到小考虑每个元素，在其左侧和右侧都出现一个更小的元素时对其进行一次操作。

给每个数打一个标记，表示左侧出现过更小的数（记为 $\text{tagL}$ ），或右侧出现过更小数（记为 $\text{tagR}$ ），或都没出现过更小数（记为 $\text{tagN}$ ）。

每次加入一个值时，设这个值最左侧和最右侧的位置为 $l, r$ ，则 $l$ 左侧的 $\text{tagN}$ 要变成 $\text{tagR}$ ， $r$ 右侧的 $\text{tagN}$ 要变成 $\text{tagL}$ 。 $l$ 右侧的 $\text{tagR}$ 和 $r$ 左侧的 $\text{tagL}$ 要进行一次操作并变成 $\text{tagN}$ 。

仔细分析可以发现标记会分成三段，一段前缀是 $\text{tagR}$ ，一段后缀是 $\text{tagL}$ ，中间是 $\text{tagN}$ 。维护标记的分界点然后分讨一下即可，需要支持单点加和区间求和，树状数组维护即可。

CF446E DZY Loves Bridges [!!!]

首先把减法变成异或。

然后就是有 $B_i = \mathrm{lowbit}(i), B_0 = 1$ ，求 $A \times B^t$ 。这里卷积是异或卷积。

直接 FWT 是 $O(n 2^n)$ 的，考虑优化。

首先对于 $B^t$ ，考虑 $B^t_m$ 的组合意义，即：对于长度为 $t$ 的序列 $a$ ，满足异或和为 $m$ ，其权值为 $\prod_{i = 1}^t \mathrm{lowbit}(a_i)$ ，求所有满足条件的序列的权值和。

考虑答案只和 $\mathrm{lowbit}$ 有关，因此如果确定一个数的 $\mathrm{lowbit}$ ，则剩下的数可以任意填，然后再确定这个数的高位即可。注意这个数的 $\mathrm{lowbit}$ 必须是整个序列里最小的。

然后写出式子：

\begin{aligned} &\sum\limits_{2^i | m} \sum\limits_{j = 1}^{t} [j \equiv m / 2^i \pmod{2}] ((n - 1 - i)2^{n - 1 - i} + \frac{1}{2^i})^{t - j} 2^{(n - 1 - i)(j - 1)} 2^{it} \binom{t}{j} \\ = &\sum\limits_{i = 0} 2^{it} ((n - 1 - i)2^{n - 1 - i} + \frac{1}{2^i})^t 2^{(i + 1 - n)} \sum\limits_{j = 1}^{t} [j \equiv m / 2^i \pmod{2}] ((n - 1 - i)2^{n - 1 - i} + \frac{1}{2^i})^{-j} 2^{(n - 1 - i)j} \binom{t}{j} \\ = &\sum\limits_{i = 0} 2^{it} ((n - 1 - i)2^{n - 1 - i} + \frac{1}{2^i})^t 2^{(i + 1 - n)} \sum\limits_{j = 1}^{t} [j \equiv m / 2^i \pmod{2}] \left(\frac{2^{(n - 1 - i)}}{(n - 1 - i)2^{n - 1 - i} + \frac{1}{2^i}}\right)^j \binom{t}{j} \\ \end{aligned}

稍微解释一下，就是 $i$ 枚举最低位 $\mathrm{lowbit}$ ，然后 $j$ 枚举有多少个数 $\mathrm{lowbit} = 2^i$ ，剩下的数可以乱填（ $\mathrm{lowbit} > 2^i$ 或值为 $0$ ），然后这 $j$ 个数里有 $j - 1$ 个高位可以乱填。

然后令后面那块东西是 $X$ ，把后面部分单独抠出来：

\sum\limits_{j = 1}^t [j \equiv m / 2^i \pmod{2}] X^j \binom{t}{j}

其组合意义就相当于有 $t$ 个球，选任意一个都会乘上 $X$ 的贡献，求选奇数 / 偶数个的贡献和，设 $f_{0 / 1}$ 表示选了奇数 / 偶数个的答案，可以矩乘优化 DP。

仔细观察这个式子容易发现答案只和 $\mathrm{lowbit}(m)$ 有关，因此只要对于每个 $i$ 和每个 $j$ 取奇偶算出答案即可，这部分复杂度是 $O(n \log t)$ 。

另外注意到模数不是质数， $X$ 的分母可能没有逆元。但是我们发现 $X$ 的分子是 $2$ 的幂次，一定有逆元，因此我们不枚举有多少个 $\mathrm{lowbit} = 2^i$ ，转而枚举有多少个 $\mathrm{lowbit} > 2^i$ 即可。

\begin{aligned} &\sum\limits_{i = 0} \sum\limits_{j = 0}^{t - 1} [t - j \equiv m / 2^i \pmod{2}] ((n - 1 - i)2^{n - 1 - i} + \frac{1}{2^i})^j 2^{(n - 1 - i)(t - j - 1)} 2^{it} \binom{t}{j} \\ = &\sum\limits_{i = 0} 2^{it} 2^{(n - 1 - i)(t - 1)} \sum\limits_{j = 0}^{t - 1} [t - j \equiv m / 2^i \pmod{2}] ((n - 1 - i)2^{n - 1 - i} + \frac{1}{2^i})^j 2^{-j(n - 1 - i)} \binom{t}{j} \\ = &\sum\limits_{i = 0} 2^{it} 2^{(n - 1 - i)(t - 1)} \sum\limits_{j = 0}^{t - 1} [t - j \equiv m / 2^i \pmod{2}] \left(\frac{(n - 1 - i)2^{n - 1 - i} + \frac{1}{2^i}}{2^{(n - 1 - i)}}\right)^j \binom{t}{j} \\ \end{aligned}

然后考虑 $A$ 和 $B^t$ 的异或卷积。由于 $B^t_i$ 只和 $\mathrm{lowbit}(i)$ 有关，记 $b_i = B^t_{2^i}$ ，则：

[x^m](A \times B^t) = \sum\limits_{i = 0}^{n - 1}b_i \sum\limits_{j = 0}^{2^n - 1} [\mathrm{lowbit}(m \oplus j) = 2^i] a_j

对 $A$ 进行蝴蝶变换，然后扔到线段树上，这样对于每个结点，一个儿子对另一个儿子的贡献乘上的 $b_i$ 是相同的，直接来即可。

// 長い夜の終わりを信じながら
// 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__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1051131, inv2 = 525566;

struct matrix {
	int mat[2][2];

	matrix() {memset(mat, 0, sizeof(mat));}
	matrix operator*(const matrix &b) const {
		matrix ans;
		for (int i = 0; i < 2; i++)
			for (int k = 0; k < 2; k++)
				for (int j = 0; j < 2; j++)
					ans.mat[i][j] = (ans.mat[i][j] + (long long)mat[i][k] * b.mat[k][j]) % mod;
		return ans;
	}
};

int n, s, a[1 << 25], b[26];
long long t;
int f[25][2], swp[1 << 25];
int ans;

int power(int a, __int128 b) {
	int ans = 1;
	while (b) {
		if (b & 1) ans = (long long)ans * a % mod;
		a = (long long)a * a % mod;
		b >>= 1;
	}
	return ans % mod;
}
matrix power(matrix a, long long b) {
	matrix ans;
	ans.mat[0][0] = ans.mat[1][1] = 1;
	while (b) {
		if (b & 1) ans = ans * a;
		a = a * a;
		b >>= 1;
	}
	return ans;
}
int sum(int l, int r) {return (a[r] - (l ? a[l - 1] : 0) + mod) % mod;}
void calc(int now, int l, int r, int h, int lzy) {
	if (l == r) {
		int val = (lzy + (long long)b[n] * sum(l, r)) % mod;
		ans ^= val;
		return ;
	}
	int lzyls = lzy, lzyrs = lzy;
	int mid = (l + r) / 2;
	lzyls = (lzyls + (long long)b[h] * sum(mid + 1, r)) % mod;
	lzyrs = (lzyrs + (long long)b[h] * sum(l, mid)) % mod;
	calc(now * 2, l, mid, h + 1, lzyls), calc(now * 2 + 1, mid + 1, r, h + 1, lzyrs);
	return ;
}

int main() {
	scanf("%d%lld%d", &n, &t, &s);
	for (int i = 0; i < s; i++) scanf("%d", &a[i]);
	for (int i = s; i < 1 << n; i++) a[i] = (101ll * a[i - s] + 10007) % mod;
	for (int i = 0; i < n; i++) {
		int aa = (long long)power(2, (__int128)i * t);
		aa = (long long)aa * power(2, (__int128)(t - 1) * (n - 1 - i)) % mod;
		int bb = ((long long)(n - 1 - i) * power(2, n - 1 - i) + power(inv2, i)) % mod;
		bb = (long long)bb * power(inv2, n - 1 - i) % mod;
		matrix c, g;
		c.mat[0][0] = 1;
		g.mat[0][0] = g.mat[1][1] = 1;
		g.mat[0][1] = g.mat[1][0] = bb;
		c = c * power(g, t);
		f[i][0] = (long long)aa * (c.mat[0][t & 1] + mod - power(bb, t)) % mod;
		f[i][1] = (long long)aa * c.mat[0][(t & 1) ^ 1] % mod;
	}
	for (int i = 0; i <= n; i++) {
		if (i < n) b[i] = f[i][1];
		else b[i] = 1;
		for (int j = 0; j < i; j++) b[i] = (b[i] + f[j][0]) % mod;
	}
	for (int i = 1; i < 1 << n; i++) {
		swp[i] = swp[i >> 1] >> 1 | (i & 1) << (n - 1);
		if (i < swp[i]) swap(a[i], a[swp[i]]);
	}
	for (int i = 1; i < 1 << n; i++) a[i] = (a[i] + a[i - 1]) % mod;
	calc(1, 0, (1 << n) - 1, 0, 0);
	printf("%d\n", ans);
	return 0;
}

洛谷 P7277 平凡点滴 [!!!]

\begin{aligned} & \sum\limits_{i = 1}^n \sum\limits_{j = 1}^n f(\gcd(i, j)) \\ =& \sum\limits_{d = 1}^n f(d) \left(2\sum\limits_{i = 1}^{\lfloor n / d\rfloor} \varphi(i) - 1\right) \end{aligned}

整除分块然后杜教筛欧拉函数的前缀和，转化成求 $f$ 的前缀和。

注意到 $g$ 只有 $O(\log V)$ 种取值，考虑枚举 $g$ 的取值 $x$ ，转化成求：

\sum\limits_{x = 1}(m - x + 1) \sum\limits_{i = 1}^n [g(i) = x] i^k

差分一下，设 $S(n, x) = \sum_{i = 1}^n [g(i) \le x] i^k$ ，就变成了求:

\sum\limits_{x = 1}(m - x + 1)(S(n, x) - S(n, x - 1))

转化成求 $S(n, x)$ 。考虑枚举某些质因子不满足要求来进行容斥：

S(n, x) = \sum\limits_{i = 1}^n \mu(i) (i^{x + 1})^k \sum\limits_{j = 1}^{\lfloor n / i^{x + 1} \rfloor} j^k

后半部分是自然数幂和，可以拉插 $O(k)$ 求出。前半部分需满足 $i^{x + 1} \le n$ ，复杂度为：

O(\sum_{i > 1} n^{\frac{1}{i}}) = O(\sqrt{n})

预处理 $f$ 前缀和的前 $O(n^{\frac{2}{3}})$ 的值，时间复杂度为 $O(k^2 + k\sqrt{n} + n^{\frac{2}{3}} \log n)$ 。

CF859F Ordering T-Shirts [!]

相当于是确定一个右部点的方案，使得对于任意选左部点的方案，都存在完美匹配。

考虑霍尔定理，由于左部点到右部点的连边是区间，因此只需要考虑右部点并为区间的子集。设左部点 $i$ 选了 $a_i$ 个，右部点 $i$ 选了 $b_i$ 个，则对于右部点区间 $[l, r]$ ，需要满足：

\sum\limits_{i = 2l - 1}^{2r - 1} a_i \le \sum\limits_{i = l}^r b_i

显然对于每个区间都要取最严的限制，因此转变成：

\min\left\{\sum\limits_{i = 2l - 1}^{2r - 1} c_i, m\right\} \le \sum\limits_{i = l}^r b_i

记 $s$ 为 $b$ 的前缀和，就变成了差分约束。只有从前往后的边，那就从前往后转移。

记 $sum_i = \sum_{j = 1}^{2i}$ ：

s_r \ge s_{l - 1} + \min\{sum_r - sum_{l - 1} - c_{2r}, m\}

显然一段后缀取前面，一段前缀取后面，找出分界点然后维护一下即可。

需要支持求前缀最小值、求后缀最小值、最后加入一个点，单调栈维护一下即可。另外发现分界点是单调的，因此可以双指针做到线性。

AGC041F Histogram Rooks [!!]

容斥，钦定 $k$ 个点没被覆盖，则容斥系数为 $(-1)^k$ 。枚举哪些列有没被覆盖的点，记为 $S$ 。

对于每一行，设其长度为 $len$ ，有 $p$ 列在 $S$ 中，则：

若该行没有未被覆盖的点，则贡献为 $2^{len - p}$ 。
若该行有未被覆盖的点，则贡献为 $\sum_{i = 1}^p \binom{p}{i} (-1)^i = -[p > 0]$ 。

但是这样不能保证 $S$ 中每一列都有没被覆盖的点，因此继续容斥，钦定 $T \subseteq S$ 满足 $T$ 中的列没有没被覆盖的点，容斥系数为 $(-1)^{|T|}$ 。

对于每一行，若有 $q$ 列在 $T$ 中，则第二部分贡献变为 $-[p > q] = -[p \ne q]$ 。

然后考虑在笛卡尔树上 DP，贡献只与 $[p = q]$ 有关而不关心 $q$ 的具体值，因此设 $f_{i, j, 0 / 1}$ 表示 $i$ 子树内 $p = j$ ，是否满足 $[p = q]$ 的答案，转移就是背包，第二维相加，第三维 $\mathrm{and}$ 起来，然后再乘上当前行的贡献即可。

CF1707D Partial Virtual Trees [!!]

设 $G(i)$ 表示答案， $F(i)$ 表示去掉相邻不同的限制时的答案，则：

F(i) = \sum\limits_{j = 1}^i \binom{i}{j} G(j) \\ G(i) = \sum\limits_{j = 1}^i (-1)^{i - j} \binom{i}{j} F(j)

转化为求 $F(j)$ 。设 $dp_{u, k}$ 表示 $u$ 子树到 $k$ 时刻还有点在集合里，且 $k + 1$ 时刻没有点在集合里的方案数。

考虑当前 $u$ 是否在集合里。

若在：

dp_{u, k} \gets \prod\limits_{v \in \mathrm{son}(u)} \sum\limits_{i = 0}^k dp_{v, i}

令 $s_u$ 为 $dp_u$ 的前缀和，可以优化到 $O(n^2)$ 。

若不在，枚举 $u$ 最后在的时刻 $p$ ，之后只有一个子树内可以有点：

dp_{u, k} \gets \sum\limits_{p = 0}^{k - 1} \sum\limits_{v \in \mathrm{son}(u)} f_{v, k} \prod\limits_{w \in \mathrm{son}(u) \land w \ne v} s_{w, p}

调换求和顺序，求出 $g_{v, k}$ 为 $\prod_{w \ne v} s_{w, k}$ 的前缀和，则：

dp_{u, k} \gets \sum\limits_{v \in \mathrm{son}(u)} dp_{v, k} g_{v, k - 1}

也可以做到 $O(n^2)$ 。

最后反演一下就可以得到答案了。

The 3rd UCup Stage1 N. (Un)labeled graphs [**+]

这个 $\lceil\log_2 n\rceil$ 个点长得就非常像是要把点的标号表示成二进制。
具体地，我们用 $n$ 个点表示原图，然后用 $\lceil\log_2 n\rceil$ 个点表示二进制下 $0 \sim \lceil\log_2 n\rceil - 1$ 位，若一个标号二进制下第 $i$ 位为 $1$ 则与对应点连边。

然后我们的目标就是用剩下三个点把原图的点和工具点区分开来。

称剩下的三个点是 $A, B, C$ ，我的构造方法是用 $A$ 连接所有原图点、工具点和 $C$ ，这样 $A$ 的度数就是 $m - 2$ ，容易发现图上只有一个这样的点，这样就可以找到 $A$ 。
然后唯一不与 $A$ 相连的点就是 $B$ ，用 $B$ 连接所有工具点即可。

这样做就可以区分原图点和工具点，还有做的就是确定工具点的顺序（即每个点代表哪一位），最直接的想法就是按顺序串成一条链，然后只要找到两个端点哪个是 $0$ 即可。
我的构造方法是让 $B$ 也与 $C$ 连边，然后 $C$ 与 $0$ 连边。唯一一个不与原图点相连的就是 $C$ ，然后就可以确定顺序了。

但是这样做有一个问题，就是当 $n = 3$ 时，工具点 $0$ 的度数也是 $m - 2$ ，因为其与原图 $n - 1$ 个点相连。解决方法就是把原图点的编号改成 0-index。

CF1637G Birthday [*]

答案一定是二的幂次。

证明考虑一个奇素数 $p$ ，在模 $p$ 意义下，对于任意两个不同时为 $0$ 的数 $x, y$ ， $x+y$ 和 $|x - y|$ 不可能同时为 $0$ 。因此最终结果一定没有奇数因子。

然后猜测下界为大于等于 $n$ 的最小的 $2$ 的次幂，尝试构造。只要把每个数都变成 $2$ 的次幂，然后用两个相同的数（一定存在）构造出一个 $0$ ，就可以通过 $0$ 实现不断乘 $2$ 了。

具体地，找到最大的 $k$ 使得 $m = 2^k \le n$ ，操作 $(n, 2m - n), (n - 1, 2m - n + 1), \ldots, (m + 1, m - 1)$ ，这样就得到了 $n - m$ 个 $2m$ 。此时没有被操作过的数有 $1 \sim 2m - n - 1$ 和 $m$ ，其中后者已经符合条件，前者是一个子问题，递归解决即可全部变为 $m$ 。被操作过的数还剩下 $2, 4, 6, \ldots, 2n - 2m$ ，求出 $1 \sim n - m$ 的解法，将每个操作中的数乘 $2$ 即可全部变为 $2m$ 。

操作次数是小常数 $O(n \log n)$ 。

CF1120F Secret Letters [+]

可以看作第一次去 R 的代价是到 $t_{n + 1}$ 的，这样每次取信再放信时放信是免费的。

因此可以得到第一次去 R 之后每次两个人交换时都一定会去 R。因此就直接确定了每封信如果要去 R 那花费是多少。

从后往前枚举第一次 R 的时间然后直接贪即可。

CF1458D Flip and Reverse [++]

$1$ 看作 $1$ ， $0$ 看作 $-1$ ，画出直线，每次操作相当于选择两个高度相等的位置，然后翻转（轴对称）中间的折线。

那就等价于每次可以在同一高度的点上任意穿梭，或者走一条边。把同一高度的点缩起来，就变成了每个点 $i$ 到 $i - 1$ 和 $i + 1$ 分别有若干条边，求字典序最小的欧拉路，直接贪即可。

CF1119G Get Ready for the Battle [**]

答案下界显然是 $\left\lceil\frac{\sum_{i = 1}^m hp_i}{n}\right\rceil$ 。直观想法就是除了最后一次每次都没有剩余。

尝试每次集火一个或两个，不妨直接按给出顺序攻击，不妨所有组按顺序攻击，那么就要满足对于任意 $1 \le i < m$ ，存在 $1 \le j \le m$ ，使得 $\sum_{k = 1}^j a_k \equiv \sum_{k = 1}^i hp_k \pmod{n}$ 。

设 $sum_i = \sum_{k = 1}^i hp_k$ ，对于 $1 \le i < m$ ，将 $sum_i \bmod n$ 从小到大排序，记为 $t$ ，令 $t_m = n$ ，然后每组人数取 $t_i - t_{i - 1}$ 即可。

CF1954F Unique Strings [!!]

考虑 Burnside，但是符合条件的串关于循环置换不封闭，于是将前 $c$ 个为 $1$ 改成存在连续 $c$ 个为 $1$ ，显然答案不变。

显然只需要关心循环位数与 $n$ 的 $\gcd$ ，设 $\ gcd = i$ 时的不动点个数为 $f_i$ ，那么答案就是：

\frac{1}{n} \sum\limits_{d = 1}^n f_{\gcd(n, d)}

考虑对于 $n$ 的每个因子 $d$ 算出 $f_d$ 。

首先特判 $c + k = n$ ，此时令 $k \gets k - 1$ 然后最终答案 $+1$ 。

问题转化成数 01 串 $s$ 使得其存在长度 $c$ 的 $1$ 连续段，且 $1$ 的个数不超过 $c + k$ ，且 $s_i = s_{i + d}$ 。

显然只需确定长度为 $d$ 的前缀，变成存在长度为 $c$ 的 $1$ 连续段且 $1$ 的个数不超过 $\frac{d(c + k)}{n}$ 。若 $d \le c$ 则需要整个串都是 $1$ ，在 $c + k < n$ 时不可能成立。

然后考虑第一个限制不好搞，于是考虑容斥，数最长 $1$ 连续段不超过 $c - 1$ 的串的个数。

设 $dp_{i, j}$ 表示长度为 $i$ ，有恰好 $j$ 个 $0$ 时的答案，枚举最后的极长 $1$ 连续段，转移方程为：

dp_{i, j} = \sum\limits_{k = 0}^{\min\{i - j, c - 1\}} dp_{i - k - 1, j - 1}

前缀和优化即可。

但是这样没办法考虑跨过首尾的串。那么枚举首尾极长 $1$ 连续段的长度就好了。

时间复杂度 $O(n^2)$ 。

分类

文章目录