FeSo4OI Long Round #1 春节欢乐赛 题解合集

· · 题解

FeSo4OI Long Round #1 春节欢乐赛

A. 人字拖 / tohaai

对于与运算，当二进制中同位上的数为：

\begin{cases} 0\ \&\ 0 = 0 + 0 \\ 1\ \&\ 1 < 1 + 1 \\ 1\ \&\ 0 < 1 + 0 \end{cases}

不优于加法。

对于或运算，当二进制中同位上的数为：

\begin{cases} 0\ |\ 0 = 0 + 0 \\ 1\ |\ 1 < 1 + 1 \\ 1\ |\ 0 = 1 + 0 \end{cases}

不优于加法。

对于异或运算，当二进制中同位上的数为：

\begin{cases} 0\ \oplus\ 0 = 0 + 0 \\ 1\ \oplus\ 1 < 1 + 1 \\ 1\ \oplus\ 0 = 1 + 0 \end{cases}

不优于加法。

综上，只需输出序列和即可。

B. 树上睡觉 / sleep

睡觉操作相当于给出了一组树链剖分，而你只能沿着链往下移动。

考虑链怎么做。

首先对于 b\ge n 的跳跃操作是无用的，去掉他们。

暂时不考虑链长，设 f_i 表示上跳到 i 级祖先需要的最少时间。因为只剩相对距离的限制，所以我们可以任意改变操作序列的顺序而只需要保证下操作比上多。那么不妨把其改为若干次下上再一直往下。则有两步转移：

f_i=\min\limits_{k\in[1,m],b_k<n} f_{i-b_k+1} +2\\ f_i=\min\limits_{j>i} f_j+j-i

加入链长限制，发现除了叶子节点，其他节点上跳到 i 级祖先的最小步数就是 f_i。

具体来说，对于取到 f_i 的操作序列，我们有如下贪心操作顺序：

不难发现向上只会在叶子节点或向下操作用完后操作，而因为保证了 b_k<n,i< n 所以这样跳是不会跳出这条链的。

回到原树上，考虑对于两个点 u,v，如何计算 dis(u,v)。不难发现我们会先走到 lca，然后再一步一步往下走，转为求 dis(u,lca)。套用链的做法，令 top 为 lca 所在链的链顶，dep_u 为点 u 到最近叶子的距离，那么 dis(u,lca) 就是链长为 dep_{top} 的链的 f_{dep_{lca}-dep_u}。

把 b 排序，对于每个 [b_i,b_{i+1}) 求出 f，这样就可以快速计算了。

接着考虑怎么计算所有点对的贡献。

枚举 lca，有三种贡献：

由于叶子节点深度相同，所以给出的剖分一定是长链剖分，所以上述过程复杂度为 O(n\sqrt n)。

最终时间复杂度 O(nm+n\sqrt n) 没有刻意卡时间空间。不过实现的时候要细致一点来保持这个根号。

被爆标了。

注意到直接从下往上合并，每次合并一个轻儿子时枚举深度计算这个轻儿子子树里上来的贡献。这样做复杂度就是所有长链的长度和，即 O(n)。

总复杂度 O(nm)。

C. Soso 的模法矩阵 / modmat

题目描述

记 \{a_i\} 的前缀积数组为 A，\{b_j\} 的前缀积数组为 B。对每对 i, j 求 (A_i\bmod B_j)\bmod 998244353。

