本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-24 16:40:10

:::::info[题目基本信息] 考察：莫比乌斯函数，狄利克雷卷积（$2900$）。
题目简介：
给定 $\{a_n\}$，求满足条件的 $(x,S)$ 个数：

1. $\displaystyle x\in[1,n],S\subseteq\bigcup_{i=1}^n\{i\},x\notin S$
2. $\displaystyle\gcd_{i\in S}a_i>1,\gcd(\gcd_{i\in S}a_i,a_x)=1$

数据范围：

• $2\le n\le 5\times 10^5$
• $\forall i\in[1,n],2\le a_i\le 10^7$ ::::: 令 $f_d$ 表示 $\{a_n\}$ 中与 $d$ 互质的数的个数，$g_d$ 表示可重集 $\displaystyle\bigcup_{i=1}^n\{a_i\}$ 的非空子集中最大公约数恰好为 $d$ 的个数。那么最后答案就为 $\displaystyle\sum_{i=2}^Vf_ig_i$，其中 $V$ 是 $a_i$ 的值域。
  先进行 $f_d$ 的推导：
  $$\begin{aligned}f_d&=\sum_{i=1}^V[\gcd(i,d)=1]t_i\&=\sum_{i=1}^V\sum_{d_2\mid\gcd(i,d)}\mu(d_2)t_i\&=\sum_{d_2\mid d}\mu(d_2)\sum_{d_2\mid i}t_i\end{aligned}$$ 其中 $t_i$ 表示 $\{a_n\}$ 中 $i$ 的出现次数，即 $\displaystyle t_i=\sum_{j=1}^n[a_j=i]$。
  令 $\displaystyle F_d=\sum_{d|i}t_i,F'(d)=\mu(d)F_d$，那么 $\displaystyle f_d=\sum_{d_2\mid d}F'(d_2)$。
  再对 $g_d$ 推导：
  不妨令 $G_d$ 为可重集 $\displaystyle\bigcup_{i=1}^n\{a_i\}$ 的非空子集中最大公约数为 $d$ 的倍数个数，注意到 $G_d=2^{F_d}-1$。
  那么就有 $\displaystyle G_d=\sum_{d_2\mid d}g_{d_2}$。

那么现在我们要求下面类型的式子：
$$b_i=\sum_{j\mid i}a_j$$ $$b_i=\sum_{i\mid j}a_j$$ 注意到他们是狄利克雷卷积的形式。
:::::success[狄利克雷卷积] 模板题

