幻影彭的彩虹

Hello World

置顶 | 发表于 2022-07-12 更新于 2022-07-13 分类于 System Test ， Basic Function Test

在无数久的 🐦咕咕咕后一个博客它建成了！

博客主要会收录这些东西：

自己在 OI 内外踩的坑。
对一些算法的想法和理解。
一些算法，技术技巧。
部分学习中的笔记。
曾经不会或者陌生的算法，数学，自然科学内容。
对学习内容的感悟与理解。
闲的没事写的科普或者技巧。
生活中的一些事。
其它

关于我自己：

常用 ID（一般不强调大小写）：幻影彭，琴风幻影，huan_yp，Phantom_Peng。

QQ：3051561876

一个热爱自然科学的，有些中二的男生。

0315 测试

T1

首先它可以四维偏序，但是难写难调常数还丑陋无比。

观察到三维的乘积不是很大，考虑对维度的乘积下手，把最小的那一维拿出来暴力，剩下的是三维偏序，是 $O(n^\frac{4}{3}\log^2 n)$ 的，还是比较难写，也比较难过。

于是干脆把最小的两维拿出来暴力，这样就是二维偏序了，可以 set，复杂度 $O(n^\frac{5}{3}\log n+n\log n)$，感觉复杂度不太平衡，考虑给查询平衡一下复杂度，对于第三维分类讨论，如果最长的一维超过 $O(n^\frac{2}{3})$，那么用 set，否则添加的时候在最长的一维的每一层暴力维护该层往上和往下遇到的第一个点的位置。

总复杂度 $O(n^\frac{5}{3}+n^\frac{4}{3}\log n)$，好写，常数小。

其实还有更聪明的暴力，每 $\sqrt q$ 次询问 BFS 一遍重构答案，然后其它的暴力。

能根号重构的前提条件是会做修改全在查询前面的情况。

T2

首先想到可以暴力 AC 自动机，但是这样的复杂度是 $O(nqm\sum)$ 的，大概是 $1.3\times 10^{10}$，过不了。

然后想到 $m$ 比较小，可以考虑用矩阵乘法优化，查询可以树链剖分一样搞，复杂度是 $O(nm^3+q\log^2nm^2)$ 的，理论上是 $10^9$ 级别的，还是过不了，实际上由于第二个查询的 $\log n$ 很小，是可以过的。

也考虑类并查集的方式，将询问放到 $lca$ 上，在 $lca$ 处并查集做合并，复杂度 $O(n\alpha(n)m^3+qm^2)$，实际上常数丑陋，无法通过。

事实上不带修的树剖可以做到 $O(q\log nm^2)$，直接在 $dfn$ 上开一维的数组维护 $top$ 到自身的前缀和即可，这个做法常数较大，过不了。

对有向链树剖时要注意顺序，具体的，线段树存储的是自顶向下的。跳树剖的时候是自底向上的。因此，对于 $u$ 到 $lca$ 的部分，应该查线段树的反向信息，并将单次查询的结果翻转后拼接起来。对于 $lca$ 到 $v$ 的部分，应该查线段树的正向信息，将单次查询的结果翻转后拼接起来最后翻转整个序列。

T3

可以树形 DP，然后发现好像一个点的转移复杂度只和它下面最浅的叶子的深度有关，好像可以类似长链剖分的做。

有一个问题是长链的转移比较不对劲，没法快速做。但是又因为复杂度是和最浅的叶子的深度有关，于是可以把链单独拿出来做转移。

对于有多个儿子的点暴力转移，对于只有一个儿子的一段链，可以算出这一段链的长度在链顶 NTT。

复杂度是有保证的，有多个儿子的转移，复杂度同长链剖分，单个儿子只会在链顶转移，而又因为每个点至多对 NTT 贡献 $\log$ 次每 NTT一次就会合并一次（注意到是较短链贡献一遍），所在子树大小翻倍，因此很容易证明其复杂度是低于 $O(n\log^2n)$ 的。

实际上上界是 $O(n\log n)$，因为合并两条单链的时候只有较短的那条单链贡献。