### subtask 1 答案要么是 $a_i$ 的一段前缀的积，要么是 $0$。 ### subtask 2 观察到 $15^{15}\leq 10^{18}$。暴力计算答案。 ### subtask 5 用十进制高精度计算 $A$，则 $A_i\bmod 10^j$ 可以表示为 $A$ 的低 $j$ 位。精细实现应该可以 $O(nm)$。 ### subtask 7 预期使用高精度取模通过，复杂度根据实现决定，Python 等自带高精度的语言写的程序有可能可以通过。 ### subtask 10 **维护变进制数**。从小到大枚举 $i$，时刻维护一个长为 $m+1$ 的非负整数数组 $c_i$ 使得 - 对所有 $1\leq i\leq m$，都有 $0\leq c_i<b_i$。 - $\prod_{i=1}^{i_0}a_i=\sum_{j=1}^{m+1}c_j\prod_{k=1}^{j-1}b_k$。 当 $i$ 加一时，考虑从小到大枚举 $j$，将 $c_j$ 乘上 $a_{i+1}$，若 $c_j\geq b_j$，则使 $c_{j+1}$ 加上 $\left\lfloor c_j/b_j\right\rfloor$，并将 $c_j$ 改为 $c_j\bmod b_j$。显然这样仍然满足上述的两条性质。 求解答案时，答案就是 $c_i$ 的低 $j$ 个数（$c[1..j]$）组成的变进制数对应的原数。精细实现可以在 $O(nm)$ 的时间复杂度内解决原问题。 subtask 8, 9 预留给常数较大或者需要求逆元的程序通过。 ## D. [神明的迷思 / god](https://www.luogu.com.cn/problem/T537088) 对于一个指令序列，我们设 $f(x)$（$1 \le x \le m + 1$）表示机器人从 $x$ 位置出发执行一轮后到达的位置。特别地，如果在执行的过程中坠落，那么 $f(x) = m + 1$。那么指令序列需要满足的要求就是 $f^\infty(x) \le m$。 考虑 $f(x)$ 的一些性质。首先 $f(x)$ 是单调不降的，这个是非常显然的。然后我们可以发现，设 $g(x) = f(x) - x$（$1 \le x \le m$），也就是执行一轮后位置的增量，那么 $g(x)$ 是单调不增的。这是因为，初始位置越靠左，被峭壁挡住的次数就越多，并且如果指令序列合法，那么一定存在至少一个 $x$ 使得 $g(x) = 0$。那么，$f(x)$ 一直迭代下去一定会在这个点上收敛。 那么我们考虑将一个操作序列在限制最严的那一轮统计。 1. $f(x) < x$：对于这样的操作序列，显然只有第一轮的限制是最严的，所以我们只需要对于第一轮 DP 即可。 2. $f(x) \ge x$：对于这样的操作序列，到了收敛的时候的限制是最严的，所以我们在收敛的那一轮统计这种操作序列。具体地，假设一个操作序列的 $f(k) = k$，那么对于每个 $s < k$ 的起始点，它都会收敛在 $k$ 位置。但是有多个合法的 $k$ 时这样会算重，那么我们只在最小的那个 $k$ 处统计，就是相当于在前面的基础上强制要求操作时必须要走到过 $1$ 位置。最后将 $f(s) = s$ 的情况算上即可。 那么设 $f_{i, j, 0/1}$ 表示一轮中执行了前 $i$ 个操作，目前在位置 $j$，是否走到过位置 $1$ 的方案数。对于每个起始点分别 DP 一次即可做到 $\mathcal O(nm^2)$。 实际上时间复杂度可以做到 $\mathcal O(n^3 + m)$，具体来说就是当 $m \ge n$ 时峭壁一定是没有用的。但是出题人觉得这样没必要，就没有将 $m$ 开大。 ## E. [询问 / sosoo](https://www.luogu.com.cn/problem/T724485) 假设第 $i$ 个函数复合后的二元组为 $(a_i, b_i)$，初始值为 $(a_0, b_0)$。 第一个性质：$a_{i+1}\geq a_i+i$（$b$ 同理）。 说明：因为 $a_{i+1}\geq \max(a_i+i, 2b_i-i)$。 第二个性质：$a_i\geq i(i+1)/2$（$b$ 同理）。 说明：因为 $a_0\geq 0$。 第三个性质：对于正整数 $c$，存在一个 $n$，使得对于 $N\geq n$ 都有 $a_N\geq cN$（$b$ 同理）。 说明：上一条的推论。 第四个性质：经过了足够多次操作后，设 $a\geq b$，再进行两次操作，则第二次操作等价于 $(a,b)\mapsto(2b-i,2a-i)$。 说明：我们可以假设经过了充分多的操作以至于 $b$ 充分大且第三条成立。则第一次操作后，$b_1=2a_0-n$（而不是 $b_0+n$，因为 $a_0$ 足够大使得 $a_0\geq 2n$）；$a_1$ 可能有很多取值，但我们知道下界是 $a_0+n$ 上界是 $2a_0-n$（因为 $a_0\geq b_0$）。第二次操作时，$a_2$ 肯定取 $2b_1-n-1$ 也就是 $4a_0-3n-1$ 而不是 $a_1+n$ 也就是 $2a_0+1$，显然后者太小了；$b_2$ 肯定取 $2a_1-n-1$ 即最小为 $2a_0+n-1$ 而不是 $b_1+n+1$ 也就是 $2a_0+1$，显然后者太小了。于是我们发现第二次操作都是取对方的两倍，也就是 $(a,b)\mapsto(2b-i,2a-i)$，这就证明完毕了。 第五个性质：经过了至多 $30$ 次操作后，以后的所有操作都等价于 $(a,b)\mapsto(2b-i,2a-i)$。 说明：上一条的推论。实际上这个常数怎么取都行，甚至还可以再小一点。 所以，本题的做法就是：在本题的数据范围中，可以发现经过至多 $30$ 个函数后 $\max$ 就只会取 $2b-i,2a-i$ 了，所以先暴力递推出前 $30$ 项，再用矩阵快速幂处理剩余的部分。时间复杂度 $O(T(30+\log n))$。 ## F. [二次根式 / sosqrt](https://www.luogu.com.cn/problem/T724484) 显然 $f(n)^2\times g(n)=n$。所以只需要计算 $N!$ 和 $F$ 即可。 对于 $F$ 来说，我们对每个质因子考虑。记 $\alpha_p(n)$ 是最大的 $k$ 满足 $p^k|n$。则 $$ F=\prod_{p\in\mathbb P}p^{\sum_{i=1}^n\left\lfloor\alpha_p(i)/2\right\rfloor} $$ 那么，这里只有 $\alpha_p(i)\geq 2$ 时，$i$ 会对答案有 $>1$ 的贡献。当 $p>\sqrt n$ 时，$p^2>N$，$p$ 不会有贡献，直接跳过；否则将 $\left\lfloor a/2\right\rfloor$ 写成 $\sum_{i\geq 1}[a\geq 2i]$ 的形式，答案就是 $$ \prod_{p\leq \sqrt N, p\in\mathbb P}p^{\sum_{k\geq 1}\left\lfloor N/p^{2k} \right\rfloor} $$ 计算复杂度，可以简单认为，不超过 $n$ 的质数有 $n/\ln n$，每个质数 $p$ 都需要 $\log_p n$ 的时间计算，那么我们无视对数的底，得到复杂度是 $O(\sqrt{N}/\log N \times \log N)$ 也就是 $O(\sqrt N)$。 但是复杂度的瓶颈其实是 $N!$ 的计算。由于本题 $N$ 相对来说很小，同时模数固定，故可以考虑分块打表。令 $B$ 为块长，用另一个程序算出 $B!,(2B)!,(3B)!,\cdots$ 的值，询问时用表中的值加上剩余部分即可，询问复杂度 $O(B)$。由于代码长度限制，建议取 $B=3\times 10^5$。 ## G. [字符串博弈 / bo1](https://www.luogu.com.cn/problem/T724527) 考虑 Alice 胜利条件，即选出的串无论 Bob 怎么选，总是满足出现奇数次的字符数大于一个，因为只有一个 Bob 可以把它放中间，偶数是可以放到两边的。 对于一个 Bob 有的字符，Bob 可以随意的操控它的奇偶性。所以 Alice 要选 Bob 没有的字符，且有两个奇数。 字典序贪心的话会有巨量分讨，我们不妨动态确定。 - 当前字符 Bob 有，那直接选满。 - 当前字符 Bob 没有。 - 这个字符选奇数就可以直接必胜，选 $1$ 个结束，后面都不选。 - 否则如果必须选这一个字符奇数个才能凑出两个奇数，说明这个字符是第一个奇数，那就选尽可能多。 - 否则选满。 ## H. [闪现树 / grood](https://www.luogu.com.cn/problem/T724422) 考虑闪现树的本质。我们不妨只考虑叶子节点，即忽略点 $2,3$。每次可以向下走 $1$ 深度或向下走 $2$ 深度，而走 $1$ 深度有 $1$ 种走法，走 $2$ 深度有 $4$ 种走法，走不超过 $n$ 次，深度正好为 $k$ 的方案数即为第 $k$ 层叶子节点个数。即求所有长度不超过 $n$，由 $1$ 和 $2$ 组成的序列的贡献和。设序列有 $u$ 个 $2$，则他的贡献为 $4^u$。 设 $f_i$ 表示深度为 $i$ 的叶子个数，若不考虑 $n$ 的限制，有 $f_i=f_{i-1}+4f_{i-2}$。考虑上 $n$ 的限制，我们需要减去在这一层长度超过 $n$ 的序列贡献和。那么根据上述组合意义，长 $n+1$ 和为 $i$ 的序列贡献和为 $\binom{n+1}{i-n-1}4^{i-n-1}$。 算上点 $2,3$ 我们可以算 $n-1$ 阶的 $f$，对于深度 $k$，他的答案是：$n-1$ 阶 $k$ 深叶子数 $+$ $n-1$ 阶 $k-1$ 深叶子数拓展下来的 $2,3$ 点 $+$ 恰好长 $n$ 和 $k$ 的序列贡献和。即 $f_i+2f_{i-1}+\binom{n}{i-n}4^{i-n}$。 ---- 验题人说还可以考虑用生成函数解决。 对于深度为 $x$ 的根，它会贡献 $1$ 个深度为 $x+1$ 的根，贡献 $4$ 个深度为 $x+2$ 的根。可以得出 $n$ 阶闪现树非叶子节点的根的生成函数为 $R(x)=\sum\limits_{i=0}^{n-1}(x+4x^2)^i=\frac{(x+4x^2)^n-1}{4x^2+x-1}$。 对于深度为 $x$ 的根，它会贡献 $1$ 个深度为 $x$ 的节点（自己），贡献 $2$ 个深度为 $x+1$ 的节点（两个非根儿子）。所以除叶子节点外每层的节点数的生成函数为 $R(x)(1+2x)$。 为什么要把叶子节点的根分开算？因为它们不会贡献深度为 $x+1$ 的节点，所以单独处理，把这些只会贡献自己的叶子根节点放到最后加上。与计算 $R(x)$ 的方法同理，其生成函数为 $D(x)=(x+4x^2)^n