我们考虑到我们可以在计算 $b_i$ 时枚举 $i$ 的因子进行容斥，这时时间复杂度就是子集枚举的复杂度，时间复杂度就为 $\Theta(3^{\log_2n})=\Theta(n^{\log_23})$，显然无法通过本题。
于是我们要优化我们的高维前缀和，我们考虑对于每一维做一次一维前缀和，然后正确性显然，但由于没有容斥所以时间复杂度在维数较高时大大降低。
此时，时间复杂度就为 $\displaystyle\Theta(\sum_{p\in\text{prime},p\le n}\frac{n}{p})=\Theta(n\log\log n)$，空间复杂度为 $\Theta(n)$。
::::: 同时注意到 $\displaystyle G_d=\sum_{d_2\mid d}g_{d_2}$ 是已知 $b$ 求 $a$ 的，那么我们反着来做一遍差分即可。
时间复杂度为 $\Theta(n+V\log\log V)$，空间复杂度为 $\Theta(n)$。 :::::warning[坑点] 还是那句话：卡空间。 ::::: :::::success[一些其他题目] 1 号题目
::::success[讲解] 注意到 $\displaystyle\lfloor\frac{i}{k}\rfloor\ne\lfloor\frac{i-1}{k}\rfloor$ 当且仅当 $k\mid i$，那么由于 $\displaystyle b_k=\sum_{i=1}^na_{\lfloor\frac{k}{i}\rfloor}$，则我们对 $\{b_n\}$ 差分可以发现（设序列 $p$ 差分后序列为 $p'$）： $$\begin{aligned}b'k&=b_k-b{k-1}\&=(\sum_{i=1}^na_{\lfloor\frac{k}{i}\rfloor})-(\sum_{i=1}^na_{\lfloor\frac{k-1}{i}\rfloor})\&=\sum_{i=1}^na_{\lfloor\frac{k}{i}\rfloor}-a_{\lfloor\frac{k-1}{i}\rfloor}\&=\sum_{i\mid k}a_{\frac{k}{i}}-a_{\frac{k}{i}-1}\&=\sum_{i\mid k}a'_{\frac{k}{i}}\end{aligned}$$ 所以 $\{b'_n\}$ 是 $\{a'_n\}$ 的狄利克雷卷积，直接套模板即可。
时间复杂度为 $\Theta(n\log\log n)$，空间复杂度为 $\Theta(n)$。
:::: 2 号题目
::::info[闲话] 被 DS 薄纱了...... :::: ::::success[讲解] 容易发现这道题的式子是有强制性要求转移顺序的，我们必须从前往后转移 $b_i$ 才可以得到正确的答案，那么我们该怎么办呢？
注意到一个性质：

• $\displaystyle d\mid k,d\ne k\Rightarrow d\le\frac{k}{2}$

这个性质启示我们倍增，或者叫二进制分组，将 $2^k+1\sim 2^{k+1}$ 的分为一组（其中 $k\in\mathbb N$）。
在此前我们也遇到了许多类似分组处理的思想，比如：

• CF710(EDU16) 题解 中 F 题二进制分组。
• 后面应该还有，但我懒得翻 4 页的题解。

为了方便，我们令 $\displaystyle b'k=\sum{p\mid k,p\ne k}b_p$，注意到这是一个典型的狄利克雷卷积形式，所以我们直接上狄利克雷卷积即可。

下面是 DS 写的算法过程：

注意 DS 所写有一定错误，比如“对每个素数 $p\le m$”应为“对每个素数 $p\le R$”，“对 $j$ 从 $m$ 到 $1$ 枚举”应为“对 $j$ 从 $1$ 到 $m$”。

时间复杂度为 $\Theta(n\log\log n)$ 但常数比板子题大几倍，空间复杂度为 $\Theta(n)$。
:::: 后面可能还会有添加。
咕咕咕。
:::::

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-26 14:34:26

Update：

• 在 Part 4 中有两处错误，感谢 XiaoZi_qwq 指出。 :::::info[题目基本信息] 考察：组合数学，数学，期望，逆元，数论。
  题目简述：
  有 $n$ 个人站在一条数轴上，令 $\{p_n\}$ 为这 $n$ 个人所处的位置，一开始时 $\forall i\in[1,n],p_i=i$，下面你可以进行若干次（可以为 $0$ 次）操作：

1. 选择一个整数 $x$，满足 $x\in[1,n]$。
2. $\forall i\in[1,n],p_i<x,p_i\leftarrow p_i+1$。
3. $\forall i\in[1,n],p_i>x,p_i\leftarrow p_i-1$。

现在赋予 $1$ 到 $n$ 的每个点权值，它们形成一个数列 $\{a_n\}$，求对于所有操作后可能的 $\{p_n\}$ 的 $\displaystyle\sum_{i=1}^na_{p_i}$ 的值的总和对于 $998244353$ 取模的结果。
数据范围：

• $1\le n\le 2\times 10^5$
• $\forall i\in[1,n],1\le a_i\le 10^9$ ::::: 好久没见过这么人类智慧的神秘小清新计数题了，还是太吃脑容量了。

Part 1：将题目问题转化：

这道题看起来就很数学，但是 $\displaystyle\sum_{i=1}^na_{p_i}$ 的这个 $a_{p_i}$ 限制了我们拆贡献之类的操作，考虑把它转化掉。
注意到 $\forall i\in[1,n],p_i\in[1,n]$，所以我们考虑将 $\{p_n\}$ 映射到它的值域上。
更加具体地，令 $\displaystyle t_i=\sum_{j=1}^n[p_j=i]$，也就是说 $t_i$ 是 $\{p_n\}$ 中 $i$ 的出现次数，那么现在我们容易将 $\displaystyle\sum_{i=1}^na_{p_i}$ 转化为 $\displaystyle\sum_{i=1}^na_it_i$，容易发现 $\{p_n\}$ 和 $\{t_n\}$ 一一对应，问题得到了解决。

Part 2：对 $\{t_n\}$ 发掘性质：

注意到 $\displaystyle\sum_{i=1}^na_it_i$ 这个式子还是无从下手，这是因为我们没有对哪些 $\{t_n\}$ 合法有一个具体的认知，我们不妨发掘一些合法的 $\{t_n\}$ 的性质。

1. 显而易见地，$\exist 1\le L\le R\le n,\forall i\in[L,R],t_i>0,\forall i\notin[L,R],t_i=0$，也就是说 $t_i\ne 0$ 的 $i$ 构成了一段区间。
   :::::success[证明]
   显然操作不会扩大人与人之间的间距，同时原来初始时 $t_i\ne 0$ 的 $i$ 就构成了一段区间，那么无论怎么操作都不会影响能否构成区间。
   实际上使用了数学归纳法的思想。
   :::::
2. 假定有一个初始 $\{t_n\}$ 序列，容易得到唯一一组满足性质 1 中限制的 $L,R$ 以及原序列 $\{p_n\}$。这个 $\{t_n\}$ 序列经过若干次操作后变为了 $\{t'_n\}$，同样得到类似的 $L',R'$ 和原序列 $\{p'_n\}$，那么 $\forall i\in[1,n],p'_i\in(L',R')\Rightarrow p_i\in(L,R)$。
   :::::success[证明]
   考虑反证法。
   若 $p_i\notin(L,R)$（其实就是 $p_i\in\{L,R\}$），那么由于操作的性质，显然能推出 $p'_i\notin(L',R')$，与条件矛盾。
   :::::
3. 对于每个 $\{t_n\}$ 唯一一组满足性质 1 中限制的 $L,R$，都又能使得 $\forall i\in(L,R),t_i\equiv 1\pmod 2$。
   :::::success[证明]
   考虑数学归纳法。
   对于初始时 $\forall i\in(L,R),t_i=1$，性质显然成立。
   我们假设操作前序列符合性质，注意到多个原来不同位置上的人只会在被操作的位置上移动到同一位置，也就是说只会在被操作的位置上“合并”，所以我们仅需验证被操作位置的 $t_i$ 的奇偶性即可。
   由于 2，所以 $i$ 位置上的所有人以前都不在端点上，所以“合并”时一定是 $pos-1,pos,pos+1$ 合并，三个奇数相加仍然是奇数。
   :::::

Part 3：构造证明充分性：

前面的性质 1,3 对于 $\{t_n\}$ 的可能性作了限制，那么满足这些性质的是否就一定合法呢？
:::::success[证明] 考虑构造。
我们要构造出 $\{t_n\}$。

1. 求出它的 $L,R$。
2. 在位置 $1$ 处进行 $t_L$ 次操作。
3. 在位置 $n-t_L$ 处进行 $t_R$ 次操作。
4. $\forall i\in(L,R)$，在合适的位置（显然存在）进行 $\displaystyle\lfloor\frac{t_i}{2}\rfloor$ 次操作。
5. 在位置 $1$ 或 $n$ 处进行若干次操作平移 $\{t_n\}$。
   :::::

Part 4：大力分讨拆贡献：

前面铺垫了这么多，我们终于要算答案了。
注意到我们要枚举 $t_L$ 和 $t_R$ 的奇偶性，我们要先特判：

• $L=R$ 时：
  我们直接枚举 $L$，$L$ 处的答案就是 $na_L$。
• $L\ne R$ 时：
  根据 Part 3 的构造过程 5，对于 $R-L+1$ 相同的 $L,R$ 答案是类似的，只是所乘的 $a_i$ 不同，所以我们考虑枚举 $R-L+1$，然后枚举 $x,y\in\{1,2\}$，表示 $t_L$ 和 $t_R$ 的奇偶性。
  容易发现，此时对于存在一个 $\{f_n\}$ 满足 $t_L=2f_L+x$ 且 $t_R=2f_R+y$ 同时 $\forall i\in(L,R),t_i=2f_i+1$ 且 $\forall i\notin[L,R],f_i=0$，容易发现 $f_i$ 和 $t_i$ 一一对应，为了方便计算我们后文将计算 $\{f_n\}$ 的数量，再来计算贡献。
  容易发现，$\displaystyle\sum_{i=L}^R2f_i=n-(x-1)-(y-1)-(R-L+1)=n-x-y+(R-L+1)+2$，我们记为 $res$，那么我们特判掉 $res<0$ 或 $res\equiv 1\pmod 2$ 的情况，容易发现 $\displaystyle\sum_{i=L}^Rf_i=\frac{res}{2}$，那么 $\{f_n\}$ 的数量可以通过插板法计算，为 $\displaystyle\binom{R-L+\frac{res}{2}}{R-L}$，这个可以预处理阶乘和逆元计算。
  $\{f_n\}$ 的数量算出来了我们还不能直接得出答案，注意到 $\forall i\in(L,R)$ 部分任意顺序的 $\{f_n\}$ 均合法，所以 $f_i$ 的期望为 $\dfrac{res}{2(R-L+1)}$，我们也容易得到 $t_i$ 的期望，$t_i$ 的期望乘 $\{f_n\}$（$\{t_n\}$）的数量再乘长度为 $R-L+1$ 的 $\{a_n\}$ 的连续子序列和的总和就是 $R-L+1$ 的答案，所以我们还差最后一步：算长度为 $R-L+1$ 的 $\{a_n\}$ 的连续子序列和的总和。
  这个东西其实不难，直接推导： $$\begin{aligned}\sum_{l=1}^{n-R+L}\sum_{i=l}^{l+R-L}a_i&=\sum_{l=1}^{n-R+L}sum_{l+R-L}-sum_{i-1}\&=(\sum_{l=1}^{n-R+L}sum_{l+R-L})-(\sum_{l=1}^{n-R+L}sum_{i-1})\&=sum^2_n-sum^2_{R-L}-sum^2_{n-R+L-1}\end{aligned}$$ 其中 $\{sum_n\}$ 是 $\{a_n\}$ 的前缀和，$\{sum^2_n\}$ 是 $\{sum_n\}$ 的前缀和，直接预处理即可。

太好了我们终于做完了！
时间复杂度为 $\Theta(n\log V)$（线性预处理逆元可以做到 $\Theta(n)$），空间复杂度为 $\Theta(n)$。

code
:::::warning[坑点] 看看谁预处理阶乘没有预处理到 $2n$？
看看谁取模取少了？
看看谁算前缀和没加模数？
:::::

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-26 20:33:41

:::::info[题目基本信息] 考察：哈希 hashing。
题目简述：
定义匹配字符串如下：

1. 空串是匹配字符串。
2. 若 $\text{p}$ 是一个小写字母，$S$ 是匹配字符串，那么 $\text{p}+S+\text{p}$ 是匹配字符串，其中定义字符串意义下 $+$ 表示连接，下同。
3. 若 $S,T$ 是匹配字符串，那么 $S+T$ 是匹配字符串。

给定一个长度为 $n$ 的由小写字母构成的字符串 $s$，求它的非空匹配子串个数。
数据范围：

• $1\le n\le 2\times 10^6$ ::::: :::::info[闲话] 由于 lca 要求证明结论所以出现了这篇题解。
  显然下面的东西是老师上课讲的。
  ::::: 令 $s_{(l,r)}$ 表示子串 $\displaystyle\sum_{i=l}^rs_i$。
  结论：$s_{(l,r)}$ 是匹配字符串当且仅当处理 $l$ 前和处理完 $r$ 后匹配时用的栈内元素和顺序完全相同。 :::::success[证明] 先证明一个小结论：
• 字符串是否匹配与匹配顺序无关。

::::success[小结论 1 证明] 设一个字符串 $str=\text{p}+a+\text{p}+b+\text{p}+c+\text{p}$，其中 $a,b,c$ 是匹配字符串，$\text{p}$ 是一个小写字母。

• 若匹配第一、四个 $\text{p}$ 和第二、三个 $\text{p}$：
  容易发现 $str$ 是一个匹配字符串。
• 若匹配第一、二个 $\text{p}$ 和第三、四个 $\text{p}$：
  容易发现 $str$ 也是一个匹配字符串。

所以 $str$ 的匹配顺序与是否匹配无关。
:::: 再证明一个小结论：匹配字符串性具有前后缀可减性。更详细地：

1. 若 $S$ 以及 $S_{(1,k)}$（$k\in\mathbb N^*$）都是匹配字符串，那么 $S_{(k,|S|)}$ 也是匹配字符串。
2. 若 $S$ 以及 $S_{(k,|S|)}$（$k\in\mathbb N^*$）都是匹配字符串，那么 $S_{(1,k)}$ 也是匹配字符串。

::::success[小结论 2 证明] 以证明小结论 2-1 为例：
若 $S_{(k,|S|)}$ 不是匹配字符串，那么匹配后的栈非空，那么匹配 $S$ 时的栈就是空栈合并非空栈，也是非空栈，这样 $S$ 就不是匹配字符串，推出矛盾，得证。
小结论 2 类似。
:::: 现在我们可以证明这个结论了。
::::success[充分性] 设 $s_{(1,l-1)}$ 和 $s_{(1,r)}$ 匹配后的栈序列为 $st$，同时设反栈序列为 $\overline{st}$，那么由于小结论 1，$\overline{st}+s_{(1,l-1)}$ 和 $\overline{st}+s_{(1,r)}$ 匹配后栈均为空，所以它们都是匹配字符串，又由于小结论 2，$s_{(l,r)}$ 就是匹配字符串。
:::: ::::success[必要性] 考虑反证法。
如果 $s_{(1,l-1)}$ 和 $s_{(1,r)}$ 的匹配时所用栈序列不同，$s_{(l,r)}$ 匹配时一定添加或删去了一些字符，那么它就不是匹配字符串，推出矛盾。
:::: ::::: 现在我们证明了结论，容易发现这个东西可以哈希。
然后做完了。
时空复杂度均为 $\Theta(n)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-01 10:05:25

:::info[题目基本信息] 考察：动态规划 DP。
题目简介：
给定一个两两元素不同的序列 $\{a_n\}$，现在问对其任意重排成 $\{a'n\}$，使得 $\displaystyle\sum{i=2}^n|a_i-a_{i-1}|\le m$ 的方案数对 $10^9+7$ 取模的结果。
时间限制 2s，空间限制 512MB。
数据范围：

• $1\le n\le 100$
• $1\le m\le 1000$
• $\forall i\in[1,n],1\le a_i\le 1000$ ::: :::info[闲话] 我咋不会这个套路，还是太菜了。
  ::: 先考虑暴力 DP，然后我们发现暴力 DP 做不了。状压 DP 状态是 $\Theta(2^nm)$ 量级的，其它可能的暴力 DP 就算是多项式复杂度，次数也非常高，这条路走不通。
  所以我们要采用连续段 DP。 ::::success[连续段 DP] :::info[注] 连续段 DP 这个名字是我自己起的，还可以叫它插入 DP 之类，没有一个明确的术语。
  ::: 注意到这个题画出图直观表示是这个样子的：
  
  现在我们用一条直线从下往上扫：
  
  连续段 DP 就记录扫到了哪里，同时记录直线下方部分构成了几个连续段进行 DP。
  :::: 好的，对于这道题就是要让折线竖直方向长度不超过 $m$，所以我们先暂时设 $f_{i,j,k}$ 表示从下往上扫到了 $i$ 个点，形成了 $j$ 个连续段，直线下方折线竖直方向总长度为 $k$ 的方案数。
  但是有一些问题，在中间位置的点往上会贡献两条折线，在位置 $1$ 或 $n$ 上的点只会往上贡献一条折线，所以我们还要记录扫到了几个位于位置 $1$ 和 $n$ 的点。
  所以我们最终状态就设 $f_{i,j,k,l}$ 表示从下往上扫到了 $i$ 个点，形成了 $j$ 个连续段，直线下方竖直方向折线总长度为 $k$，扫到了 $l$ 个位于位置 $1$ 和 $n$ 上的点，状态数是 $n\times n\times m\times 3=\Theta(n^2m)$ 的，看上去很对，空间如果有点炸用滚动数组压掉第一维就行了。

接下来，考虑转移。
这时会有一个问题，看图：

注意到未被扫到的点下一个扫到谁的贡献是不一样的，所以我们考虑进行大力分讨（这里就是为什么本题填表法严格劣于刷表法，可是我还是写了填表法）：

1. 连在了一个原有连续段上：
   这时还需要分是不是扫到了一个位于位置 $1$ 和 $n$ 的分类讨论。
   • 扫到的点位置不位于位置 $1$ 和 $n$：
     这时转移方程式为：
     $$f_{i,j,k,l}\leftarrow f_{i,j,k,l}+(2j-l)f_{i-1,j,k-(2j-l)(a_i-a_{i-1}),l}$$ 前提条件：首先 $(2j-l)(a_i-a_{i-1})$ 这一坨肯定要大于等于 $0$ 且小于等于 $k$（下同，下文中省略），然后还需要原本就有连续段，也就是 $j\ne 0$。
   • 扫到的点位置位于位置 $1$ 和 $n$：
     这时转移方程式为：
     $$f_{i,j,k,l}\leftarrow f_{i,j,k,l}+(3-l)f_{i-1,j,k-(2j+1-l)(a_i-a_{i-1}),l-1}$$ 前提条件：首先原本要有连续段，即 $j\ne 0$，同时 $l\ne 0$。
2. 把两个原有连续段合并成了一个连续段：
   都合并连续段了，那位置肯定不位于 $1$ 或 $n$ 了啊。
   这时转移方程式为：
   $$f_{i,j,k,l}\leftarrow f_{i,j,k,l}+jf_{i-1,j+1,k-(2j+2-l)(a_i-a_{i-1}),l}$$ 前提条件：合并完后肯定不能没有连续段，所以 $j\ne 0$ 又双叒叕要成立。
3. 新建了一个连续段：
   还是要分两种情况讨论。
   • 扫到的点位置不位于位置 $1$ 和 $n$：
     这时转移方程式为：
     $$f_{i,j,k,l}\leftarrow f_{i,j,k,l}+(j-l)f_{i-1,j-1,k-(2j-2-l)(a_i-a_{i-1}),l}$$ 前提条件：都出现 $j-1$ 了那么肯定 $j\ne 0$ 啊。
   • 扫到的点位置位于位置 $1$ 和 $n$：
     这时转移方程式为：
     $$f_{i,j,k,l}\leftarrow f_{i,j,k,l}+(3-l)f_{i-1,j-1,k-(2j-1-l)(a_i-a_{i-1}),l-1}$$ 前提条件：同上，需要满足 $j\ne 0$ 且 $l\ne 0$。

好的我们终于分讨完了，最后答案就等于：
$$\sum_{k=0}^mf_{n,1,k,2}$$ 时空复杂度均为 $\Theta(n^2m)$，时间常数可能有些爆炸。
:::warning[坑点] 主要还是说明为什么填表法不如刷表法。

填表法和刷表法虽然状态转移方程式同样要分 $5$ 种情况讨论，但是刷表法中 $k$ 的变化量是一样的，而填表法并不，所以如果你写填表法你会写出来这么一个鬼东西：

if(j&&((j<<1)-l)*(a[i]-a[i-1])>=0&&((j<<1)-l)*(a[i]-a[i-1])<=k)
    (f[i&1][j][k][l]+=f[i-1&1][j][k-((j<<1)-l)*(a[i]-a[i-1])][l]*((j<<1)-l)%MOD)%=MOD;
if(j&&l&&((j<<1)+1-l)*(a[i]-a[i-1])>=0&&((j<<1)+1-l)*(a[i]-a[i-1])<=k)
    (f[i&1][j][k][l]+=f[i-1&1][j][k-((j<<1)+1-l)*(a[i]-a[i-1])][l-1]*(3-l)%MOD)%=MOD;
if(j&&((j+1<<1)-l)*(a[i]-a[i-1])>=0&&((j+1<<1)-l)*(a[i]-a[i-1])<=k)
    (f[i&1][j][k][l]+=f[i-1&1][j+1][k-((j+1<<1)-l)*(a[i]-a[i-1])][l]*j%MOD)%=MOD;
if(j&&((j-1<<1)-l)*(a[i]-a[i-1])>=0&&((j-1<<1)-l)*(a[i]-a[i-1])<=k)
    (f[i&1][j][k][l]+=f[i-1&1][j-1][k-((j-1<<1)-l)*(a[i]-a[i-1])][l]*(j-l)%MOD)%=MOD;
if(j&&l&&((j-1<<1)+1-l)*(a[i]-a[i-1])>=0&&((j-1<<1)+1-l)*(a[i]-a[i-1])<=k)
    (f[i&1][j][k][l]+=f[i-1&1][j-1][k-((j-1<<1)+1-l)*(a[i]-a[i-1])][l-1]*(3-l)%MOD)%=MOD; 

可读性很低，不建议写。
:::

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-03 21:12:33

:::::info[闲话] 模拟赛的题，太菜了，不会，打了 30pts 部分分（其实就是 F1）跑路了。
看完 F2 题解中 Ri 的 idea 大受震撼。
::::: :::::info[题目基本信息] 考察：

• F1：Catalan 数，组合数学（$2400$）。
• F2：Catalan 数，组合数学，并查集（$2700$）。

题目简述：
$t$ 组数据，每组数据以一定顺序给定一个长度为 $2n$ 的匹配括号序列的 $n$ 组括号匹配对，当 $\forall i\in[0,n]$ 时，求有多少长度为 $2n$ 的匹配括号序列使得它的括号匹配对中含有第 $j$（$1\le j\le i$）组括号匹配对（对 $998244353$ 取模）。
数据范围：

1. F1：

• $1\le t\le 1000$
• $2\le n\le 5000$
• 对于单个测试点，$\displaystyle\sum n\le 5000$

2. F2：

• $1\le t\le 10^4$
• $2\le n\le 3\times 10^5$
• 对于单个测试点，$\displaystyle\sum n\le 3\times 10^5$ :::::

F1 部分：

我们有一个结论：长度为 $2n$ 的匹配括号序列的个数为 $C_n$（这里的 $C_n$ 指 Catalan 数的第 $n$ 项）。
:::::success[证明] 太经典了，懒得写，右转 oiwiki。
::::: 那么我们设最后的答案序列为 $\{ans_n\}$，根据上文我们得到 $ans_0=C_n$。
现在我们考虑从 $ans_i$ 推导到 $ans_{i+1}$（这里 $i\in[0,n)$）：

其中黑色虚线表示的是当前要加入的第 $i$ 对括号匹配对，红色实线表示的是离它最近的包含它的括号匹配对（记为 $lst_i$），蓝色虚线表示的是它所包含的括号匹配对，设第 $k$ 对括号匹配对内未被其它括号匹配对包含的位置的数量为 $siz_k$，那么我们可以得到：
$$ans_{i+1}\leftarrow \frac{ans_iC_{(siz'{lst_i}-siz{i}-2)\div 2}C_{siz_i\div 2}}{C_{siz'_{lst_i}\div 2}}$$ 这里，$siz'_k$ 表示还未被更新的 $siz_k$，那么：
$$siz_k\leftarrow siz'_k-siz_i-2$$ :::::success[证明] 显然，一对括号匹配对左右拼起来是一个匹配括号序列，它的里面也是一个匹配括号序列，通过这个性质我们可以得出上面的式子。
::::: 现在，我们还需要找到 $lst_i$，同时计算 $siz_i$，考虑将 ( 当作 $+1$，) 当作 $-1$，我们发现：

• $l_{lst_i}$（$lst_i$ 的左括号位置，$r$ 同理）是从右往左第一个 $p$ 使得 $[p,l_i)$ 的权值和大于 $0$ 的，因为它是第一个统计不到 $r$ 的。
• $siz_i$ 是 $p$（$p\in(l_i,r_i)$）满足 $(l_i,p)$ 的权值和等于 $0$ 的数量。

这两个显然可以 $\Theta(n)$ 统计（也可能可以用数据结构优化），这样我们就解决了 F1。
时间复杂度为 $\Theta(n^2+n\log m)$（$m=998244353$ 是模数，可以优化成 $\Theta(n^2+\log m)$ 但没必要），空间复杂度为 $\Theta(n)$。

F2 部分：

注意到上面 F1 的做法正推优化可能比较麻烦，需要上数据结构（诸如线段树，官解用了平衡树），所以我们考虑倒推删括号。
显然 $ans_n=1$，现在我们考虑从 $ans_i$ 推导到 $ans_{i-1}$。
还是上面的图，我们考虑删去黑色虚线表示的括号匹配对，这时：
$$siz_{lst_i}\leftarrow siz'{lst_i}+siz_i+2$$ 同时由于括号被删去，$siz_i\leftarrow 0$。
同时，根据：
$$ans{i+1}\leftarrow \frac{ans_iC_{(siz'{lst_i}-siz{i}-2)\div 2}C_{siz_i\div 2}}{C_{siz'{lst_i}\div 2}}$$ 我们得到：
$$ans{i-1}\leftarrow \frac{ans_iC_{siz_{lst_i}\div 2}}{C_{(siz_{lst_i}-siz_{i}-2)\div 2}C_{siz_i\div 2}}$$ 现在我们需要快速求出 $lst_i$。
注意到删去括号等价于把括号合并到它的 $lst$ 上，我们使用并查集维护即可。
然后做完了。
时间复杂度为 $\Theta(n\lpha(n)+n\log m)$（递推 Catalan 数可以做到 $\Theta(n\lpha(n))$，爆标了），空间复杂度为 $\Theta(n)$。
:::::success[code] F1
F2
:::::

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-04 11:37:03

:::::info[题目基本信息] 考察：数学，动态规划 DP，容斥（$2700$）。
题目简介：
给定序列 $\{a_n\}$，设：
$$x_k=\lfloor\frac{x}{10^k}\rfloor\bmod 10$$ $$f(S)=\sum_{i=0}^510^i\min_{x\in S}x_i$$ 求：
$$\bigoplus_{i=0}^{999999}i((\sum_{S\subseteq\{a_n\},f(S)=i}(\sum_{x\in S}x)^2)\bmod(10^9+7))$$ 数据范围：

• $1\le n\le 10^5$
• $\forall i\in[1,n],0\le a_i\le 999999$ ::::: 不妨设 $\displaystyle G(i)=\sum_{S\subseteq\{a_n\},f(S)=i}(\sum_{x\in S}x)^2$，注意到 $f(S)=i$ 这个条件过于严格，不好统计，考虑容斥。
  设 $\displaystyle g(i)=\sum_{S\subseteq\{a_n\},i\subseteq f(S)}(\sum_{x\in S}x)^2$，其中，定义两个整数 $x,y$ 之间满足 $x\subseteq y$ 当且仅当 $\forall k\in[0,5],x_i\le y_i$，最终我们也可以得到 $g(i)$ 的转移方程式（？）：
  $$\begin{aligned}g(i)&=\sum_{S\subseteq\{a_n\},i\subseteq f(S)}(\sum_{x\in S}x)^2\&=\sum_{S\subseteq\{a_n\}}[\forall x\in S,i\subseteq x](\sum_{x\in S}x)^2\end{aligned}$$ 好像并不容易，我们记 $S_i=\{x\in\{a_n\}|i\subseteq x\}$，则 $\displaystyle g(i)=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^2$。
  好像还是不容易，但是我们观察到 $x\subseteq y\Rightarrow S_y\subseteq S_x$，这种情况我们就要考虑从 $y$ 合并到 $x$。
  考虑如何合并，假设有两个集合 $S_p,S_q$，满足 $S_p\cap S_q=\arnothing$ 且 $S_p\cup S_q=S_i$，这时我们要将 $S_p,S_q$ 的信息合并到 $S_i$ 上，容易得到：
  $$\begin{aligned}g(i)&=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^2\&=\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x+\sum_{x\in S_q\cap S}x)^2\&=\sum_{S\subseteq S_i}((\sum_{x\in S_p\cap S}x)^2+2(\sum_{x\in S_p\cap S}x)(\sum_{x\in S_q\cap S}x)+(\sum_{x\in S_q\cap S}x)^2)\&=(\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x)^2)+2(\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x)(\sum_{x\in S_q\cap S}x))+(\sum_{S\subseteq S_i}(\sum_{x\in S_q\cap S}x)^2)\&=(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}(\sum_{x\in s_p}x)^2)+2(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}(\sum_{x\in s_p}x)(\sum_{x\in s_q}x))+(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}(\sum_{x\in s_q}x)^2)\&=2^{|S_q|}(\sum_{s_p\subseteq S_p}(\sum_{x\in s_p}x)^2)+2(\sum_{s_p\subseteq S_p}(\sum_{x\in s_p}x)\sum_{s_q\subseteq S_q}(\sum_{x\in s_q}x))+2^{|S_p|}(\sum_{s_q\subseteq S_q}(\sum_{x\in s_q}x)^2)\end{aligned}$$ 这时，我们要维护什么就显而易见了，设：
  $$\begin{aligned}F(i,2)&=g(i)\&=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^2\end{aligned}$$ $$F(i,1)=\sum_{S\subseteq S_i}\sum_{x\in S}x$$ $$\begin{aligned}F(i,0)&=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^0\&=\sum_{S\subseteq S_i}1\&=2^{|S_i|}\end{aligned}$$ 最终，我们可以得到： $$F(i,2)=F(p,2)F(q,0)+2F(p,1)F(q,1)+F(p,0)F(q,2)$$ 类似地，我们可以得到：
  $$\begin{aligned}F(i,1)&=\sum_{S\subseteq S_i}\sum_{x\in S}x\&=\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x+\sum_{x\in S_q\cap S}x)\&=(\sum_{S\subseteq S_i}\sum_{x\in S_p\cap S}x)+(\sum_{S\subseteq S_i}\sum_{x\in S_q\cap S}x)\&=(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}\sum_{x\in s_p}x)+(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}\sum_{x\in s_q}x)\&=2^{|S_q|}(\sum_{s_p\subseteq S_p}\sum_{x\in s_p}x)+2^{|S_p|}(\sum_{s_q\subseteq S_q}\sum_{x\in s_q}x)\&=F(p,1)F(q,0)+F(p,0)F(q,1)\end{aligned}$$ $$F(i,0)=F(p,0)F(q,0)$$ 现在我们得到了 $g(i)=F(i,2)$，要容斥出 $G(i)$，这个就是平凡的高维差分。
  最后计算出答案即可。
  时间复杂度为 $\Theta(n+V\log V)$，空间复杂度为 $\Theta(V)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-05 11:26:30