封装 NTT 的时候不要左移两遍，具体的，设置 multi 函数 $lim$ 参数的时候不要把 $lim$ 设成 $1<<\log_2(n)+1$，而应该设成 $\log_2(n)+1$。

0314

T1

需要最大化满足 $\operatorname{mex}(a[l:r])\ge k$ 的区间个数，又有一个很重要的性质，所有数的个数相差 $1$。

Case1

先从简单的情况考虑，只有 $01$，最大化 $\operatorname{mex} \ge1$ 的区间个数，记 $tot$ 为区间个数总数，它是可以取到 $tot-cnt_0$ 的，方式是 $01$ 隔着放。

Case2

稍稍推广一下，假设每个数的个数都相同，都是 $x$，最大数为 $m-1$，然后需要最大化 $\operatorname{mex} \ge m$ 的区间个数，我们可以以 $0,1,2\cdots m,0,1,2\cdots m,\cdots$ 的方式放，这样确实是最优的，因为每个长度不小于 $m$ 的区间都可以取到，而长度小于 $m$ 的区间一定取不到。

Case3

继续推广，假设每个数个数相差 $1$，最大数为 $m-1$，那么同样可以做到每个长度不小于 $m$ 的区间都满足条件，具体的，将有 $x+1$ 个的数先放一下，然后再放剩下的，每 $m$ 个循环一遍。

Case4

继续推广，现在不一定最大化 $\operatorname{mex}\ge m$ 了，而是 $\operatorname{mex}\ge a$ 了，先考虑所有小于 $a$ 的数，它们的相对顺序必定如 Case3，如果它们的相对顺序不为 Case3 的顺序，那么调整为 Case3 的顺序之后一定不会变劣，因为原有的合法区间调整后同样合法。

接下来的问题变成了在 Case3 的序列中插入若干个数，要最小化 $\operatorname{mex} <a$ 的区间个数，如果一个区间包含了至少 $a$ 个小于 $a$ 的数，那么它就一定合法，于是将小于 $a$ 的数看成 $0$，大于 $a$ 的数看成 $1$，要最小化 $0$ 个数小于 $a$ 的区间数。

我们插入 $1$ 的时候一定是尽可能连续的插入，具体的，任意两段 $1$ 至少间隔 $a$ 个 $0$，否则容易证明将这两段$1$ 移动到一起一定不劣（可能向左也可能向右），因此每一段 $1$ 互不影响，考虑一共有 $k+1$ 段，每一段是 $x_i$，所有不合法的段的贡献可以拆成含 $1$ 和不含 $1$ 的段的贡献。

$\begin{align} Ans&=[cnt_0(a-1)-k\frac{(a-1)(a-2)}{2}]+\frac{x_0(x_0+1)+x_k(x_k+1)}{2}+(x_0+x_k)(a-1)+S\\ S&=\sum_{i=1}^{k-1}\frac{x_i(x_i+1)}{2}+\frac{(a-1)(a-2)}{2}+2x_i(a-1)\\ \end{align}$

化简一下：

$Ans&=[cnt_0(a-1)-\frac{(a-1)(a-2)}{2}]+cnt_1\frac{4a-3}{2}-(x_0+x_k)(a-1)+\sum_{i=0}^k\frac{x_i^2}{2}\\$

前面那一坨只和 $a$ 有关，是个常数，考虑后面那一坨。

最终问题

有 $k+1$ 个整数变量 $x_i,i\in[0,k]$，满足 $\sum\limits_{i=0}^kx_i=W$，需要最小化 $-a(x_0+x_k)+\sum\limits_{i=0}^kx_i^2$，其中 $a$ 是一个常数。

首先这个式子在确定了 $x_0+x_k$ 之后就能 $O(1)$ 求最小值，而且是单峰的，可以三分，于是得到一个 $O(m\log n)$ 的做法。

我们需要一种能够线性做法，考虑对 $x_0+x_k$ 梯度下降。