最后得出 n 阶闪现树每层的节点数的生成函数为 F(x)=R(x)(1+2x)+D(x)。展开可以做到 O(n) 求出 n 阶闪现树每层的节点数。

g_i=[x^i](x+4x^2)^n-1=\binom{n}{i-n}4^{i-n}\\ 4f_{i-2}+f_{i-1}-f_{i}=g_i\\ f_i=4f_{i-2}+f_{i-1}-g_i=4f_{i-2}+f_{i-1}-\binom{n}{i-n}4^{i-n}\\ ans_i=f_i+2f_{i-1}+g_i

I. 雨き声残響 / ame

先不考虑结束在 (x, y) 的限制，考虑刻画合法路径的形态。可以发现，路径一定是类似以下的形式：

黄色段的情况是基本固定的，所以我们先考虑红色段和蓝色段的方案数。

红色段一定是许多“S”型拐弯拼在一起的，就像这样：

考虑设 f_{i, 0 / 1} 表示填满长度为 i 的前缀并结束于 (1, i) 或 (3, i) 的方案数，转移考虑每次延长最后一个拐弯，或者 新增一个新的拐弯，可以推出转移方程：f_{0, 0} = 1, f_{1, 1} = 1, f_{i, 0} = f_{i, 1} = f_{i - 1, 0} + f_{i - 1, 1}。当然你也可以推出 f_{i, 0} = f_{i, 1} = 2^{i - 2} (i > 1)。

蓝色段一定是许多“拱形”拼在一起的，就像这样：

每一段拱形长度都是 2，要么第一列往下拱，要么第三列往上拱。设 g_i 表示从左上进入，左下回来并填满一个长度为 i 的后缀的方案数，则 g_i 显然等于 (i \bmod 2) \times 2^{\lfloor{\frac i2}\rfloor}（即 i 是偶数时不存在合法方案）。

考虑 (x, y) 也是简单的，大概分类讨论一下：

  1. 先把 n < 3 的情况判掉。
  3. 1. 先把 $y = n$ 的情况判掉，答案显然为 $f_{n, [x = 1]}$。 2. 接下来枚举不存在黄色部分的方案数。方案数显然为 $f_{y - 1, [x = 1]}g_{n - y + 1}$。 3. 如果黄色部分存在，则长度至少为 $3$。前缀长度任意，后缀长度固定为 $n - y - 1$，方案数为 $g_{n - y - 1}\sum_{l = 0}^{y - 2} f_{l, [x = 1]}$。

预处理出 f, g 以及前缀和即可做到 \mathcal O(1) 查询，当然也可以都化简成 2^k 的形式，可做到无需预处理并 \mathcal O(\log n) 查询，但是本题对时间复杂度要求是 \mathcal O(n + T)。

J. IMAWANOKIWA (Counting ver.) / popc

首先考虑原题咋做。考虑先判断原题答案。

证明