:::::info[题目基本信息] 考察：容斥原理，动态规划 DP（$2835$）。
题目简述：
给定序列 $\{l_m\}$ 和 $\{r_m\}$，同时有一个序列 $\{c_n\}$，初始时 $\forall i\in[1,n],c_i=0$，求进行下面操作使得 $\forall i\in[1,n],c_i=1$ 的期望次数对 $998244353$ 取模的结果。

• 等概率选取一个整数 $i$ 满足 $i\in[1,m]$，然后 $\forall pos\in[l_i,r_i],c_{pos}\leftarrow 1$。

数据范围：

• $1\le n,m\le 400$
• $\forall i\in[1,m],1\le l_i\le r_i\le n$
• $\forall i\in[1,n],\exist j\in[1,m],l_j\le i\le r_j$ ::::: 设 $t_i$ 为 $c_i$ 第一次变成 $1$ 的已进行操作数，显然最后答案就是 $\displaystyle E\max_{i=1}^nt_i$，但是由于 $\displaystyle E\max_{i=1}^n t_i\ne\max_{i=1}^n Et_i$，所以我们不能直接拆，也不好直接算，我们就要考虑容斥。
  对于极值，我们有 Min-Max 容斥，对于本题式子为：
  $$\max_{x\in S}t_x=\sum_{T\subseteq S,T\ne\arnothing}(-1)^{|T|+1}\min_{x\in T}t_x$$ :::::success[证明] 考虑对于 $S$ 中的每个元素分别计算贡献：
  设 $\displaystyle p=\min_{x\in T\subseteq S}t_x$，此时，要是最小值等于 $p$，大于 $p$ 的可选可不选，小于它的一定不能选，贡献就是：
  $$\begin{aligned}\sum_{T\subseteq \{x|x\in S,x>p\},p\in T}(-1)^{|T|+1}p&=p\sum_{T\subseteq \{x|x\in S,x>p\}}(-1)^{|T|}\&=p\sum_{T'=0}^{\sum_{x\in S}[x>p]}\sum_{T\subseteq\{x|x\in S,x>p\},|T|=T'}(-1)^{T'}\&=p\sum_{T'=0}^{\sum_{x\in S}[x>p]}(-1)^{T'}\binom{\sum_{x\in S}[x>p]}{T'}\&=p\sum_{T'=0}^{\sum_{x\in S}[x>p]}(-1)^{T'}1^{\sum_{x\in S}[x>p]-T'}\binom{\sum_{x\in S}[x>p]}{T'}\&=p(-1+1)^{\sum_{x\in S}[x>p]}\&=[\sum_{x\in S}[x>p]=0]p\&=\max_{x\in S}t_x\end{aligned}$$ ::::: 显然上面的式子在期望意义下也成立，所以直接套用到本题。
  在本题中 $\displaystyle E\min_{x\in T\subseteq S}t_x$ 是好算的，表达的意思就是 $T$ 中有元素 $x$ 使得 $c_x=1$ 的已进行操作数的期望，若 $p$ 表示所有 $[l_i,r_i]$ 与 $T$ 有交的个数，即 $\displaystyle p=\sum_{i=1}^m[[l_i,r_i]\cap T\ne\arnothing]$，容易发现会有 $\dfrac{p}{m}$ 的概率使得存在 $x$ 使得 $c_x=1$，那么我们得到 $\displaystyle E\min_{x\in T\subseteq S}t_x=\frac{m}{p}$。
  :::::success[证明] 根据题意得出方程：
  $$E\min_{x\in T\subseteq S}t_x=\frac{p}{m}\cdot 1+\frac{m-p}{m}(E\min_{x\in T\subseteq S}t_x+1)$$ 容易解出方程的解。
  ::::: 那么我们就可以设出 DP 状态，设 $f_{i,j}$ 表示考虑到 $t_i$，有 $j$ 个 $[l_i,r_i]$ 与区间有交的方案数（包括乘 $-1$ 的权值），初始条件为 $f_{0,0}=-1$，考虑枚举上一个 $t_{lst}$，设 $k$ 为区间包含 $i$ 但不包含 $lst$ 的区间数，容易得出转移方程：
  $$f_{i,j+k}\leftarrow f_{i,j+k}-f_{lst,j}$$ 现在我们考虑怎么快速求出 $k$，容易容斥发现 $k$ 是区间包含 $i$ 的数量减去区间包含 $[lst,i]$ 的数量，这两个可以预处理二维前缀和实现。
  最后答案就是：
  $$\sum_{i=1}^n\sum_{j=0}^mf_{i,j}\cdot\frac{m}{j}$$ 时间复杂度为 $\Theta(n^2m)$，空间复杂度为 $\Theta(nm)$。
  code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-06 23:21:30