最开始我把学习率设为 $\Large\eta=\frac{1}{e^{\sqrt t}}$，偏移量设为 $\Large\lceil f_\Delta(x)\eta\rceil$，常数差了一点，$f_\Delta$ 表示 $f(x)$ 的差分。

后面发现其实直接让它向梯度反方向移动 $\pm1$ 或者 $\pm2$ 就行。

由于这是个多组询问，而且每次 $W$ 变小，$a$ 变大，$a$ 变大感觉上最优解会右移，$W$ 变小则相反，不同问题的解连续性应该比较强，所以将初始解设定为上一次的最优解。

也许决策点也是单峰的，但我不会证。

复杂度 $O(能过)$ 或者是 $O(m)$。

另一种化简方式

还是考虑上面那个式子，最小化 $-a(x_0+x_k)+\sum\limits_{i=0}^k x_i^2$，考虑向每一个分配 $1$ 的贡献，显然先向 $x_0,x_k$ 分配最好，然后 $x_0,x_k$ 的一次项系数就被改变了，继续贪心分配就行。

0311测试

T1

限制是序列每个元素至少要大于左边一半的元素。

先考虑怎么算方案数，填值很不好做，考虑先把排名确定后再根据排名去填值。

然后我们需要的信息就是具体填了几个不同的数，然后就是简单的组合数，可以

T2

T3

筛法模板题。

本质上要算的是。

$\begin{align} Ans&=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\gcd(i,j)[k|\gcd(i,j)]\\ &=\sum_{g=1}^ngd(g)\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=g]\\ &=\sum_{g=1}^ngd(g)\sum_{i=1}^{\lfloor\frac{n}{g}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{g}\rfloor}[\gcd(i,j)=1]\\ &=\sum_{g=1}^ngd(g)\sum_{i=1}^{\lfloor\frac{n}{g}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{g}\rfloor}\sum_{k|\gcd(i,j)}\mu(k)\\ &=\sum_{g=1}^ngd(g)\sum_{k=1}^{\lfloor\frac{n}{g}\rfloor}\mu(k)\sum_{i=1}^{\lfloor\frac{n}{gk}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{gk}\rfloor}1\\ &=\sum_{g=1}^ngd(g)\sum_{k=1}^{\lfloor\frac{n}{g}\rfloor}\mu(k)\lfloor\frac{n}{gk}\rfloor^2\\ \end{align}$

现在已经可以算了，对 $g$ 数论分块，然后对 $k$ 再数论分块，然后杜教筛算几个函数的前缀和，两次数论分块的复杂度为 $O(n^{\frac{5}{6}})$，可以过了。

注意杜教筛的时候所有的前缀和其实都是算过的，所以能杜教筛，换成 min25 这些筛法是不行的。

可以继续推式子，枚举 $gk=T$：

$\begin{align} Ans&=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2\sum_{g|T}\mu(\frac{T}{k})d(k)k\\ &=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2\sum_{g|T}\mu(\frac{T}{k})(\operatorname{id} * \operatorname{id})(k)\\ &=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2(\mu * \operatorname{id} * \operatorname{id})(k)\\ &=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2(\phi * \operatorname{id})(k)\\ \end{align}$

$h=\phi * \operatorname{id}$ 是积性函数，可以杜教筛。

具体的，构造 $h 1 = \operatorname{id} \operatorname{id}$。问题变成了算 $\operatorname{id} * \operatorname{id}$ 的前缀和，它就是 $nd(n)$，可以杜教筛，也可以直接数论分块算：

$\sum_{i=1}^nd(n)n = \sum_{i=1}^ni\sum_{j|i} 1=\sum_{j=1}^n\lfloor\frac{n}{j}\rfloor$

310

发表于 2023-03-10 更新于 2023-03-13

0310测试

T1

树上单点修改，查一个点和所有祖先权值异或的最大值。

首先想到树剖，然后树剖每个节点都要维护 Trie，修改 $O(\log^2 n)$，查询 $O(\log^3 n)$，时间是 $O(n\log^3n)$ 的，空间是 $O(n\log^2n)$ 的，过不了。