前两个情况是显然的。先证明第三种情况的对应形式无法合成 1，可以发现如果 0 不参与操作只是相当于减少了一个 1，还是该形式；而 0 若参与操作，序列 a 就会变为第二种情况，并且只有奇数个 2，显然答案为 2。所以该情况一定只能合成 2。

再证明非对应形式一定可以合成。考虑归纳，如果我们能找到一个 0，然后将其左右两边合成，只要左右两边不都是 2，最终就可以合出 1。

假设 0 的个数大于两个，那么选择最左边的 0 即可，右边至少有两个 0，一定可以得到 1；

假设 0 的个数恰好有两个，那么序列 a 一定是 A0B0C 的形式，其中 A, B 都是不存在 0 的序列。如果 B 为 [2]，那么先将 B 和旁边一个 0 合成即可得到 A01C 的形式，该形式答案一定为 1；否则左右两个 0 肯定有一个合法。

假设 0 的个数只有一个。如果 0 两边至少有一个不是 2，那么我们就有操作空间了：当 2 有奇数个时，我们让最靠近 0 的 2 把经过的 1 都干掉，与 0 合并。否则我们直接让 0 与它旁边的那个 1 合并。假设这个 0 的左右两边都不合法，那么一定有一边至少有三个 2，我们把最靠近 0 的两个 2 合并，0 两边就至少有一个 1；否则可以直接合出 1。

这样所有情况都被考虑到了，证毕。

那么对于最小字典序，我们贪心从前往后枚举合并位置即可，如果一个位置合并时不影响答案就合并。

显然答案为 0 或 2 时合并序列均为全 1，那么我们只需要考虑答案为 1 的情况。

那么我们肯定是一直合并第一个位置，直到某个临界位置时再合并第一个位置会导致答案变大。考虑这种临界情况会有若干种（其中第一个位置可能是一个前缀一直合并第一个位置得出的）：

对于每一种分类讨论出它对应的序列并统计即可。计数是简单的，你可能需要预处理出 f_{i, j} 表示长度为 i，一直合并首位得到 j 的序列数，可能还需要处理 2 的幂次。时间复杂度为 \mathcal O(\sum n)。

K. 一千年以后 / years

考虑对每种颜色分别统计答案。

对于一种颜色，先建出虚树。发现答案是 连通块数量 - 虚点连通块数量。

前者直接点边容斥，考虑计算后者。我们考虑对于一个虚点连通块，只在深度最浅的点算贡献。

初始所有虚点都有贡献。当其能连到父亲或者子树中的实点儿子时就没有贡献了。

容易发现限制是一些区间。

考虑一个点 u 子树中的所有实点的区间限制。

现在向上合并。我们令 L=\min(u\to fa_u),R=\max(u\to fa_u)。那么就要和 [L,R] 取并。

暴力枚举所有右端点 r_i<R 的区间。容易发现取完并后这些区间右端点都变成了 R。那么我们只需要保留最左端点最大的区间即可。

对于左端点同理。

然后需要将剩下的区间扔到父亲上。

接着考虑贡献到点上。容易发现有贡献的区间就是上文中枚举出来的区间和到父亲的区间 [L,R]。那么直接用这些区间即可。

对于一个实点，向上找出第一次被修改的地方，然后挂上去就好了。

由于枚举区间个数均摊是 O(n) 的，所以总时间复杂度是 O(n\log n) 的。

对于查询，可以直接扫描线求出答案。时间复杂度 O(n\log n)。

L. 构造树的题 / tree

考虑什么时候结果最小。

我们发现对于两个点之间的 f，两个点的权值是必然算入的。所以我们考虑构造的树满足两两之间路径最大值在两端，不难发现这是答案的下界。

提供几种容易输出的方案：

  1. 一个权值有序的链
  2. 一个以最小值为根的菊花图

M. 回文回文回 IV / paliniv

可以想象一个折线图，图上有 n 个平面直角坐标系的点，第 i 个在 (i, \sum_{j\leq i}a_{p_j})，且第 i 个点和第 i+1 个点连了一条边。则题述即要求这个折线图是左右对称的，等价于这 n-1 条线关于 x=(n+1)/2 对称，则通过几何直观可以推导出：

我们只需要确定第一个数是什么，和其它数字各自和哪个数字进行匹配，再乘上 \left\lfloor (n-1)/2\right\rfloor! 即为答案。

特判：当 n 为偶数时，最中间的数字一定只能是 0，计算其贡献并剔除它。

确定第一个数：开一个桶统计每个数字的出现次数，记 c_x 是 x 的出现次数。如果存在 x>0 使得 |c_x-c_{-x}|>1，则无解。否则若存在 |c_x-c_{-x}|=1，对这样的 x 强制拿一个 x 或 -x 出来作为第一个数，计算其贡献并剔除它。若有奇数个 0，则第一个数也必须是 0， 计算其贡献并剔除它。在这一段中，如果出现两次“ 计算其贡献并剔除它”的过程，说明无解。

确定每个数字的匹配：0 需要互相匹配，首先确定哪些 0 在左边 \binom {c_0}{c_0/2}，然后让左边排好序，右边随意重排 (c_0/2)!。其它数字 x，先假设全部是 x 在左边 -x 在右边，然后让左边排好序，右边随意重排 c_x!，最后每一个匹配对考虑 x 在左边还是 -x 在左边 2^{c_x}。

至此本题可以在 O(n) 的时间复杂度内完成。

N. équinoxe / equinox

subtask 1: 20 pts

二进制暴力都可以过吧。

subtask 2: another 10 pts

菊花。

花心至多只能连 2 条边，其他的边都被断掉，所以答案是 n-3(n\ge 3)。

subtask 3: 100 pts

树形 dp。

定义 f_{i,0/1} 表示点 i 不连/连父亲，其子树需要断的边数。不连父亲意味着至多连 2 个儿子，连父亲意味着至多连 1 个儿子。贪心转移即可。时间复杂度 O(n)。

O. Soso 的期望并查集 / exsodsu