:::::info[闲话] 已完成今日模拟赛挂分 180pts 大学习。
::::: :::::info[题目基本信息] 考察：

• G1：KMP 算法（$2400$）。
• G2：KMP 算法，矩阵加速（$2600$）。

题目简介：
定义斐波那契串为：

• $f_1=\texttt{a}$
• $f_2=\texttt{b}$
• $\forall i\ge 3,f_i=f_{i-1}+f_{i-2}$，其中 $+$ 表示字符串拼接。

给定 $n$，$q$ 次询问，每次给出一个字符串 $p$，求 $p$ 在 $f_n$ 里的出现次数（对 $10^9+7$ 取模）。
数据范围：

1. G1：

• $1\le n,q,\displaystyle\sum|p|\le 3000$

2. G2：

• $1\le n\le 10^{18}$
• $1\le q\le 10^4$
• $1\le\sum|p|\le 10^5$ ::::: G1 对 G2 几乎毫无启发，我们直接看 G2（绝对不是因为不会，而是因为这是 G2 题解）。

G2：

首先在 $n\le 10^{18}$ 时 $|f_n|$ 是很爆炸的，我们不能直接算。
在放弃数据结构等若干方法后，我们考虑 DP，设 $F_n$ 为 $f_n$ 中 $p$ 的出现次数，容易发现出现的 $p$ 只能有这三种情况：