然后它要查的是祖先，考虑直接用 dfs 序，然后变成了区间修改单点查询，时间复杂度降到了 $O(n\log ^2)$。空间还是过不了。

这个时候我想到可以根号重构，处理树的复杂度是 $O(n\log n)$，暴力询问是 $O(n)$，所以每 $\sqrt {n\log n}$ 个询问分块处理。

根号重构复杂度高了被卡了常。

实际上我们注意到 dfs 序那个询问是可以拆分的，把每个线段树节点的所有修改和询问离线下来做就可以了。

另外就是 Trie 可以写循环版本的，常数低很多。

T2

先考虑给一个数怎么算贡献，如果它只有一个二进制位为 $1$，那么简单积分一下就知道答案是 $2$。因为最后只会剩下最高位，所以考虑一个低位的贡献，显然它的贡献就是它为 $1$ 的概率，记作 $a$。

然后可以记录一下前一个 $a$，如果当前位是初始 $0$，那么它是 $1$ 的概率为 $\frac{a}{2}$，否则为 $1-\frac{a}{2}$。

此时有两种思路，其一是对 $a$ 的和进行数位 DP，其二是考虑每一对二进制位的贡献。

由于每一个二进制位对当前二进制位的贡献是可以拆分的，所以也就很容易了。

我用了第二种思路。

教训

数位 DP 时 long long 级别的数要取模，特别是 1ll<<x！一定要先取模再算乘法！
__builtin_clz,__builtin_ctz 在 $x=0$ 时没定义，数位 DP 时最好把 $0$ 先判了再做。

T3

暴力挂了。

原因是轮廓线状压换行的时候清空没有清干净。

for(int mask=0;mask<p3[n];mask++){
    g[0][mask]=min(min(g[0][mask],g[1][mask]),g[2][mask]); // 转移到下一行
    g[1][mask]=g[2][mask]=1e9; //清空上一行的无用信息，这句没加
}

vmware安装小记

发表于 2023-03-06

Vmware 安装小记

很久很久以前，hyp 使用不正确的软件并以不正确的方式安装了正确的 ubuntu，然后有一大堆问题，所以记一下安装 Vmware 的过程

选择 Vmware WorkStation Pro16 作为虚拟机软件，启用了 Hyper-V，Vmware 自动安装了一个东西
用 ubuntu 官网的 22.04 镜像。
配置 VmwareTool 的时候要先关机，将三个盘的物理驱动器改成自动检测。参考。

303

发表于 2023-03-03 更新于 2023-03-10

0303测试

考试

T2

考虑怎么去分析整个过程，比如怎么通过高度得到 $A$，如果从高到低的考虑每个高度的柱子，条件写出来是很麻烦的东西，因此我们从编号大到小考虑整个过程。

又注意到其实震 $n$ 次和震 INF 次没有区别，所以思考的时候可以从震 INF 次的角度去思考。

考虑加入一根新的柱子，记它的高度为 $h_i$。如果它前面的柱子中没有高度为 $h_i$ 的，那么它最终的高度就是 $h_i$，如果有，那么它的高度可能是 $[1,h_i)$，我们记每个柱子的最终高度为 $h’_i$，那么一根柱子的最终高度就是从 $h_i$ 开始扫到第一个没有被占用的高度。

于是有了一个朴素的暴力，记录一下哪些高度已经被占用，然后新增一个时如果需要保留就必须放到一个可以扫到的位置转移，否则就只能放到一段被占用的前缀中。

考虑优化，注意到我们只关心哪一段前缀被转移了，所以设 $dp[i][j]$ 表示考虑后 $i$ 个柱子，第 $i$ 个柱子恰好占用了一个位置使得只有 $[1,j]$ 都被占用的方案数。转移枚举下一段占用哪些位置，这样是不重不漏的。枚举下一段的过程也是一个动态规划，可以设 $f[i][j]$ 表示考虑了从前 $i$ 个。

另外还有一种做法，考虑