建立 Kruskal 重构树，即每次合并两棵树时，建一个虚点作为它们共同的父亲（而不是它们之一作为父亲）。然后将 x 的树根的点权上移至虚点，原来树根的点权设为 0。这样不影响 find 的代价，但可以更加方便的刻画交换操作：若有 p 的概率交换 x, y，x, y 两棵树的树根为 x, y，新建虚点为 q，那么设置新的点权 a'_q=(1-p)a_x+pa_y, a'_x=pa_x, a'_y=(1-p)a_y，在这个新的点权上做 find 操作，就能得到答案的期望。复杂度根据实现可以做到 O(n\alpha(n)), O(n\log n) 不等，都能通过。

P. 引航罗盘 / luopan

结论：

设 h 为满足 2^h\le n 的最大的非负整数，则最多能选的数的个数为：

ans=\min(2^{h},n-2^{h-1}+1)

且这些数在区间 [2^{h-1},2^{h-1}+ans-1] 中。

首先这样选出来的数一定合法的，因为 [2^{h-1},2^{h}-1] 的数 2^{h-1} 位都是 1，2^{h} 位都是 0；[2^{h},2^{h-1}+ans-1] 的数 2^{h-1} 位都是 0，2^{h} 位都是 1。这样任意两个数的异或和都满足这两位要么都是 1，要么都是 0，故一定不在 S 中。

分别证明：

Q. k-绍兴序列 / splay

条件可以直接改写为：存在 i<j 使得 a_i<ka_j，这个命题的否定是对所有 i<j 都有 a_i\geq ka_j，我们做这个反问题，然后用 (m+1)^n 减去反问题的答案得到原来的答案。

当 k=1 时，序列是单调不升的，答案是 \binom{n+m}{m}。否则可以发现序列中的非零数很少，序列前 O(\log m) 项有可能是非零的，后面的都一定是 0。我们直接以值为状态做 O(\log n) 轮 dp，前缀和优化转移，复杂度是 O(m+m/2+m/4+\cdots)=O(m)。

R. 基础想象练习题 / fantasy

subtask 1