• 出现在 $f_{n-1}$ 中。
• 出现在 $f_{n-2}$ 中。
• 一段非空前缀出现在 $f_{n-1}$ 中，一段非空后缀出现在 $f_{n-2}$ 中。

设第 $3$ 种情况的出现次数为 $F'n$，那么我们得到：
$$F_n=F{n-1}+F_{n-2}+F'n$$ 现在我们重点解决 $F'_n$。
想要既有字符出现在 $f{n-1}$ 中，又有字符出现在 $f_{n-2}$ 中，那么它一定出现在 $f_{n-1}$ 的后 $|p|$ 个字符和 $f_{n-2}$ 的前 $|p|$ 个字符拼接形成的字符串中，长度大约是 $2\times 10^5$，看起来没有那么爆炸了，但是还是不能直接做。
但是我们观察得到，$f_{n-1}$ 的后 $|p|$ 个字符和 $f_{n-2}$ 的前 $|p|$ 个字符拼接形成的字符串经过一定时间就没有几种情况了，因为根据原式 $f_i=f_{i-1}+f_{i-2}$，$f_i$ 的前 $|p|$ 个字符在字符串足够长的时候与 $f_{i-2}$ 的相同，后 $|p|$ 个字符同理，考虑找出这个位置。
由于首先这个字符串要有 $|p|$ 个字符，所以我们先找到第一个使得 $|f_{pos}|\ge|p|$ 的 $pos$，这个直接暴力预处理暴力跑就行，简单分析一下发现每次询问会有 $\Theta(\log |p|)$ 的复杂度，跟没有一样。预处理的时间复杂度简单分析一下发现下界是 $\Theta(|p|\log |p|)$ 的，也不大。
我们找到了 $pos$，不断尝试 $pos,pos+1,pos+2,\dots$，最终我们发现这个拼接而成的字符串会在 $pos+4$ 以后就不变了，那么当 $n\le pos+3$ 时我们就可以直接跑 KMP 算答案，此时字符串长度上界也才 $8|p|$，稳稳的。
那么我们现在要算 $n\ge pos+4$ 时的答案，此时容易得到 $F'n=F'{n-2}$，我们进行推导：
$$F_{n-2}=F_{n-3}+F_{n-4}+F'{n-2},F'{n-2}=F'n\\Leftrightarrow F'_n=F{n-2}-F_{n-3}-F_{n-4}$$ 代入 $F_n=F_{n-1}+F_{n-2}+F'n$ 得： $$F_n=F{n-1}+2F_{n-2}-F_{n-3}-F_{n-4}$$ 这个东西显然可以用矩阵快速幂维护，开一个 $siz=4$ 的矩阵即可。
然后做完了，代码长度也并不长，感觉就是 KMP 板子和矩阵快速幂板子拼了起来。
时间复杂度为 $\Theta(\max|p|\log\max|p|+\sum|p|+qsiz^3\log n)$，空间复杂度为 $\Theta(siz^3+\sum|p|)$。