一件比较麻烦的事情是可以填相同的数，但是不妨将每个相同的数区分一下，最后除以一个 $2^n$。

不要把模数写错。

T3

考虑选定了点集之后具体位置在那里，应该是虚树的重心上，如果虚树的重心只有一个，那么答案显然为 $1$，因此奇数的情况答案为 $1$。

对于偶数的情况，如果存在两个重心，那么虚树上对应链都可以成为答案点，所以枚举每条链看两侧较小的那边的大小 $x$，它对人数小于 $x$ 的状态有贡献，这个可以放到最后取后缀 $\max$。

对于链上的统计问题考虑点分治，枚举当前点时查比它大的所有点的最长的，注意此时的大小不是分治的大小，需要另外算。

因为有序所以要正反各做一遍。

下面是点分治写错的几个细节：

要先 dfs 再把 $sz$ 加上去
分治中心到点的情况不要写错下标。
这里的 $0$ 应该取 -INF，因为如果不存在大小大于它的子树那么必须不能贡献。
偶数的情况也有可能不存在两个重心，此时如果只算链会漏，因此还需要和 $1$ 取 $\max$。

有的题最好还是写按题意模拟的暴力对拍，转化过程中有可能漏情况！

其它做法一

一件很震撼的事情是大小直接取分治时的大小是对的。考虑归纳的证明，分治到一棵子树时如果取到了向原重心的链的大小会被算小，但如果取到了这些点一定会在原重心被算到，所以是对的。

于是可以用桶优化到 $O(n\log n)$。

其它做法二

考虑定根后在每个点统计以它为 $lca$ 的路径的答案，然后答案的下标和 $sz$ 的较小值有关，因此可以考虑启发式合并，在一个点维护重儿子各个 $sz$ 深度的后缀最大值，暴力枚举轻儿子的每个 $sz$ 并统计答案，合并轻儿子暴力，另外会有根的贡献，但是根的深度最小，只会影响 $\sum\limits_{v\ne son_u} sz_v$ 个点的后缀最大值。

另外要考虑一条父子链的贡献，重儿子不好弄，于是考虑一个点最往上能到哪个位置，可以二分。实际上可以直接以重心为根做，就不用二分了，直接取根。

301

发表于 2023-03-01 更新于 2023-03-02

0301测试

考试

T1

考虑如何检查一个条件是否合法，如果最高位为任意，那么两边需要都合法，否则要求两边至少有一个合法。

考虑两边的检查，发现第 $i$ 层的节点个数为 $2^i$，总的情况数为 $2^{n-i}$，因此可以记忆化搜索一下。用一个 $mask$ 的前若干位表示限制，后若干位表示高位的数字即可。

也可以这样想：考虑算所有的情况，设 $T(n)$ 表示计算第 $n$ 层所有情况的复杂度，暴力计算有 $T(n)=2^n+4T(n-1)=2^{2n}$，实际上发现对于只有第 $n$ 层不同的情况可以只算一次，于是 $T(n)=2^n+2T(n-1)$，得到 $T(n)=n2^n$。

T2

做法一

考虑钦定 $A$ 组先选满，枚举 $A$ 组选满的位置计算对应概率然后再乘二。对于每一个位置 $p$，基本情况总数为 $\binom{p-1}{n-1}$，每种基本情况等概率取到，概率为 $2^{-p}$，分三类讨论

如果 $x_k<p$，那么 $k$ 个人既可以在 $A$ 组也可以在 $B$ 组，对应的基本情况数分别为 $\binom{p-1-k}{n-1-k}+\binom{p-1-k}{n-1}$。
如果 $x_k=p$，那么一共有 $\binom{p-k}{n-k}$ 种基本情况。
如果 $x_k>p$，首先 $p\notin X$，然后记 $c$ 为 $p$ 之前的 $x$ 个数，基本情况总数为 $\binom{p-1-c}{n-1}$。

于是有一个 $nq$ 的做法。

观察到查询的答案是一个二元函数 $f(p,x)$ ，对于 $x$ 较小的情况可以预处理前缀和，对于 $x$ 较大的情况，查询数比较少，可以暴力。于是有一个 $n\sqrt q$ 的做法。