### subtask 2 $n\leq 300, m\leq 8$。把搜索改为 dp，大概可以做到 $O(nk+n^22^m)$。 ### subtask 5 $m=1$。即所有的方案都不会因为没有字符出现而没有喜爱度。此时枚举一个造成贡献的极长子区间的长度，$O(nk)$ 或 $O(nk+n\log n)$ 地计算。 ### subtask 6 $m\leq 8$。二项式反演，钦定集合 $S$ 中的字符不出现，其它字符不管是否出现，容斥系数为 $(-1)^{|S|}$。然后整个序列被划分为若干连续段，根据 subtask 3 的做法计算方案数，这里计算一个 $S$ 的答案是 $O(n)$ 的，总时间复杂度 $O(nk+n2^m)$。 ### subtask 4 $n\leq 2000$。定义题目中的多项式代入 $n$ 的结果为 $=\sum_{k=1}^n(n-k+1)f(k)$，即反演得到一个新的确定的函数 $f(k)$，这样只需要考虑每个段而不是极长的段。枚举每个段 $[l, r]$，定义确定激活这个段（指这个区间上 $b_i=1$）以后其他字符激活的方案数 $w(l, r)$。为计算之，则定义 $S(l, r)$ 表示这个区间中的字符集合，$q(c)$ 表示不在 $[l, r]$ 中的字符 $c$ 的个数。则有 $w(l, r)=\prod_{c\in S}2^{q(c)}\cdot \prod_{c\not\in S}(2^{q(c)}-1)$。可以暴力计算，$O(nk+mn^2)$ 或 $O(nk+n^2)$。 ### subtask 7 $a_i$ 单调不降。记字符 $c$ 的出现次数 $cnt_c$，在 subtask 5 的基础上，枚举这个区间左右端点是哪两个字符 $i, j$，然后观察到这样会有 $O(c_i+c_j)$ 种长度，每一种长度里面因为 $i, j$ 字符都出现在 $S$ 中，具体 $i, j$ 有多少个不关心，只需要关心它们一共有多少个，所以每一种长度对应的 $w$ 都是一样的，而且可以递推计算。时间复杂度 $O(\sum_{i=1}^m\sum_{j=i}^m(c_i+c_j))=O(nk+mn)$。 ### subtask 9 $n\leq 200000, m\leq 50$。在 subtask 5 的基础上，考虑固定 $l$，右移 $r$ 的过程中，$S(l, r)$ 只会更改 $O(m)$ 次，将这些更改的断点记录为 $r_1, r_2, \cdots, r_m$ 表示 $r_k$ 是第一个满足 $S(l, r_{k-1})\neq S(l, r_k)$ 的 $r$，当然 $r_1=l$。对于 $r_k\leq r<r_{k+1}$ 的 $r$，可以发现 $S(l, r)$ 的前半部分每次右移都除以二。因此我们定义 $w'(l, r)=w(l, r)\cdot 2^{r-l+1}$，这样 $[r_k, r_{k+1})$ 这一段的 $w'$ 就是常数。如果最后统计了 $A_t=\sum_{l=1}^{n-t+1}w'(l, l+t-1)$，则答案就是 $\sum_{t=1}^nA_tf(t)/2^t$，而枚举 $l$ 以后若能快速维护 $w'$ 则能差分求出 $A$。 考虑已经知道 $l$ 的答案，计算 $l-1$ 的答案。则会插入一个新断点 $r_1=l$，修改 $O(m)$ 个断点的答案。都是可以计算的。总复杂度 $O(nk+n(m+\log mod))$。 ### subtask 12 可以归纳证明，若题目输入的多项式为 $f_0(x)$，则有 $f(x)=f_0(x)-2f_0(x-1)+f_0(x-2)$（边界情况 $f(1)=f_0(1), f(2)=f_0(2)-2f_0(1)$，需要特殊处理，这部分并不难）。这说明 $f(x)$ 的 $k$ 项系数可以被写出来，只需要做两次多项式平移，而这可以以 $O(k^2)$ 地完成。 仔细整理发现我们实际上只需要快速求出以下两个和式： $$ \sum_{i=1}^n\sum_{j=i}^nf(j-i+1)/2^{j-i+1} $$ $$ \sum_{i=1}^n\sum_{j=1}^mf(i+j+t)/2^{i+j+t} $$ 其中 $n, m, t$ 是参数，一共需要求值大约 $O(nm)$ 次。这个问题太困难了，考虑引入科技： $$ \sum_{i=0}^{n-1}i^{\underline k}a^i=g(n)-g(0), \quad g(x)=\frac{a^x}{a-1}\sum_{i=0}^k\left(\frac{-a}{a-1}\right)^ik^{\underline i}x^{\underline{k-i}} $$ 参考资料：[有限微积分与数列求和 - 洛谷专栏](https://www.luogu.com.cn/article/e0cvjkua) “不定和式与分部求和”一节 有了这个式子，我们将 $f(x)$ 转为下降幂，并求出对应的 $g(x)$，使 $\sum_{i=l}^{r-1}f(i)/2^i=g(r)-g(l)$。 上文的第一个式子可以转化为 $\sum_{i=1}^n(n-i+1)f(i)/2^i$，需要对 $f(x)$ 和 $xf(x)$ 进行变换。 第二个式子先对 $f(x)$ 变换使其变为 $$ \sum_{i=1}^n(g(i+m+t+1)-g(i+1+t)) $$ 注意到 $g(x)$ 也是一个下降幂多项式乘上 $(1/2)^x$ 的形式，可以对 $g(x)2^x$ 再次变换，这样就能求了。 复杂度 $O(nm(k+\log n))$ 其中 $\log n$ 是快速幂的代价，但实际上可以写光速幂去掉这个 $\log n$。 ## S. [最小生成树 / sosomst](https://www.luogu.com.cn/problem/T724489) 考虑对每个连通块维护一个下标线段树，节点上维护 $\max A, \max B, ans$。在 pushup 的时候，如果其中有一边的儿子是空的，就说明那一段都是 $B$，可以预处理这些空节点，然后拿过来之后，就有 $ans=\max(ans_l, ans_r, (\max A)_l+(\max B)_r)$。对于连通块，直接线段树合并即可。复杂度 $O(n\log n)$。 ## T. [迁跃 / clock](https://www.luogu.com.cn/problem/T724477) 考虑树形 dp，令 $f_u$ 表示从 $u$ 出发向子树内行走，最终通过迁跃回到点 $u$ 获得的最大价值减代价。考察 $u$ 的每个子树是否进入则获得： $$ f_u=\sum_{(v, w)} \max(f_v+w-k, 0) $$ 但是我们不一定要回到根，我们枚举最后停在哪个点，并钦定路上必须往这个点的方向走。考虑这个点到根的链，则需要统计的答案可以描述为： $$ \max_t(f_t+\sum_u(f_u-\max(f_v+w_{u, v}-k, 0)+w_{u, v})) $$ 其中要求 $(u, v)$ 在 $1$ 到 $t$ 的链上且 $u$ 是父亲，意思就是统计不在这条链上的子树的贡献和链的总边权。以上两个步骤均可以线性完成。 ## U. [不稳定金属锭 / powerbreak](https://www.luogu.com.cn/problem/T724488) 我们要干的事情就是对输入的序列进行 FWT，求出 $\leq p$ 的位置中最靠右的非零数。对序列建线段树，做线段树二分。每次访问到一个节点的时候，假设这个节点代表的区间为 $[l,r)$，在这一位上做 FWT（令 $k=(r-l)/2$，枚举 $i\in [l, (l+r)/2)$，将 $(a_i,a_{i+k})$ 改成 $(a_i+a_{i+k},a_i-a_{i+k})$）。 如果这时发现 $[(l+r)/2,r)$ 是全零的，那么对它继续做完剩下的 FWT 操作是没有意义的，最后还是全零，因此我们可以跳过 $[(l+r)/2,r)$ 这个区间。 否则，我们继续对这个区间做完剩下的 FWT 操作，一定会有一个非零的数。可以用反证法发现，一个全零的序列做 FWT 仍然是全零的，既然现在这个区间不是全零的，那么它做 FWT 之前一定不是全零的。 有了这些发现，我们就能确定我们往哪个节点走能得到答案。由于还有一个 $\leq p$ 的限制，我们每一层需要对最多两个线段树节点做 FWT，故总加法次数不超过 $4\times 2^n$，正常情况下应当可以通过。 ## V. [Soso 的排列 / soperme](https://www.luogu.com.cn/problem/T724482) 题解作者: @[_Acheron_](/user/984018)，有一点改动。感谢。 考虑正解的一些子问题。 假设我们得到一个排列 $p$，如何计算所有字典序小于等于它的排列的每一位的总和？ 先考虑完等于 $p$ 的排列，剩下就是字典序小于 $p$ 的排列了。 我们具象一点讨论。 看到字典序就能够想到经典套路：枚举 LIS。考虑枚举 $i$ 表示一个比 $p$ 小的排列 $q$ 在前 $i-1$ 位与 $p$ 相同，$q_i < p_i$。考虑对于每一个 $i$ 算出 $q$ 的总贡献。 假设我们枚举到 $i$ 时，对于第 $j$ 位，有三种贡献情况： 1. $j < i$。显然，因为前 $i-1$ 位都被固定了，所以 $q_j = p_j$。我们假定 $s_i$ 表示 $\sum_{j=i+1}^n[p_j < p_i]$（这个 $s$ 在后面也挺重要的），那么后 $s_i$ 个数换过到 $i$ 的位置字典序就更小了，而后 $n-i$ 位可以随便填，所以第 $j$ 位就有 $p_j s_i (n-i)!$ 的贡献。 2. $j = i$。这样第 $i$ 位可以选填后面比它小的数，所以第 $j(i)$ 位就有 $\left(\sum_{j=i+1,p_j < p_i}^n p_j \right)(n-i)!$ 的贡献。 3. $j > i$，这是最复杂的。因为第 $i$ 位挑走了一个比它小的数，所以第 $j$ 位可以被出其以外的所有数贡献，而因为有 $i+1$ 位确定了（前 $i$ 位和第 $j$ 位），共有 $(n-i-1)$ 种顺序。所以第 $j$ 位的贡献就有 $\left(\sum_{j=i+1,p_j < p_i}^n\sum_{k=i,p_j \ne p_k}^n p_k\right)(n-i-1)!$。我知道这式子有点抽象，化一下就是：令 $sp_i$ 表示 $\sum_{j=i}^n p_j$，则式子就是 $\left(\sum_{j=i+1,p_j < p_i}^n sp_i - p_j\right)(n-i-1)!$。 理论是说完了，怎么敲代码？ 拆一下贡献啊！我们不要按 $i$ 考虑，这很麻烦。我们按 $j$ 考虑，考虑有多少个 $i$ 能够贡献到 $j$。 换一换上面的式子，就能得到： 令 $ss_i$ 表示 $\sum_{j=i+1,p_j < p_i}^n p_j$。 1. $ans_j \gets \sum_{k=j+1}^n p_j s_k (n-k)!$。 2. $ans_j \gets ss_j (n-j)!$。 3. $ans_j \gets \sum_{k=1}^{j-1} (s_k sp_k - ss_k)(n-k-1)!$。 这些还是挺好树状数组维护的。 接下来考虑原问题。 如果变前变后的两个排列都在同一轮（也就是 `next_permutation` 的返回值都为真），我们只要求出最终序列 $q$ 的答案减初始序列 $p$ 的答案就行了。 如果不在同一轮的话，我们可以找到 `next_permutation` 有几次返回值为假，然后最终把每个答案加上次数乘上 $\dfrac{n(n+1)}{2}(n-1)!$ 就行了。 那么怎么找到 $q$ 呢？可以看 [P1088 的题解](https://www.luogu.com.cn/article/vb1m6qp0)。 没错 P1088 的题目内容就是求排列 $p$ 做 $k$ 次 next_permutation 后的结果。 对于排列字典序排名，我们考虑[康托展开](https://www.luogu.com.cn/problem/P5367)。 具体的说，一个排列 $p$ 的排名为 $\sum_{i=1}^n s_i (n-i)!$（从 $0$ 开始）。 然后呢，我们求出这个值，把它加上 $k$，然后通过[逆康托展开](https://www.luogu.com.cn/problem/UVA11525)还原为排列就行了。 康托展开很明显就是树状数组做一下就行了，那么什么是逆康托展开呢？如何通过 $s$ 数组还原排列 $p$ 呢？ 这个简单，从小到大看 $p$ 的第 $i$ 位，并维护一个集合 $S = \{1,2\dots n\}$。每次令 $p_i$ 为集合 $S$ 的第 $s_i + 1$ 大数，并把它从集合里删除就行。 维护第 $k$ 大可以用树状数组二分，不会[来学](https://www.cnblogs.com/userLCX/articles/17808302.html)，复杂度只有一只 $\log$，比直接二分好。 想求出排列 $q$ 还有一个问题，就是康托展开后的结果太大了，根本存不下啊！ 有一个解决方案，就是我们不用 $10$ 进制存。 显然的，$0 \le s_i < n-i+1$，且 $x!$ 是 $(x-1)!$ 的倍数（废话），所以我们可以把 $\sum_{i=1}^n s_i (n-i)!$ 看成一个“$s$ 进制数”，最高位是 $s_1$，最低位是 $s_n$，第 $i$ 到第 $i+1$ 位是 $n-i+1$，满足满 $n-i+1$ 向前进一的规则。 于是我们就可以用类似高精度加法的方式求出 $q$ 的 $s$ 数组，再逆康托展开，求出 $q$，然后套用上述方法就做完了。 顺带一提，有一个方便的地方，就是 $s_0$ 的值就是 `next_permutation` 返回值为假的次数。 有一个实现细节，就是只算一部分的答案（只算 $p$ 的贡献而没有加上 $q$ 的贡献）太大了，可以用 `unsigned long long` 存储。因为答案不到 $2^{64}$，所以取模后结果仍是对的。 然后整道题就全部做完了，总体复杂度是 $O(n \log n)$ 的。 顺带一提，**对因为 $k$ 太小导致存在 $O(n+15^2)$ 的方法而表示不满**，建议出题人加强这题！（用排列排名表示 $k$ 的方法就非常好） 代码其实能够很简短，以下代码有很多重复部分，一点都没有亚航，仍能在 $80$ 行以内解决。速度还很快，比 std 快多了。 ## W. [幻影之春 / phantom](https://www.luogu.com.cn/problem/T724456) 经典数学签到题，先把式子变个形。 $$ \sum_{i=1}^n \lfloor \sqrt{i} \rfloor=\sum_{i=1}^n \sum_{j=1}^n [j^2 \le i] $$ 考虑交换求和顺序。 $$ \displaystyle \sum_{i=1}^n \sum_{j=1}^n [j^2 \le i]=\sum_{j=1}^n \sum_{i=1}^n [j^2 \le i] $$ 再把内层求和展开。记 $a=\lfloor \sqrt{n} \rfloor$。 $$ \sum_{j=1}^n \sum_{i=1}^n [j^2 \le i]=\sum_{j=1}^{a} (n-j^2+1)=(n+1)a-\sum_{j=1}^a j^2 $$ 使用公式 $\displaystyle \sum_{j=1}^a j^2 =\dfrac{a(a+1)(2a+1)}{6}$ 计算即可。时间复杂度 $O(1)$。注意要开 `__int128`。 ## X. [关于最大公约数的又一个问题 / gcd](https://www.luogu.com.cn/problem/T724425) $F(l,r)$ 即最大的 $d$ 满足区间 $[l,r]$ 中存在多于一个数是 $d$ 的倍数。 如何计算 $\sum_{r\in[l+1,n]} F(l,r)$？我们可以先枚举 $d$ 计算 $F(l,n)$，然后对于 $F(l,r)$ 考虑继承 $F(l,r+1)$。我们发现任意 $l,r$ 必然满足 $F(l,r) \leq F(l,r+1)$，因为在 $[l,r]$ 合法的 $d$ 在 $[l+1,r]$ 也合法。但是在 $[l+1,r]$ 合法的 $d$ 在 $[l,r]$ 不一定合法。所以我们还要不停的检查当前的 $d$ 是否合法，如果不合法就要把 $d$ 减一再检查。 时间复杂度 $O(F(l,n))=O(n)$。 ---- 剪枝是保留值不同的 $F(l,n)$，这样实测可以跑 $1e9$。但是我不会证明这个东西的上界。 ## Y. [浙江旅行团 / hangzhou](https://www.luogu.com.cn/problem/T724486) 不用持久化时，我们用颜色段均摊的想法，配合一些动态开点线段树就可以完成了。（可能可以看一下 P9320 这道题？） 要求持久化时，则需要分别解决这两个部分。颜色段均摊直接抛弃，改成线段树的区间覆盖即可。我们想象，对于一个机器人，我们打在他身上的是一堆形如 $(t,u)$ 的操作，表示在 $t$ 时刻这个机器人走到城市 $u$。将操作打包称为操作包，记录第一个操作和最后一个操作，以及总共产生的评分；那么两个操作包合并的时候，只需要计算前一个的最后一个和后一个的第一个的贡献即可。 现在，两个操作对应的时刻之间，我们需要计算某个城市举行的活动的矩阵积，一共 $O(n\log n)$ 次，而且强制在线。而对于这个计算任务，原本是动态开点线段树解决的，现在相当于是上树了，我们对每个城市的修改建类似于虚树的东西，我们将到修改城市 $c$ 的版本，连一条边到离它最近的修改城市 $c$ 的祖先上去，这样我们发出计算任务的时候就能做树上倍增。而找到这个最近的祖先，我们用持久化线段树记录每个城市对应的最近祖先即可。总复杂度 $O(n\log^2n)$。 ## Z. [前缀和与差分 / coprime](https://www.luogu.com.cn/problem/T724492) 参考资料：[数论柿子题的发现](https://masterhuang.blog.uoj.ac/blog/9279) 设 $h(x)$ 为一个数论函数满足 $\sum_{d|n}h(d)=n^2$，那么答案为： $$ f(n, m)=\sum_{\{a_i\}}\sum_{d|a_1, d|a_2, \cdots, d|a_n}h(d)=\sum_{d=1}^mh(d)\left\lfloor{m/d}\right\rfloor^n $$ 设 $g(x)=x^n-(x-1)^n$，则 $$ \begin{aligned} f(n, m)&=\sum_{d=1}h(d)\sum_{i=1}^{\left\lfloor{m/d}\right\rfloor}g(i)\\ &=\sum_{d=1}h(d)\sum_{id\leq m}g(i)\\ &=\sum_{id\leq m}h(d)g(i)\\ &=\sum_{t=1}^m\sum_{d|t}h(d)g(t/d) \end{aligned} $$ 也就是说 $f(n, m)$ 为 $h*g$ 这个函数的前 $m$ 项和。只需要求出 $h*g$ 的前 $m$ 项点值就能解决原问题了。 可以发现，$h=\text{Id}_2/\text{I}=\text{Id}_2*\mu$ 为积性函数，可以线性筛；$g$ 可以先线性筛出 $\text{Id}_n$ 再做差分，将它们直接做狄利克雷卷积，复杂度为 $O(m\log m)$。还有其它很多做法能到这个复杂度，所以分数没有给太多。 正解是尝试优化这个狄利克雷卷积，虽然结果不是积性函数，但是因为其中一方是积性函数，我们可以尝试模仿狄利克雷前缀和。 设 $p_1, p_2, \cdots, p_{cnt}$ 是不超过 $m$ 的所有素数，将 $h$ 分解为 $\prod_{i=1}^{cnt}H_i$，其中乘法是狄利克雷卷积，$H_i(p_i^\alpha)=h(p_i^\alpha)$，其它位置全为 $0$。那么 $h*g=g*h=g*\prod_{i=1}^{cnt}H_i$。算一个 $g*H_i$ 可以枚举所有不是 $p_i$ 的倍数的 $j$，将 $j, p_ij, p_i^2j, \cdots, p_i^kj$ 这些位置去卷上 $H_i$ 对应的点值，类似一个背包，其它部分就不用管，这样就对了。 最惊人的是以上做法的复杂度分析，对每个 $p_i$ 的复杂度为 $$ \sum\limits_{j\ge 1,p_i^j\le m} \lfloor m/p_i^j \rfloor\le m\sum\limits_{j\ge 1} 1/p_i^j=\frac{m}{p_i-1} $$ 求和后 $$ \sum_{i=1}^{cnt}\frac{1}{p_i-1}=1+\sum_{i=2}^{cnt}\frac{1}{p_i-1}\leq 1+\sum_{i=1}^{cnt-1}\frac{1}{p_i}\leq O(1+\log\log m) $$ 所以总复杂度为 $O(m\log\log m)$。 总结：定义 $\Sigma f(n)=\Sigma f(n-1)+f(n)$（前缀和），$\Delta f(n)=f(n)-f(n-1)$（差分），那么 $$ f(n)=\sum_{i=1}^ng(i)h(\left\lfloor n/i\right\rfloor)\iff \Delta f=g*\Delta h $$