code

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-08 11:20:00

:::::info[题目基本信息] 考察：构造（$3000$）。
题目简述：
$T$ 组数据，每组数据给定 $n$，有一序列 $\{a_n\}$，初始时 $\forall i\in[1,n],a_i=i$，你可以进行下面操作若干次：

• 选定 $x,y$ 满足 $x,y\in[1,n]$ 且 $x\ne y$，同时进行操作 $a_x\leftarrow a_x+a_y$ 和 $a_y\leftarrow|a_x-a_y|$。

你想让 $\{a_n\}$ 中的元素都为一个数，在此基础上你想让这个数最小，在此基础上你想让操作数不超过 $20n$，问是否有解，若有解构造方案。
数据范围：

• $1\le T\le 25000$
• $2\le n\le 5\times 10^4$
• $\sum n\le 5\times 10^4$ ::::: :::::info[闲话] 神秘构造题。
  本题中所有结论均可使用打表发现。
  ::::: 结论 1：若有解，则最后序列中含有的唯一一个数为 $2^{\lceil\log_2 n\rceil}$。 :::::success[证明] 先把这个结论拆成答案上界和下界均为 $2^{\lceil\log_2 n\rceil}$ 证明。
  对于答案上界，可以直接构造证明，如何构造就留在后面，所以我们先证明答案下界。
  结论 1.1：最终的数一定不是奇素数的倍数。
  ::::success[证明] 考虑反证法。
  设一奇素数为 $P$。
  若对 $a_x,a_y$ 进行操作，设 $p=a_x\bmod P,q=a_y\bmod P$，则 $(a_x+a_y)\bmod P=(p+q)\bmod P,|a_x-a_y|\bmod P=|p-q|\bmod P$，如果我们想让最后的数是奇素数的倍数，那么我们需要在 $p\ne 0\lor q\ne 0$ 的条件下凭空制造出 $(p+q)\bmod P=|p-q|\bmod P=0$，同时由于 $p,q\in[0,P)\cap\mathbb N$，那么我们得到：
  $$(p+q)\bmod P=0\Rightarrow p=q=0\lor p+q=P\Rightarrow p+q=P$$ $$|p-q|\bmod P=0\Rightarrow p=q$$ 解得 $p=q=\dfrac{P}{2}\notin \mathbb N$，产生矛盾。
  证毕。
  :::: 最后的数不是奇素数的倍数，那么它一定能被表示为 $2^k$（$k\in \mathbb N$）。
  由于操作 $a_x,a_y$ 会产生一个更大的数 $a_x+a_y$，所以答案下界就是 $2^{\lceil\log_2 n\rceil}$。
  答案下界证毕。
  ::::: 现在我们要构造方案，注意到操作两个数 $0,x$ 能变成 $x,x$，再操作一次 $0,2x$，所以我们在序列有 $0$ 时能够将任意一个数乘 $2$，所以我们考虑将这些数全部操作成 $2$ 的非负整数次幂，比较容易想到具体过程：
  以序列 $\{a_{10}\}=\{1,2,3,4,5,6,7,8,9,10\}$ 为例：