进一步观察，$2^{-p}\binom{p-1-c}{n-1}$ 可以很容易的预处理 $2^{-p}\binom{p-1}{n-1}$ 的前缀和然后查询时乘上一个 $2^{-c}$。

对于 $2^{-p}\binom{p-1-k}{n-1-k}$，答案应该是：

$\begin{align} \sum_{p=x_k+1}^{2n-1}2^{-p}\binom{p-1-k}{n-1-k}&=\sum_{p=\max(n,x_k+1)}^{2n-1}2^{-p}\binom{p-1-k}{n-1-k}\\ &=\sum_{p=\max(n,x_k+1)}^{2n-1}2^{-p}\binom{p-1-k}{n-p}\\ &=\sum_{p=\max(n,x_k+1)-k-1}^{2n-1-k-1}2^{-p-k-1}\binom{p}{n-k-1}\\ \end{align}$

注意到 $\sum k$ 其实很小。

~~好吧，我不会线性做法，摆了。~~

做法二

先只算都在 $A$ 组的情况，然后分 $B$ 选满的位置 $p$ 所在的区间讨论。

$p>x_k$：令 $x_k$ 及之前每一种可能的硬币选择为基本情况，需要计算在 $x_k$ 处 $X$ 都取到 $A$ 且 $B$ 不能被选满的方案总数，隐含条件是 $x_k$ 之前 $A$ 也不能被选满。

可以暴力的算组合数，枚举剩下的 $x_k-k$ 个数有多少个分配到 $A$ 中，可以直接限制 $A,B$ 都满足要求，即 $\sum\limits_{i=\max(0,x_k-k-n+1)}^{n-k}\binom{x_k-k}{i}$。

然后 $\sum k$ 是比较小的，于是放宽一下限制，算 $\sum\limits_{i=\max(0,x_k-k-n+1)}^{n}\binom{x_k-k}{i}$ 再减掉，容易发现这个式子只和 $x_k-k$ 有关，而这个式子本身也不是很难算，进一步的将 $\max$ 的限制去掉，变成 $\sum\limits_{i=0}^n \binom{x}{i}$，然后对于 $x-n\ge0$ 的情况，需要减去 $\sum\limits_{i=0}^{x-n}\binom{x}{i}$。都可以拆组合数然后动态规划。
$\begin{align} \sum\limits_{i=0}^{x-n}\binom{x}{i}&=\binom{x-1}{0}+\sum\limits_{i=1}^{x-n}\binom{x-1}{i-1}+\binom{x-1}{i}\\ &=\binom{x-1}{0}+\sum_{i=1}^{x-n}\binom{x-1}{i}+\sum_{i=1}^{x-n}\binom{x-1}{i-1}\\ &=\binom{x-1}{x-n}+\sum_{i=0}^{x-n-1}\binom{x-1}{i}+\sum_{i=0}^{x-n-1}\binom{x-1}{i}\\ &=\binom{x-1}{x-n}+2\sum_{i=0}^{x-1-n}\binom{x-1}{i} \end{align}$

另一种考虑方式是算一个 $f_w$ 表示一共 $w$ 个，$A,B$ 都不超过的情况总数，然后需要减去 $B$ 抵到的情况数，然后又因为需要把 $A$ 超过的情况去掉，$A$ 超过是因为 $k$ 个被塞进了 $A$，分别枚举超过 $1,2,3\cdots k$ 个减掉对应的基本情况数即可。$f_w$ 的转移考虑直接放 $A,B$ 然后去掉不合法的情况。

$x_{i-1}<p<x_{i},i\in[1,k]$