• 若 $n$ 自身就是 $2$ 的非负整数次幂那么我们就递归大小为 $n-1$ 的子问题，但是这里 $10$ 不是 $2$ 的非负整数次幂，要继续往下走。
• 先取 $pos=2^{\lfloor\log_2 n\rfloor}=8$，在 $pos$ 左右对称取数操作，变成 $\{1,2,3,4,5,\color{red}4\color{black},\color{blue}2\color{black},8,\color{blue}16\color{black},\color{red}16\color{black}\}$。
• 观察发现子序列 $\{1,2,3,4,5\}$ 是一个更小的子问题，子序列 $\{4,2\}$ 整体除以 $2$ 后也是一个子问题，递归处理，当序列长度不超过 $2$ 时停止递归，因为已经合法。
• 最终，序列变为 $\{1,2,2,4,8,4,2,8,16,16\}$，操作次数为 $3$ 次。

然后我们考虑选择两个相同的数操作 $1$ 次得到 $0$，但是注意，这两个数不能等于 $2^{\lceil\log_2 n\rceil}$。
结论 2：当 $n\ne 2$ 时，一定能得到一个 $0$（下文简称序列合法）。
:::::success[证明] 首先当 $n$ 是 $2$ 的非负整数次幂时，长度为 $n$ 的序列合法当且仅当长度为 $n-1$ 的序列合法。
然后一个长度为 $n$（$n$ 不是 $2$ 的非负整数次幂，下同）的序列，操作一次后会产生 $n-pos$ 个 $2^{\lceil\log_2 n\rceil}$，且由于向下的两个递归长度一定小于 $pos$，所以不会再产生 $2^{\lceil\log_2 n\rceil}$，所以最后一共会有 $n-pos$ 个 $2^{\lceil\log_2 n\rceil}$，所以有 $pos$ 个不是 $2^{\lceil\log_2 n\rceil}$，在 $\lfloor\log_2 n\rfloor+1<pos$ 时序列一定合法，令 $t=\lfloor\log_2 n\rfloor\in\mathbb Z$，解不等式：
$$\lfloor\log_2 n\rfloor+1<pos\\Leftrightarrow\lfloor\log_2n\rfloor+1<2^{\lfloor\log_2n\rfloor}\\Leftrightarrow t+1<2^t\\Leftrightarrow t\ge 2\\Leftrightarrow n\ge 4$$ 接下来对 $n=2,3$ 时进行检验（CF 还怪良心，样例就是这两个），发现 $n=2$ 不合法，$n=3$ 合法。
证毕。
::::: 所以我们直接 $\Theta(n)$（可能由于实现方式导致 $\Theta(n\log n)$，但是肯定远远跑不满）找到相同的数构造出一个 $0$，然后让其它数暴力乘 $2$，最后还原 $0$ 即可。
此时，构造数无论是递归部分还是暴力乘 $2$ 部分显然都是 $\Theta(n\log n)$ 级别，但是两者都远远跑不满，实测在 $n=5\times 10^4$ 时操作数约为 $2.1\times 10^5$，虽然此时的操作数比序列长度不是最大的，但是可以看出即使最大时也并不大，通过暴力计算发现该比值最大为 $6.76$。
然后做完了。
时间复杂度为 $\Theta(n\log n)$（如果实现较劣可能变成 $\Theta(n\log^2 n)$），空间复杂度为 $\Theta(n)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-08 16:38:32

:::::info[题目基本信息] 考察：构造，哈希 hashing（$2900$）。
题目简介：
给定 $n$，有一集合 $\displaystyle S=\bigcup_{i=1}^n\{i\}$，问 $S$ 的最大子集 $S'$ 满足 $\displaystyle\prod_{x\in S'}x!\in\{p|p=k^2,k\in\mathbb Z\}$ 的大小，并给出一种 $S'$。
数据范围：

• $1\le n\le 10^6$

时间限制：4s。
空间限制：250MB。
::::: 结论：答案下界为 $n-3$。
:::::success[证明] 考虑凑平方。
$$\begin{aligned}\prod_{i=1}^ni!&=(\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(2i-1)!(2i)!)\times([n\equiv 1\pmod 2]\cdot n)!\&=(\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(2i-1)!^2)\times(\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}2i)\times([n\equiv 1\pmod 2]\cdot n)!\&=(\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(2i-1)!^2)\times 2^{\lfloor\frac{n}{2}\rfloor}\lfloor\frac{n}{2}\rfloor!\times([n\equiv 1\pmod 2]\cdot n)!\&=(\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(2i-1)!^2)(2^{\lfloor\frac{n}{4}\rfloor})^2\times 2\lfloor\frac{n}{2}\rfloor!\times([n\equiv 1\pmod 2]\cdot n)!\end{aligned}$$ 我们开始丢数，当 $n$ 是奇数的时候，我们丢掉 $n!$，然后我们丢掉 $2!$ 和 $\lfloor\dfrac{n}{2}\rfloor!$，最后一定剩下一个完全平方数。
证毕。
::::: 这时我们仅需判断子集大小为 $n,n-1,n-2$ 时是否有解即可。

• 大小为 $n$ 时：容易发现此时对于每一个质数，它总共出现了偶数次，那么我们可以考虑异或哈希，给每一个质数附一个随机值，然后这些数的乘积的哈希值就是它们的异或和，这样可以计算出每个数的阶乘的哈希值，进而计算出整个序列的哈希值，此时哈希值为 $0$。
• 大小为 $n-1$ 时：同上，此时扔去一个数的哈希值为 $0$，即整个数列的哈希值等于某个数。
• 大小为 $n-2$ 时，同上，此时可以使用 map 处理。

这样就做完了。
时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

code