将基本情况定为 $x_i$ 之前（不含）的硬币状态，限制有两个，$|B|$ 不小于 $n$，且 $X$ 内的是必须为 $A$ 的。满足 $A$ 限制的总情况数为 $2^{x_i-i}$。满足 $A$ 限制但不满足 $B$ 限制的情况数为 $\sum\limits_{i=0}^{n-1}\binom{x_i-i}{i}$，先扣掉。这里不需要考虑 $A$ 被选满，因为 $A$ 被选满的情况确实应该扣掉。然后再减去再 $x_{i-1}$ 之前就满足 $B$ 限制的所有情况，注意额外带一个 $2_{x_i-x_{i-1}-1}$ 的系数。

这里还会有一些误解，其实隐含了 $|A|<n$ 的限制，实际上如果这两个限制都满足那么这个隐含限制一定满足，因此不管这个隐含限制直接算也是可以的。

当使用容斥计算 “恰好” 时，应该减掉上一次的 “至少” 而不是 “恰好”，记录 $lst$ 的时候要注意。

T3

先考虑构造一种合法的解满足条件。挨个确定值的办法并不好弄。考虑先确定前 $i$ 个的大小关系，如果前 $i$ 个合法了，并且第 $i+1$ 个可以放到一个位置，满足前面没有不小于 $a_{i+1}$ 且存在至少一个 $a_{i+1}-1$，那么就合法。于是得到一个有解的充要条件：任何一个前缀 $a_i$ 值的集合连续。

现在考虑算 $i$ 位置的答案，它前面的不小于它的元素必须在它后面，它后面的元素可以线性扫一遍，维护前缀连续最大值算出来。

考虑优化，对于一个 $i$ 算答案的时候，就是要找到依赖它以及它前面不小于它的元素的所有元素。后面的比 $a_i$ 大的元素如果能在 $i$ 之后找到一个 $a_i$ 依赖，那么就可以被放在 $i$ 前面。

元素的依赖关系好像是构成一棵树的，于是建树，每个元素向它的第一个前驱连边，然后 $i$ 节点以及它同层左边的兄弟里所有节点都不能放在 $i$ 前面，于是算出了 $p_i$ 的最大值。

0228测试

发表于 2023-02-28 更新于 2023-03-01

0228测试

考试

T1

毒瘤计算几何。

考虑一步的过程，是从一个点的一个方向开始旋转，于是对所有目标点极角排序，极角相同的长度较长的放前面，查询就是要找到接下来的第一个长度小于当前长度的。

一个很暴力的想法是直接开始跳，如果遇到了相同的点说明有环，然后模环长再跳，这样每个点期望经过 $O(\log)$ 次，总共要处理 $O(nm\log n)$ 次，感觉很可做。

接下来的问题变成了如何快速查询。考场上觉得排序后确实是查第一个比它大的，但是要带上删除，于是考虑长度倒序做。然后想 set 暴力操作肯定要超时，然后考虑用并查集做删除操作，用优先队列维护长度的处理顺序。

很麻烦，写不出来。

实际上可以不带删，考虑找到第一个极角超过查询极角的位置，在上面二分第一个长度满足限制的，用 ST 表做长度查询，复杂度 $O(\log n)$。

找环的时候需要注意不是点重复而是边重复才出现环，判断需要再检查一下来向，需要记录当前点上一次访问时有几个点，走了多远，从哪个来的。

总复杂度 $O(Tnm\log^2n)$。因为卡不满所以能过。

带删的查询问题都很麻烦，考察之前先想想能不能不删。

T2

首先考察 $1$ 是不是重心，如果 $1$ 不是重心那么一定会向重心移动？不对，可以先往重心走一步，让重心的点相互消耗，然后往回去。

考虑目标点和 $1$ 之间的毛毛虫。毛毛虫任意两个端点都是可以相互抵消大小的。因此如果毛毛虫所有端点大小和为偶数且没有任何一个端点大小超过 $\frac{totalsize}{2}$，那么一定可以移动到目标点。

如果有一个大小超了，考虑能不能在它的内部抵消，是可以的，考虑计算一下某棵子树最少要将中心往自己的方向拉几步，同时也不难证明最少步数到 $sz$ 之间每一个奇偶性相同的步数都能取到。

最小步数是可以动态规划的，转移看是否有一个儿子的 DP 值超过其它儿子的大小总和，还要看当前子树大小奇偶性。可以拿个类记录一下 DP 值最大的儿子和对应的子树大小以及总的子树大小。因为如果有儿子 DP 值超过其它儿子总大小，那么这个儿子的 DP 值一定是最大的，所以这样没问题。

然后考虑计算答案，直接再 DFS 一遍，判断合法性的信息就是转移的那个信息，很容易合并的，额外算一个后缀和就行。

T3

最开始想能不能把限制弄成不包含或者不交，然后发现不行，由于 $x_i$ 可能相等，所以不交也是不现实的。然后想能不能从位置入手做，比如区间 DP 或者扫描 DP，还是不好处理。

就算是容斥，同样不好考虑位置。

考虑从值本身入手做，每段位置有一个限制，然后考虑一个限制，可能让它满足条件的段是一段区间，而且使值不同的限制满足的位置集合不交。说人话就是不同值的限制独立，一段上界相同的位置只会满足值是其上界的限制。因此可以上界不同的段分开做然后乘起来。

将区间弄成左闭右开方便处理，然后离散化暴力算每一段的上界，上界记在左端点。枚举每个值，暴力将每一段放进去，然后将对应的限制挂在新标号的位置上去。

然后设 $dp[i][j]$ 表示考虑到前 $i$ 个，上一个抵到上界的位置是 $j$ 的方案数，在右端点还需要将不满足挂上的限制的状态清掉。

复杂度 $O(q^2T)$。

其实有 $O(Tq\log q)$ 的做法，暴力算上界可以用单点改后缀查的树状数组优化，暴力放段的过程可以用 vector 记一下每一个值具体有哪些段和哪些限制。

动态规划中，先对限制的左端点取前缀 $\max$，然后可以考虑枚举最后一个 $1$ 的位置转移，然后转移可以双指针加标记搞定。

多项式算法

发表于 2023-02-21

多项式算法

多项式是组合计数题目中非常重要的工具。

约定

幂级数用大写字母表示，系数用对应的小写字母表示，对于 $F(x)$，$f_i$ 就是 $F(x)[x^i]$。

多项式乘法

应用

对于形如 $f_k=w(k)\sum\limits_{i+j=k}a_ib_j$ 的 $f_k$，可以利用多项式乘法在 $O(n\log n)$ 的时间里解决。

或者说，对于形如 $F(x)=A(x)\cdot(B(x) * C(x))$ 的幂级数 $F(x)$ ，可以在 $O(n\log n)$ 的时间里求出。

多项式求乘法逆

一般被描述对于一个 $F(x)$ 找一个 $H(x)$，满足 $F(x) * G(x)\equiv 1\pmod{x^n}$。

可以用定义法配合分治 FFT 在 $O(n\log^2 n)$ 的时间内解决：

$h_n=\dfrac{-\sum\limits_{i\in[0,n)}f_ih_{n-i}x^n}{f_nx^n}$

第二种方式是倍增法，假设我们已经求出了 $H’(x)$ 满足 $H’(x) F(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}}$。又显然有 $H(x) F(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}}$。两式相减得 $(H’(x) - H(x)) F(x)\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}$。平方得 $(H’(x) - H(x))^2 F^2(x)\equiv 0\pmod{x^n}$。

$\begin{align} (H'(x) - H(x))^2 * F^2(x)&\equiv 0\pmod{x^n}\\ H'^2(x)F^2(x)-2H'(x)H(x)F^2(x)+H^2(x)F^2(x)&\equiv 0\pmod{x^n}\\ H'^2(x)F(x)-2H'(x)+H(x)&\equiv 0\pmod{x^n}\\ H(x)&\equiv -2H'(x) - H'^2(x)F(x)\pmod{x^n}\\ \end{align}$

其中第二行到第三行先同时除以 $F(x)$ 再对 $F(x)$ 和 $H(x)$ 进行乘法得到 $1$。

对于 $n=1$ 我们显然有 $H’(x)=f_0^{-1}$，然后依次推出即可。