考试LIST [2020.11]

2020.11.01

$\texttt{Location:NOIP2020}$

得分：$\texttt{205/300,Rank1}$。

[11.01]-错误

目标不够准确，在 $\texttt{T1}$ 和 $\texttt{T2}$ 之间左右横跳......

$\texttt{T3}$ 最后一个点 $\texttt{MLE}$ 了，常数不够优秀。

[11.01]-部分正解

$\texttt{T1}$

妙题！

题面中有一个非常奇怪的条件：长宽均为奇数。

考虑充分利用这个条件进行构造。不难发现，对于任意一个矩形，其左右、上下位置的奇偶性是不相同的，这是从上面的条件可以直接推出的。

又两个矩形最多只交于边界，假设是左右两边相邻，则这其中一个矩形的左边和另一个的右边奇偶性相同。从而可以推出这两个矩形左边位置奇偶性不同。上下同理。

那么现在得出结论：两个相交的矩形，满足两个矩形上边界（或下边界）奇偶性不同，或左边界（或右边界）奇偶性不同。

现在做法就很显而易见了，按照左边、上边的奇偶性分成 $4$ 类，每一类一种颜色即可。

时间复杂度 $\mathcal{O}(n)$。

$\texttt{T2}$

考虑建立线段树，每一个节点表示的是数组 $a$ 在这个区间中对答案的贡献。对于一个点 $a_i$，他对答案的贡献就是：满足 $l\le i\le r,x\le a_i$ 的询问数。现在可以直接考虑区间赋值的做法，因为求原数组答案的时候可以看做做 $n$ 次单点的赋值。

当将 $[l,r]$ 全部赋值为 $v$ 的时候，如何快速计算 $[l,r]$ 中每一个位置，在变成 $v$ 之后的贡献？

可以考虑建立主席树，按照询问的 $x$ 值从小到大排序，并以这个 $x$ 值作为版本。当我们询问版本 $v$ 的时候，实际上就包括了询问值 $x$ 在 $1$ 到 $v$ 之间的所有询问了。

如果不需要算整个 $[l,r]$ 区间，而是更简单的问题：

将单点 $p$ 修改为 $v$，查询这个点修改后对答案的贡献。

我们可以参考树状数组的做法：对于一个询问 $(l,r,x)$，我们在版本 $x$ 的主席树上实际上需要将 $[l,r]$ 集体加 $1$ ，但如果改成差分，就只需要修改 $l$ 和 $r+1$ 两个位置了，同时主席树可以快速求出前缀和，因此可以通过差分再前缀和，求出某个单点 $p$ 在值变成 $v$ 的时候对答案的新贡献。

如何拓展到一个区间的修改？

同样的，我们可以模拟树状数组维护区间加，区间求和的套路，再维护一棵主席树即可。

这样的话，不难发现每当我们在线段树上修改，总是需要在主席树上求某区间变成某值的新贡献。容易看出，时间复杂度是 $\mathcal{O}(n\log^2 n)$ 的。

$\texttt{T3}$

题目实际上是求：$g*\sigma$。

有为人熟知的柿子：$\sigma=\text{Id}*1$。然后题目求的就是 $g*1*\text{Id}$。而狄利克雷卷积有结合律，所以可以先求 $g*1$。通过各种方法可以得到：如果设 $g*1=a$，则当 $n$ 为完全平方数时 $a(n)=1$，否则 $a(n)=0$。证明如下：

由于 $g$ 和 $1$ 均为积性函数，所以 $a$ 仍然是积性函数，把 $n$ 质因数分解，设：

$$n=p_1^{x_1}p_2^{x_2}...$$

那么 $a(n)=a(p_1^{x_1})\times a(p_2^{x_2})...$，单独取出一个 $a(p^x)$，可以发现其取值要么是 $1$，要么是 $0$。因为：

$$a(p^x)=g(1)+g(p)+...+g(p^x)$$

当且仅当 $x$ 是偶数时为 $1$。

所以只有 $n$ 中每一个质因数的幂都是偶数，$a(n)$ 才为 $1$，也就是完全平方数时取 $1$。

然后就可以单独考虑每一个完全平方数的贡献了，答案可以写成：

$$\sum_{i=1}^{\sqrt{n}} \sum_{j=1}^{\frac{n}{i^2}} j$$

后面就是一个等差数列求和，可以 $\mathcal{O}(1)$ 求解。这样就是 $\mathcal{O}(\sqrt{n})$ 的了，可以得到 $\texttt{70pts}$ 左右。

不难发现我们实际上只关心每一个 $\dfrac{n}{i^2}$ 的取值，考虑数论分块。这样就是 $\mathcal{O}(\sqrt[3]{n})$ 的了。

至于时间复杂度的证明的话，可以考虑类似二次根号的证法：

由于 $i\in [1,\sqrt{n}]$，那么分成 $[1,\sqrt[3]{n}],(\sqrt[3]{n},\sqrt{n}]$ 两段：

$i\in [1,\sqrt[3]{n}]$，那么 $i$ 的取值只有 $\sqrt[3]{n}$，显然 $\dfrac{n}{i^2}$ 只有 $\sqrt[3]{n}$ 个取值。

$i\in (\sqrt[3]{n},\sqrt{n}]$，那么 $\dfrac{n}{i^2}< \sqrt[3]{n}$，也只有 $\sqrt[3]{n}$ 个取值。

所以时间复杂度是 $\mathcal{O}(\sqrt[3]{n})$ 的。

2020.11.03

$\texttt{Location:NOIP2020}$

得分：$\texttt{210/300,Rank2}$。

[11.03]-错误

$\texttt{T3}$ 的 $\texttt{50pts}$ 写挂了......

常数太大了！！！

[11.03]-部分正解

$\texttt{T1}$

把物品表示为 $(a,b)$，意思为需要占用 $a$ 的空间，接着得到 $b$ 的空间。

不难想到将物品分为三类：$a<b,a=b,a>b$，他们分别 增大、不改变、减小 背包空间。

对于 $a<b$ 的物品，显然他们会不断增加背包的空间，先做肯定是优的。由于加入他们之后背包空间增加，所以贪心地先将 $a$ 值小的加入。

对于 $a=b$ 的物品，应该在背包空间最大的时候加入，也就是 $a<b$ 的物品全部加入后。

对于 $a>b$ 的物品，自然会放在以上两种情况的物品之后进行放入，最优的方案是按照其 $b$ 值从大到小依次加入。证明如下：

设现背包空间是 $V$，有两个物品 $(a_i,b_i),(a_j,b_j)$，满足 $a_i>b_i,a_j>b_j$。

假设先放入 $i$ 更优，则满足以下两个条件之一：

第一种：

$$ \left\{ \begin{array}{ll} V-a_i>0 \\ V-a_i-a_j+b_i>0 \\ V-a_j>0 \\ V-a_i-a_j+b_j<0 \end{array} \right. $$

显然可以得出 $b_i>b_j$ 的结论。

第二种：

$$ \left\{ \begin{array}{ll} V-a_i>0 \\ V-a_i-a_j+b_i>0 \\ V-a_j<0 \end{array} \right. $$

也就是无法直接放入 $a_j$。由于 $a_i>b_i$，所以 $b_i-a_i<0$，又 $V-a_j<0$，因此必然有：

$$V-a_i-a_j+b_i<0$$

与上面柿子矛盾，因此不会出现这种情况。

所以对于 $a>b$ 的物品，只需要按照 $b$ 值从大到小排序加入即可。

最后按照以上顺序模拟一遍，判断是否合法即可。

时间复杂度 $\mathcal{O}(Tn\log n)$。

$\texttt{T2}$

$\texttt{2020.10.07}$ 原题......可以考虑另外一种做法。对区间 $\gcd$ 和区间 $\min$ 建立两个 $\text{st}$ 表，二分长度。

对于一个区间，如果其区间 $\gcd$ 与区间 $\min$ 相等，则显然该区间合法。

时间复杂度 $\mathcal{O}(n\log^2 n)$。

$\texttt{T3}$

首先十分 $\text{naive}$ 的 $\text{dp}$ 可以设 $\text{dp[n]}$ 为长度为 $n$ 的合法划分数量。显然有：

$$\text{dp[n]}=\sum_{i=0}^{n-2} \text{dp[i]}\times f(n-i)+(r-l+1)\sum_{i=0}^{n-1} \text{dp[i]}$$

其中 $\text{dp[0]}=1$，$f(n)$ 为长度为 $n$，所有数字都在 $[l,r]$ 之间且公比不为 $1$ 的等比数列个数。公比为 $1$ 的时候比较特殊，最后一块就是在特殊处理。

不难发现，任意满足条件的公比都是有理数，因为等比数列增长较快，所以实际上 $f(n)$ 中 $n$ 的取值非常小，最多也就是 $\log r\approx 24$ 的样子（公比为整数则 $2$ 时达到最长，公比非整数时只关心分母是否除尽了）。这就是特殊处理公比为 $1$ 的等比数列的情况的理由。

那上面的转移方程前半部分下限可以紧很多，后半段实际是前缀和：

$$\text{dp[n]}=\sum_{i=\max(0,n-24)}^{n-2} \text{dp[i]}\times f(n-i)+(r-l+1)\sum_{i=0}^{n-1} \text{dp[i]}$$

这样就可以在 $\mathcal{O}(n\log r)$ 的时间做 $\text{dp}$。

由于前面有用的状态很少了，所以可以做矩阵快速幂，从而优化到 $\mathcal{O}(\log n\log^3 r)$。

现在考虑如何求 $f(n)$。容易想到一个 $\mathcal{O}(r^2\log r)$ 的简单做法，实际上就是枚举等比数列的前 $2$ 项，然后算一算他最多可以延伸多少位。但是这样太慢了，显然无法通过。

时间瓶颈在于计算 $f(n)$，因此考虑如何优化这个过程。不妨设公比为 $\dfrac{x}{y}$，由于公比大于 $1$ 与公比小于 $1$ 实际上可以一一对应，所以不妨先设 $x>y$，最后乘 $2$。设等比数列第一项为 $a_1$，则第 $n$ 项 $a_n=\dfrac{x^{n-1}}{y^{n-1}}a_1$。化一化柿子，可以写成这样的形式，设下式等于 $t$：

$$\dfrac{a_n}{x^{n-1}}=\dfrac{a_1}{y^{n-1}}=t$$

不难发现对于一个固定的长度 $n$ 与固定的 $\dfrac{x}{y}$，只要 $t$ 确定了，整个等比数列就是一定的。现在考虑一下 $t$ 的取值范围，由于 $a_n=x^{n-1}t,a_1=y^{n-1}t$，又公比大于 $1$，所以需要满足：

$$ \left\{ \begin{array}{ll} x^{n-1}t\le r \\ a_1=y^{n-1}t\ge l \end{array} \right. $$

然后就可以得到 $t\in [\lfloor\dfrac{l}{y^{n-1}}\rfloor,\lfloor\dfrac{r}{x^{n-1}}\rfloor]$，所以对于一个固定的 $n$，有 $\max(0,\lfloor\dfrac{r}{x^{n-1}}\rfloor-\lfloor\dfrac{l-1}{y^{n-1}}\rfloor)$ 个贡献。

特殊处理一下 $n=2$ 的情况，于是剩下的所有 $x,y$ 就都在 $\sqrt{r}$ 之内了。在 $1$ 到 $\sqrt{r}$ 之内枚举一下 $x$，然后枚举一个比 $x$ 小的 $y$。之后暴力从小到大枚举长度，判断这个长度在这样的 $\dfrac{x}{y}$ 下是否存在至少一个 $t$，如果已经不存在这样的 $t$ 了，则直接跳出循环即可。

由于会算重，所以还需要保证一下 $\gcd(x,y)=1$，也就是保证是最简分数。最后再构造一下大小为 $\log r\times \log r$ 的转移矩阵，矩阵加速即可通过，注意再加一维记录 $\text{dp}$ 值的前缀和来转移公比为 $1$ 的情况。

时间复杂度 $\mathcal{O}(\log n\log^3 r+ r\log r)$，但实际上并跑不满这个上界。

2020.11.09

$\texttt{Location:NOIP2020}$

得分：$\texttt{300/300,Rank1}$。

[11.09]-错误

很快写完了，但是每题各有一个锅......还是要积极对拍，提升代码能力。

[11.09]-部分正解

$\texttt{T1}$

考虑 $\text{DAG}$ 要怎么做：肯定是一条最长链的长度。

如果现在有环，那显然环上所有点颜色不同，对于这个环所连出的任何边，所对应的点也与这个环上的任意点颜色不同。那就直接 $\text{Tarjan}$ 缩点，把一个点的权值看做这个强连通分量的大小。

然后再求最大权值的链即可。

时间复杂度 $\mathcal{O}(n+m)$。

$\texttt{T2}$

考虑把方差那个柿子拆掉，可以变成：

$$\sum (x_i^2-2x_i\overline{x}+\overline{x}^2)$$

化一化，那题目要我们求的就是：

$$(n+m-1)\sum x_i^2-(n+m-1)^2\overline{x}^2$$

的最小值。后面那个实际上就是 $(\sum x_i)^2$

考虑到值域非常小，所以设 $\text{dp[i][j][s]}$ 表示走到 $(i,j)$，现在的数字和是 $s$ 的时候，最小的 $\sum x_i^2$ 是多少。

随便从左边和上面转移一下。

然后答案就是：

$$\max\Big\{dp[n][m][i]-i^2 \Big\}$$

时间复杂度 $\mathcal{O}(n^4)$。

$\texttt{T3}$

显然是树同构问题。

但是如果对其中一棵树每一个点都求一遍哈希值，时间复杂度 $\mathcal{O}(n^2)$ ，无法通过。

考虑用某一些特殊的点来代表一棵树。例如重心，一棵树最多有两个重心。于是可以对两棵树的至多 $4$ 个重心进行树形哈希，然后判断一下是否存在哈希值相同的即可。

至于多叉树树形哈希，可以对儿子按照哈希值为第一关键字，子树大小为第二关键字进行排序，然后随便哈希一下。

找到相同的根之后，再做一遍 $\text{DFS}$ 就可以找出两棵树的点的对应关系了。

时间复杂度 $\mathcal{O}(n\log n)$。

2020.11.10

$\texttt{Location:NOIP2020}$

得分：$\texttt{115/300,Rank3}$。

[11.10]-错误

做题要钻进一道题里，不能动不动换题......

[11.10]-部分正解

$\texttt{T1}$

首先特判一下不在序列中的数的情况。

把每一个数字离散化下来，记录若干前缀和数组，两个数字 $x,y$ 在一个区间内出现次数相同的充要条件是两个前缀和分别相等，或者是左端点前缀和的差与右端点前缀和的差相等。于是记录每个数出现的位置，暴力枚举两个序列中的数字 $x,y$，不难发现只有数字出现的位置会使前缀和数组变化，于是拿两个指针跳出现的位置，记录某一个位置两个数字前缀和的差，然后组合一下即可。

由于枚举一个数字 $x$ 后，再枚举 $y$ 只会跳 $2n$ 个位置，所以时间复杂度是 $\mathcal{O}(n^2)$ 的。

$\texttt{T2}$

看到恰好，就要想二项式反演。 ————鲁迅

首先把 $A,B$ 中均有数字的位置去掉，同时如果中间有满足条件的，则将 $S$ 减去。

那么现在每一个位置 $A,B$ 中恰有一个不为 $0$。考虑 $A$ 为 $0$ 的部分，另一半同理。可以设 $\text{dp[i][s]}$ 为：现在考虑到第 $i$ 个位置，已经有 $s$ 个满足条件的方案数。如果对原序列做，这显然是不正确的，因为无法确定这一位上放哪些数字会使 $s+1$。

但是如果我们按照 $B$ 从大到小排序，那么就可以做了。因为 $B$ 单调递减，所以任意在 $i$ 处可以对答案作贡献的数，在 $i+1$ 同样可以。所以只需要记录可用的 $A$ 中数字的后缀和即可转移，需要注意的是，这里我们不管除了我们钦定以外的数字，而是把他们先空着。

求出两个 $\text{dp}$ 数组后，设 $f(x)$ 为钦定 $x$ 个位置 $A>B$ 的方案数，这个直接拿两个 $\text{dp}$ 数组组合一下即可，由于还有很多部分没填，所以乘上阶乘。

不难发现这个 $f(x)$ 每一种方案中都至少有 $x$ 个位置满足条件，所以二项式反演一下即可。

时间复杂度 $\mathcal{O}(n^2)$。

$\texttt{T3}$

可以考虑离线再分治的方法。

如果现在在处理道路 $[L,R]$ 的操作，令 $\text{mid}=\dfrac{L+R}{2}$，那么可以 $\text{dp}$ 求出两个数组 $\text{Lv[i][x][y],Rv[i][x][y]}$ 分别表示处理了 $i$ 到 $\text{mid}$ 的边之后，$y$ 走到 $x$ 的最小代价，和处理了 $\text{mid}+1$ 到 $i$ 的边之后，$x$ 走到 $y$ 的最小代价。

如果有一个询问 $(l,r)$ 跨过了 $\text{mid}$，那么可以 $\mathcal{O}(n)$ 枚举中间点求出答案。否则，询问一定要么在 $[L,\text{mid}]$，要么在 $[\text{mid}+1,R]$，分治下去即可。

时间复杂度 $\mathcal{O}(nq+q\log m+n^2m \log m)$。

2020.11.13

$\texttt{Location:NOIP2020}$

得分：$\texttt{160/400,Rank2}$。

[11.13]-错误

$\texttt{T4}$ 花费太多时间......对构造题、规律题不够熟悉。

$\texttt{T1}$ 的 $\text{trick}$ 不够熟悉，导致没有通过。

$\texttt{T3}$ 应该先写好暴力，而不是只是想正解。

[11.13]-部分正解

$\texttt{T1}$

显然的是：先做更长的区间更优。

那么可以参照超级钢琴的 $\text{trick}$，丢进堆里搞，加一个 $\text{st}$ 表就可以很轻松地做到 $\mathcal{O}(Tn\log n)$，大概就是把区间丢进堆，优先做更长的，然后把区间按最小值位置划分成两个，再丢进堆里。

但是复杂度太高无法通过，先考虑省去这个堆。不难发现每次区间的大小是严格减小的，又我们从大到小考虑区间长度且区间长度不超过 $n$，所以挂在桶上从 $n$ 到 $1$ 依次考虑即可。

再考虑搞掉 $\text{st}$ 表。易于发现一个位置作为最小值的极大区间是固定的，且只有这些区间有贡献。所以单调栈搞出每一个位置左边、右边比他小的第一个位置，再直接挂到桶里就可以做到 $\mathcal{O}(Tn)$ 了。需要注意同样元素可能导致区间算重的情况。

$\texttt{T2}$

大大大大大大大大大模拟，每次暴力模拟操作即可，时间复杂度 $\mathcal{O}(n^2q)$。

码了 $\text{5.5k}$ 而已

$\texttt{T3}$

发现乘法非常烦人，于是直接求原根，离散对数转成加法。

为了简便，以下的同余符号统一为 $\bmod n-1$ 的情形。

令 $Ta_i,Tb_i$ 分别为 $a,b$ 中 $i$ 这个数字的个数，那么现在要求的就是：

$$\max_s\Big\{\sum \min(Ta_i,Tb_j)(i+j\equiv s)\Big\}$$

也就是枚举一个和 $s$，然后枚举由哪些值加起来为他。

令 $Tc_i$ 为 $s=i$ 的答案，并把上面的同余改成等于，那么：

$$Tc_i=\sum_{j+k=i} \min(Ta_j,Tb_k)$$

这个不太好搞，于是考虑枚举这个最小值，也就是构造这样的东西：

$Sa_{s,i}=[Ta_i\ge s],Sb_{s,i}=[Tb_i\ge s]$

然后 $\text{NTT}$ 卷起 $Sa_s$ 和 $Sb_s$，就可以得到两个值都在 $s$ 及以上的组数，和 $s+1$ 的答案作差就可以得到恰好 $\min=s$ 的组数。

这样直接做是 $\mathcal{O}(n^2\log n)$ 的，反而更慢了。

但是不难发现 $\sum Ta=\sum Tb=n-1$，那其中不同的取值最多是 $\mathcal{O}(\sqrt{n})$ 级别，因此我们只在 $Sa,Sb$ 发生变化的时候做卷积，这样就可以做到 $\mathcal{O}(n\sqrt{n}\log n)$。

继续考虑，对于一个数 $t$，桶中数字 $\ge t$ 的桶的个数不超过 $\dfrac{n}{t}$ 级别，如果暴力做一次，可以做到 $\dfrac{n^2}{t^2}$，这在 $t$ 较大的时候甚至比 $\text{NTT}$ 还优秀很多。所以我们设 $t$ 以上的部分做暴力，以下做卷积，可以获得 $\mathcal{O}(tn\log n+\dfrac{n^2}{t^2})$ 的复杂度。

根据出题人的估算 $t$ 在取 $\sqrt[3]{\dfrac{n^2}{\log n}}$ 的时候复杂度是 $\mathcal{O}(n^{\frac{4}{3}}\log^{\frac{2}{3}}n)$ 的......实现上 $t$ 取 $8$ 到 $10$ 即可。

$\texttt{T4}$

是 $n$ 为奇数时，仅有 $n=1$ 时有解，应该比较显然，偶数貌似一定有解，这样就可以得到 $\text{30pts}$。

对于正解做法，可以考虑构造一个很大的合法解，通吃所有询问。

通过打表找规律可以发现一些东西，这是我的方法：

可以找到以下这些矩形：

4
1 2 3 4 
5 1 4 3 
6 7 1 2 
7 6 5 1 

还有：

8
1  2  3  4  5  6  7  8  
9  1  4  3  6  5  8  7  
10 11 1  2  7  8  5  6  
11 10 9  1  8  7  6  5  
12 13 14 15 1  2  3  4  
13 12 15 14 9  1  4  3  
14 15 12 13 10 11 1  2  
15 14 13 12 11 10 9  1  

后面的就搜不出来了，但是通过这两个矩形可以发现一些共性：

主对角线都为 $1$。

关于主对角线对称的位置，两数之差为 $n-1$。

那这样的话，我们就可以考虑只找右上的部分：

4
1 2 3 4 
  1 4 3 
    1 2 
      1 

和

8
1  2  3  4  5  6  7  8  
   1  4  3  6  5  8  7  
      1  2  7  8  5  6  
         1  8  7  6  5  
            1  2  3  4  
               1  4  3  
                  1  2  
                     1  

很快发现，$n=8$ 的最左边正好是 $n=4$ 的情况，其下方也是 $n=4$ 的情况。中间有很显然的规律。

所以直接把 $n=2$ 的手动构造出来，然后让程序自己推到 $1024$ 就可以了。

时间复杂度 $\mathcal{O}(n^2\log m)$。

2020.11.14

$\texttt{Location:NOIP2020}$

得分：$\texttt{160/400,Rank1}$。

[11.14]-错误

$\texttt{T3}$ 最后没做出来......

[11.14]-部分正解

$\texttt{T1}$

毒题，不想写。咕了算了

$\texttt{T2}$

首先考虑没有空腔的情况。如果把每一个黑点当做一个平面图上的点，相邻的黑点连边。考虑欧拉定理，即 $V+F=E+2$，其中 $V$ 是点数，$F$ 是面数，$E$ 是边数。由于没有空腔，所以在这个图上的面数恰好是四元环个数 $+1$，若令四元环个数为 $C$ 的话，那么 $V+C-E=1$。

然后可以计算一下横边、竖边、点、四元环个数的前缀和，然后就可以求了。

考虑有空腔的情况，如果一个矩形中有空腔，那其边界向左右上下延伸之后仍然不合法。所以可以先找出所有空腔，这至多是 $\mathcal{O}(n^2)$ 级别的，记录下包括这个空腔的最小子矩形 $(x_1,y_1,x_2,y_2)$，那么固定了上下右边界之后，每一个子矩形是对左端点的限制，也就是上下右边界被包括的子矩形，其左端点一定不能被包含。

那么对于 $(x_1,y_1,x_2,y_2)$，在我们枚举的上边界 $\le x_1-1$ 的时候，在 $(x_2+1,y_2+1)$ 这个位置打上 $y_1-1$ 的标记，也就是说包含这个矩形的上下右边界的时候，其左端点一定不能 $\le y_1-1$，否则一定包含这一个子矩形。

因此只要把矩形按 $x_1$ 从大到小排序，倒序枚举上边界，然后暴力枚举下边界与右边界，再拿上述方法，单调地维护每一个左边界的区间即可。

时间复杂度 $\mathcal{O}(n^3)$。

$\texttt{T3}$

不难发现，加边操作实际上就是把排列划分成若干段，然后对一些段进行翻转，再对段进行排列的过程。

所以现在要求的就是所有划分段数 $\le k+1$ 的方案数之和。

设 $f_i$ 为恰好 $i$ 段的方案，$g_i$ 为至多 $i$ 段的方案。

那么：

$$g_k=k^k$$

后面那个实际就是对排列进行划分，其生成函数应该是 $x+2x^2+2x^3+2x^4...$，意思是长度为 $1$ 的段不能翻转，但是其他长度均可翻转。随便化一下可以成以上的封闭形式，$k$ 次方就是划分成 $k$ 段。最后对 $k$ 段进行排列，就 $\times k!$ 即可。

为什么 $g$ 是至多？因为存在一些方案，我们看似划分出了 $k$ 段，但是当他们接在一起的时候可能恰好有多段连接在了一起，所以至多是 $k$ 段。

化一化上面的柿子，有：

$$g_k=k^k$$

二项式定理展开：

$$g_k=k!\sum_{i=0}^k \binom{k}{i}2^i[x^{n-k}]\dfrac{1}{(1-x)^i}$$

$$=k!\sum_{i=0}^k \binom{k}{i}2^i\binom{n-k+i-1}{i-1}$$

然后这个一看就可以卷，所以随便拆一下组合数卷一下即可求出 $g$。

改一下意义，把 $f,g$ 系数向左平移一位，意义就变成恰好/至多有 $i$ 个位置使得相邻两数差的绝对值 $> 1$。

可以得到：

$$g_i=\sum_{j=0}^i \binom{n-1-j}{i-j}f_j$$

大概就是枚举哪里接起来。套路拆组合数：

$$g_i=\sum_{j=0}^i \dfrac{(n-1-j)!}{(i-j)!(n-1-i)!}f_j$$

乘以一个 $\dfrac{i!\times j!}{i!\times j!}$：

$$g_i=\sum_{j=0}^i \dfrac{(n-1-j)!\times j!}{(n-1-i)!\times i!}\binom{i}{j}f_j$$

那么：

$$i!(n-1-i)!g_i=\sum_{j=0}^i \binom{i}{j}j!(n-1-j)!f_j$$

这就变成了我们喜闻乐见的二项式反演标准形式，令 $F_i=i!(n-1-i)!f_i,G_i=i!(n-1-i)!g_i$，二项式反演过去：

$$F_i=\sum_{j=0}^i \binom{i}{j}(-1)^{i-j}G_j$$

再拆掉组合数就可以卷了。

所以，先卷出 $g$，然后变成 $G$，卷出 $F$，再还原为 $f$ 即可。

最后答案就是：

$$\sum_{i=0}^k [x^i]f$$

时间复杂度 $\mathcal{O}(n\log n)$。

$\texttt{T4}$

咕咕咕

2020.11.18

$\texttt{Location:NOIP2020}$

得分：$\texttt{224/400,Rank1}$。

[11.18]-错误

$\texttt{T3}$ 有大概 $\texttt{16pts}$ 来不及写了......

[11.18]-部分正解

$\texttt{T1}$

这题和之前某一次考试的一道题非常像。大概思路还是分治，每次用类似猫树的方法从 $\text{mid}$ 向两侧做 $\text{dp}$，然后只更新那些跨过 $\text{mid}$ 的询问。剩下的就左右递归。

需要注意的是，将 $\text{mid}$ 左右合并的时候，可以很简单地做到单个询问 $\mathcal{O}(m^2)$，但是这还是太慢了一些，而对两个数组做前缀和，又会算重。因此考虑只对 $\text{mid}$ 左侧/右侧的 $\text{dp}$ 值进行前缀和，这样就不会算重了。

时间复杂度 $\mathcal{O}(n\log n+mq)$。

$\texttt{T2}$

这题貌似有些签到？

首先易于发现的是，如果对一个 $i$，其合法的祖先集合是 $S_i$，那么 $S_i=S_{i-1}$ 的一个子集 $\cup \{i\}$。因为显然除了 $i$ 之外，$i$ 的任意合法祖先都一定要满足 $i+1$ 的条件。

所以可以维护一个栈，里面维护当前的合法祖先集合。每次考虑弹出栈顶，如果 $i$ 不是当前栈顶节点子树内部的节点，那对 $i$ 及 $i$ 以后的所有节点，这个栈顶节点都不会有任何贡献，弹掉即可。

至于判断是否在子树内，考烂了都......直接 $\text{dfn}$ 就可以了。

时间复杂度 $\mathcal{O}(n)$。

$\texttt{T3}$

首先可以考虑 $u=v$ 的 $\text{Subtask}$。先建立出 $\text{Kruskal}$ 重构树，需要注意的是：这里的 $\text{Kruskal}$ 重构树是多叉树的版本，这可以保证一棵树建出的 $\text{Kruskal}$ 重构树是唯一的。

对于每一个 $\text{Kruskal}$ 重构树上的非叶子节点，相当于是要将其若干儿子所对应的树，用这个节点代表的权值的边连接。如果我们设他有 $m$ 个儿子，每一个儿子的子树中，真实的点的个数分别为 $a_i$，那么根据 $\text{Prufer}$ 序列的推论，连接他们的方案数为：

$$\prod_{i=1}^m a_i \Big(\sum_{i=1}^m a_i\Big)^{m-2}$$

暴力做就可以拿到这一档部分分。

接着考虑 $u\ne v$ 的时候的做法。发现上面的东西完全与 $u,v$ 的距离无关，因此我们希望通过魔改上述柿子并使用 $\text{dp}$ 来将 $u,v$ 的距离加入我们考虑的范围。

首先我们找出在 $\text{Kruskal}$ 重构树中深度最深的，并且子树内包括 $u,v$ 的节点，称其为 $\text{rt}$。不难发现，除了 $\text{rt}$ 这棵子树以外的部分都可以随便连，因为他们与 $u,v$ 的距离没有关系了。

更为关键的是如何处理 $\text{rt}$ 的子树。不难发现任意 $\text{rt}$ 的子树中，至多存在 $u,v$ 中的一个，所以分为：没有 $u,v$ 中任意一个/存在 $u,v$ 中一个 两种情况进行讨论。

大概的思路是，对于一个节点 $x$，我想要从其每一个儿子 $y$ 的子树中，拿出一些节点放在 $u,v$ 之间的关键链上。若该子树内不存在 $u$ 或 $v$，那这个子树可以贡献任意长度的链（可以为 $0$），但是若该子树内存在一个，那么该子树一定要贡献非 $0$ 的长度，并且这个特殊点必须是这条关键链的一端。

那么就可以考虑点 $x$ 的前 $k$ 棵子树内，拉出了一条长度为 $l$ 的关键链的方案数了，这个转移可以考虑类似背包的方法。

$\texttt{T4}$

首先考虑一下 $k=1$ 的 $\text{Subtask}$，把 $k=1$ 带入就成了：

$$\sum_{i=0}^n a^ib^i\binom{n}{i}$$

十分显然的二项式定理，答案就是：

$$(ab+1)^n$$

考虑把这个思路给拓展到任意 $k$ 的情形。我们可以定义一个数 $z$ 满足 $z^k=a$，当然这个 $z$ 不见得是一个实数。

那上面的柿子可以表示为：

$$\sum_{i=0}^n (zb)^{ik}\binom{nk}{ik}$$

不考虑上面 $ik$ 的限制。那么如果求：

$$\sum_{i=0}^{nk} (zb)^{i}\binom{nk}{i}$$

那直接又可以二项式定理，变成：

$$(zb+1)^{nk}$$

把以上 $(bz+1)^{nk}$ 看做一个多项式 $f(z)$ ，那实际上我们需要的就是：

$$\sum_{i=0}^{n} z^{ik}\times [z^{ik}]f$$

不难发现上面的 $z^{ik}=a^i$，所以可以写成：

$$\sum_{i=0}^{n} a^{i}\times [z^{ik}]f$$

这可以直接 $\texttt{NTT}$ 快速幂，每次把 $a\times [x^{i}]f$ 加到 $[x^{i\bmod k}]f$ 上就可以了。

时间复杂度 $\mathcal{O}(\log nk\times k\log k)$。

2020.11.19

$\texttt{Location:NOIP2020}$

得分：$\texttt{320/400,Rank1}$。

[11.19]-错误

考试中想到 $\texttt{T3}$ 大致思路，但是没有深入思考，导致最后没有 $\texttt{A}$ 掉。

[11.19]-部分正解

$\texttt{T1}$

首先有一个十分显然的数位 $\text{dp}$ 做法，可以拿一个 $\text{map}$ 维护 $\text{dp}$ 值，但是这只能跑过 $\text{50pts}$ 的样子。

考虑枚举数字长度，并枚举 $7$ 的个数来进行 $\text{dp}$。具体来说，分为是否有前导 $0$ 两种情况分类讨论，当考虑到一个当前位放数字没有限制的位置时，就开始枚举接下来放多少个 $7$，再枚举每一种数字放多少个，背包+组合数转移即可。

$\texttt{T2}$

看到异或，就要想 $\text{Trie}$。————鲁迅

令 $\text{v[i]}$ 为从根 $1$ 到 $i$ 路径上权值的异或和。那么 $x$ 与 $y$ 之间的路径的权值即是 $\text{v[x] xor v[y]}$。

题目中有一个非常有用的条件：树形态随机，再根据题中连边方式可以判断出：树高是 $\log$ 级别。

那么先将所有的 $\text{v}$ 加入一棵 $\text{01Trie}$。每次到达一个点 $u$，枚举其儿子 $v$ 的时候计算边 $(u,v)$ 的答案。具体来说，每次暴力从 $\text{01Trie}$ 中删除 $v$ 子树内所有的 $\text{v}$，然后暴力把子树中每一个 $\text{v}$ 放到 $\text{Trie}$ 中匹配最小异或和来更新 $(u,v)$ 的答案，接着暴力把 $v$ 子树内的 $\text{v}$ 加回 $\text{Trie}$，最后递归进入 $v$。

看起来十分的暴力，但是由于有树高是 $\log$ 这个优秀的性质，所以我们可以发现，每一个点会被从 $\text{Trie}$ 中删除、加入 $\text{Trie}$ $\mathcal{O}(\log)$ 次，并查询 $\mathcal{O}(\log)$ 次。加上 $\text{Trie}$ 的一个 $\log$，就得到了 $\mathcal{O}(n\log^2 n)$ 的优秀复杂度。

当然，如果追求更高级的做法，可以按照 $\text{dfn}$ 建立可持久化 $\text{Trie}$，每次删掉一个子树，实际上就是去掉可持久化 $\text{Trie}$ 的一个区间，然后再进行暴力查询。但是复杂度是一样的

$\texttt{T3}$

如果我们令区间 $[l,r]$ 中颜色 $i$ 的出现次数分别为 $c_i$，那么区间 $[l,r]$ 的答案就是：

$$\prod (c_i+1)$$

就是每一种颜色可以不选，也可以选 $c_i$ 个中的一个，一共 $c_i+1$ 种方案。

这样就可以很简单地离线做了，直接莫队即可。

至于强制在线的话，可以考虑分块。

首先处理出每一个块内每一个颜色的出现次数，然后暴力处理出任意两个块及其中间的块的答案，每次暴力处理左右两边的部分即可。至于修改，实际上就是先乘上之前的 $c_i+1$ 的逆元，更新 $c_i$，再乘回来。

时间复杂度 $\mathcal{O}((n+q)\sqrt{n})$。

所以是不是所有强制在线的莫队题都可以分块搞啊

$\texttt{T4}$

标算太劲看不懂

$\text{zxyhymzg}$ 是我们的红太阳！

如果我们令满足条件 $a^2+b^2=c^2$ 的三元组 $(a,b,c)$ 为一个勾股数组，且 $\gcd(a,b,c)=1$ 的勾股数组称为本原勾股数组，那么有结论：

$a,b,c\le n$ 的本原勾股数组数量是 $\mathcal{O}(n)$ 级别的。

不仅如此，他还有十分简洁的构造方式：

对于任意奇数 $a,b$ 满足 $\gcd(a,b)=1$，存在一个斜边为 $\dfrac{a^2+b^2}{2}$ 的本原勾股数组且一一对应，至于构造的话，他是 $(a\times b,\dfrac{b^2-a^2}{2},\dfrac{a^2+b^2}{2})$。

那么这个东西就可以在 $\mathcal{O}(n\log n)$ 的时间内解决了，并且这个 $\log$ 是 $\gcd$ 的。

先考虑第一象限的这 $\dfrac{1}{4}$，最后 $\times 4$ 即可。

首先得出所有整点：

$$\sum_{i=1}^n \lfloor\sqrt{n^2-i^2}\rfloor$$

然后根据以上的本原勾股数组，令其斜边的数组为 $s$，那么需要减去：

$$2\times \sum_{i} \left\lfloor\dfrac{n}{s_i}\right\rfloor$$

$\times 2$ 是因为直角边可以互换。

所以答案就是：

$$4\times \sum_{i=1}^n \lfloor\sqrt{n^2-i^2}\rfloor-8\times \sum_{i} \left\lfloor\dfrac{n}{s_i}\right\rfloor$$

时间复杂度 $\mathcal{O}(n\log n)$。

2020.11.21

$\texttt{Location:NOIP2020}$

得分：$\texttt{50/400,Rank6}$。

垫底了啊......

[11.21]-错误

考试时开题顺序不够清晰，导致没有深入理解题目。

很多本来应该拿到的分挂了，应该要把能拿到的分拿稳才行啊。

考试中由于精神不佳等情况，掉线了......

[11.21]-部分正解

$\texttt{T1}$

显然 $a,b$ 是相对独立的，可以通过直接对 $a$ 排序依次合并来得到 $a$ 的最大值。

然后发现，由于每次是在之前合并的结果中合并一个，所以两个 $b$ 中至少有一个 $0$，通过计算可得，在 $x$ 个二元组合并之后结果中的 $b=2^{x-1}-1$。直接考虑状压 $\text{dp}$。

首先可以有最简单的做法：设 $\text{dp[x][S]}$ 为：已经用了 $S$ 中的二元组，得到了 $a=x$ 的方案数。

这转移是很简单的，依照题意分类即可。

但是发现第一维是很大的，考虑优化一下。回想一下上述求 $a_{\max}$ 的做法，不难发现 $a$ 的所有取值是 $\mathcal{O}(n)$ 级别的。所以直接把所有可能的 $a$ 离散化，然后转移即可。

时间复杂度 $\mathcal{O}(n^2\times 2^n)$。

$\texttt{T2}$

首先在模数与 $a,b$ 互质的时候，有一个十分显然且自然的扫描线做法。之所以需要模数与 $a,b$ 互质，是因为需要求出 $a,b$ 的逆元。

考虑正解。发现 $n$ 并不大，如果真的是扫描线大可放大数据范围。而如果我们以每一个卫星的位置将整个二维平面划分，即按照 $x,y$ 坐标划分，那么最多会出现 $n^2$ 个矩形。

首先预处理出对于每一个矩形，其左上、左下、右上、右下的点，到距离其最近的那个端点的权值，这里可以通过光速幂或者预处理幂来做到 $\mathcal{O}(n^2)$。

接着对于每一次询问，我们首先找出他属于哪一个矩形，然后只需要更新从四个角到该位置的距离即可。

时间复杂度 $\mathcal{O}(n^2+q\log n)$。

$\texttt{T3}$

建立 $\text{AC}$ 自动机，考虑跳 $\text{fail}$ 的意义：实际上在某一个节点跳 $\text{fail}$ 意味着删除该节点所代表的字符串的一个前缀。

设 $S=S'+B,T=B+T'$，那么 $S$ 跳 $\text{fail}$ 一定可以跳到 $B$ 这个节点，同时 $T$ 走 $\text{trie}$ 的边同样可以走到 $B$。那么现在我们实际上求的就是：

代表 $S$ 的节点在 $\text{fail}$ 树上的链上，与代表 $T$ 的节点在 $\text{trie}$ 树上的链上的节点的并的深度最大值。

直接把所有询问离线下来，然后走 $\text{trie}$ 树。走到一个新点，实际上就是为 $\text{fail}$ 树上这个节点的子树增加一个 深度为当前串长的贡献。如果直接树链剖分，可以做到 $\mathcal{O}(n\log^2 n)$。

实际可以更快：子树加一个值可以使用 $\text{dfn}$ 加线段树区间 $\max$ 解决，当我们走到一个 $T$ 的节点时，在线段树上询问其 $S$ 点的值即可。

但是在遍历 $\text{trie}$ 的时候，我们需要进行回溯并撤销某一些线段树的标记，所以下传标记不可取，又我们只询问单点值，所以标记永久化，然后套一个可回退即可。

时间复杂度 $\mathcal{O}(n\log n)$。

$\texttt{T4}$

连边操作实际上是对一个数字进行加减。为了方便，将长度为 $n$ 的序列映射到 $0$ 到 $n-1$。

根据直觉，当 $S$ 中某一个元素 $S_i$ 很小的时候，他或许会连很多边。所以我们先设一个数 $m$，分别考虑 $m$ 以上与以下的 $S_i$。

对于所有 $S_i\le m$，假设我们现在希望从 $x$ 到 $x+g$，那么一定有方程：$\sum a_i\times S_i = g$。也就是我们可以从 $m$ 及其以下的 $S_i$ 中每一个选若干次来凑成 $g$，显然 $a_i$ 可正可负。

考虑构造一个方法使得能够这样加减并不越界。设我们当前凑出的数字是 $v$，初始 $v=0$，希望到 $g$。当 $v\le m$ 的时候，如果存在一个还没有拿出来用来更新的 $-S_i$，那就让 $v$ 变为 $v-S_i$，显然 $v-S_i\ge 0$。若不存在这样的 $-S_i$，那么所有 $S_i$ 前面的系数都是正的，同时 $g$ 不越界，所以直接加是不会越界的。

当 $v<m$ 的时候，一定存在一个 $S_i\le m$，使得 $v+S_i\le 2m-1$。

所以我们希望 $2m-1\le n-1$，解出来 $m$ 可以 $=\dfrac{n}{2}$。令 $d$ 为这些 $S_i$ 的 $\gcd$，按模 $d$ 分组，那通过 $S_i$ 互相连边的都会在同一组了。

若所有 $S_i>\dfrac{n}{2}$，那么会存在一些“孤立点”，即 $i-S_i<0,i+S_i>n-1$，也就是无法连边。记 $V=\min\{S_i\}$，那么孤立点满足 $n-V\le i<V$，一共 $2V-n$ 个。把他们累加入答案，然后把 $n$ 与所有 $S_i$ 全部减去 $2V-n$。

这样最小值就变成了 $V-(2V-n)=n-V< \dfrac{n}{2}$，回到了存在 $S_i\le \dfrac{n}{2}$ 的情形。

接着考虑满足 $S_i>\dfrac{n}{2}$ 的 $S_i$。当 $d+S_i\le n$ 的时候，按 $d$ 分的每一组中 $S_i$ 都会连出一条边了。所以我们可以令新的 $d'=\gcd(d,S_i)$。

显然 $d$ 在一直变小，所以满足上述条件的 $S_i$ 会越来越多。把 $S_i$ 从小到大排序，显然就可以正确更新 $d$ 了。

仍然剩下的 $S_i$ 满足 $d+S_i>n$ 且 $S_i>\dfrac{n}{2}$。那么可以向右连出边的最大位置是 $n-S_i$，向左连出边的最大位置是 $n$。由于 $n-S_i<d$，所以可以将 $n$ 缩小为 $n'=d+(n\bmod d)$，剩下的 $S_i$ 变成 $S_i'=n'-n+S_i$。

由于模意义下分组，答案是不变的。

需要注意的是，缩小之后的 $n'$ 中，可能存在一个完整的 $d$ 块向最后不完整的块连的边，这些边在缩小规模之后需要被加入，所以若存在不完整的块，就在集合中加入 $d$。

每一次，我们要么 $\text{mod}$ 最小值，要么全体减。这类似将区间求 $\gcd$，可以证明最多递归 $\mathcal{O}(\log n)$ 层。加上排序，复杂度是 $\mathcal{m\log^2 n}$ 的，但实际上跑得飞快。

2020.11.22

$\texttt{Location:NOIP2020}$

得分：$\texttt{295/400,Rank1}$（实际上之前看过 $\texttt{T4}$）

[11.22]-错误

$\texttt{T3}$ 应该取拿一些部分分的，少了很多分。

[11.22]-部分正解

$\texttt{T1}$

首先考虑建出最短路图，那么显然两个人都只会在最短路图上走。

接着考虑使用 $\text{dp}$ 来计算，不妨令 $\text{dp[x][y]}$ 为两人分别走到 $x,y$ 的方案数，那么最后就是 $\text{dp[T][T]}$。

如果不考虑除了 $S,T$ 路径上的点不交，那么转移是十分 $\text{naive}$ 的，只要考虑从能到的前驱节点转移即可。

但是加入了路径上的点不交这个条件之后，我们不能从形似 $\text{dp[x][x]}$ 的前驱节点转移。这稍微有一些麻烦，主要是有可能会错过一些状态。

不妨定义一下两个节点的大小。令 $d_x$ 为 $S$ 到 $x$ 的最短路。那么第一关键字为 $d_x$，第二关键字是 $x$，从小到大排序。

那么当我们现在需要得到 $\text{dp[x][y]}$ 时，优先从大小更大的节点的前驱转移。也就是只修改 $x,y$ 中的一个，将其变为其某前驱。这很显然会走到所有可能的有交状态。因为每次让 $d$ 更大的缩小，所以只要有节点重叠的，都会这样被缩到。

直接记忆化搜索即可，时间复杂度 $\mathcal{O}(nm)$，但实际上根本跑不满。

$\texttt{T2}$

套路：对于形似这种每次将一个序列分开为两个的计数问题，可以考虑枚举这个断开的位置。

首先考虑枚举哪个位置的点作为根，设该位置为 $x$，则当前状态的贡献为：左子树，即该点左侧位置的贡献；右子树，即该点右侧位置的贡献；该点 $rs-ls$。

前两个是一样的问题，所以先考虑计算当前点的 $rs-ls$。可以先计算出当 $x$ 作为根的时候所有方案的 $\sum rs$ 与 $\sum ls$，然后直接减就可以了。

记 $G_i$ 为长度为 $i$ 的序列中，所有方案中根的下标的和。那么有：

$$G_n=(n-1)!\sum_{i=1}^n i=\dfrac{n\times(n+1)}{2}\times (n-1)!=\dfrac{(n+1)!}{2}$$

也就是枚举最大值在哪一个位置，然后别的位置可以 $(n-1)!$ 随便排。

再设 $F_i$ 为长度为 $i$ 的序列的答案。若求 $F_n$，假设现在选 $x$ 这个位置作根，那么令 $a=x-1,b=n-x$ 那么贡献分为两部分，转移方程是：

$$F_n=\sum_{a+b=n-1} \binom{a+b}{a}(b!F_a+a!F_b+[a>0][b>0](a!G_b-b!G_a+x\times a!\times b!))$$

前面就是分成左右两边之后的贡献，一边确定之后另一边可以任意排列。后面是该点的所有贡献，$x\times a!\times b!$ 是右边的根的下标的偏移量。最后还需要组合一下，乘 $\binom{a+b}{a}$ 即可。

这就是 $\mathcal{O}(n^2)$ 的了。

考虑优化一下，那么就拆掉柿子：

$$F_n=\sum_{a+b=n-1}\binom{a+b}{a}(b!F_a+a!F_b)+\sum_{a+b=n-1,a>0,b>0} \binom{a+b}{a}(a!G_b-b!G_a+x\times a!\times b!)$$

$$=\sum_{i=1}^n \binom{n-1}{i-1}((n-i)!F_{i-1}+(i-1)!F_{n-i})+\sum_{i=2}^{n-1} \binom{n-1}{i-1}((i-1)!G_{n-i}-(n-i)!G_{i-1}+i\times (i-1)!\times (n-i)!)$$

$$=\sum_{i=1}^n \binom{n-1}{i-1}((n-i)!F_{i-1}+(i-1)!F_{n-i})+\sum_{i=2}^{n-1} \binom{n-1}{i-1}(\dfrac{(i-1)!(n-i+1)!}{2}-\dfrac{(n-i)!i!}{2}+i\times (i-1)!\times (n-i)!)$$

$$=\sum_{i=1}^n \binom{n-1}{i-1}((n-i)!F_{i-1}+(i-1)!F_{n-i})+\sum_{i=2}^{n-1} \binom{n-1}{i-1}(\dfrac{(i-1)!(n-i)!(n-i+1)}{2}-\dfrac{(n-i)!(i-1)!i}{2}+i\times (i-1)!\times (n-i)!)$$

$$=\sum_{i=1}^n \binom{n-1}{i-1}((n-i)!F_{i-1}+(i-1)!F_{n-i})+\sum_{i=2}^{n-1} \binom{n-1}{i-1} \dfrac{(i-1)!(n-i)!(n+1)}{2}$$

$$=\sum_{i=1}^n ((n-1)!\dfrac{F_{i-1}}{(i-1)!}+(n-1)!\dfrac{F_{n-i}}{(n-i)!})+\sum_{i=2}^{n-1} \dfrac{(n-1)!(n+1)}{2}$$

发现每一项都有 $(n-1)!$，且还有 $\dfrac{F_i}{i!}$ 的形式，所以整体除一个 $(n-1)!$：

$$\dfrac{F_n}{(n-1)!}=\sum_{i=1}^n (\dfrac{F_{i-1}}{(i-1)!}+\dfrac{F_{n-i}}{(n-i)!})+\sum_{i=2}^{n-1} \dfrac{(n+1)}{2}$$

$$=\sum_{i=1}^n (\dfrac{F_{i-1}}{(i-1)!}+\dfrac{F_{n-i}}{(n-i)!})+\dfrac{(n-2)(n+1)}{2}$$

$$=2\sum_{i=1}^n \dfrac{F_{i-1}}{(i-1)!}+\dfrac{(n-2)(n+1)}{2}$$

那么令 $H_i = \dfrac{F_i}{i!}$，那么有：

$$ H_n=\left\{ \begin{array}{ll} 0 & ,n \le 2\\ \dfrac{2\sum_{i=1}^{n-1} H_i+\dfrac{(n+1)(n-2)}{2}}{n} & ,n > 2 \end{array} \right. $$

显然可以前缀和+线性推逆元做到 $\mathcal{O}(n)$。

$\texttt{T3}$

神奇的三合一。

对于 $\text{type=1}$，发现数据范围很小，于是直接状压。

设 $\text{dp[x][S]}$ 为操作了 $x$ 次，现在状态是 $S$ 的方案数。这样的话转移很慢，因为我们还需要枚举一个合法的区间进行翻转，所以时间复杂度是 $\mathcal{O}(n^32^n)$ 的，无法通过。

易于发现，每当我们进行一次翻转，$S$ 中的 $1$ 恰好减少一个，且在数字大小上会变小。因此可以搞掉 $x$ 一维，然后就是 $\mathcal{O}(n^22^n)$ 就可以了，有点卡但是实际上有效状态很少，可以通过。

对于 $\text{type=2}$ 且 $k\le n+1$，考虑 $\text{dp}$。

当我们翻转一个区间，一定会在两侧出现 $00$ 的情况，那么就不可能出现跨过 $00$ 的合法区间了。

因此，当我们做一次操作时，相当于将一个问题划分为三个独立的子问题。如果我们直接枚举三块的大小，那么复杂度是 $\mathcal{O}(n^3k^3)$ 的，无法通过。但是，如果我们先将两段合并，用辅助数组记录，然后再加入第三块进行合并，那两个数组的更新都是 $\mathcal{O}(n^2k^2)$ 的了，可以通过。

对于 $\text{type=2}$ 且 $k=n+1$ 的时候，发现 $n$ 很大，所以可以猜一波结论。

通过使用第二种做法中的 $\text{dp}$，可以发现答案为：

$$\prod_{i=1}^n (2i-1)$$

也就是在 $2n$ 以下所有奇数的乘积。对于 $n\le 10^9$，可以考虑分块打表，令 $5\times 10^6$ 或 $10^7$ 为一块，打出表来就可以了。当 $n\le 10^{18}$，无法分块打表，但是由于模数是奇数，所以当 $2n-1\ge \text{mod}$ 的时候，答案被模成了 $0$！所以判断一下，超出则输出 $0$ 即可。

$\texttt{T4}$

好题！

首先可以点分治，暴力枚举四种区间大小的情况是可以做的。但是这里说另一种更为有趣的做法：

如果我们只连接所有边权在 $[l,r]$ 之间的边，显然 $\max-\min \le r-l$，令所有的方案数为 $G_{l,r}$，而 $F_{l,r}$ 为恰好 $\max=r,\min=l$ 的方案数。

我们会发现，$G$ 类似于一个二维平面上的二维前缀和，而 $F$ 是单点。所以如果我们求出了 $G$，则可以通过容斥来得到 $F$，具体来说：

$$F_{l,r}=G_{l,r}-G_{l+1,r}-G_{l,r-1}+G_{l+1,r-1}$$

那么现在考虑求 $G$。

不难发现，我们所需要的所有 $G$ 的区间长度为 $k,k-1,k-2$ 三种，考虑每次对同一种长度同时求解。假设现在我们已经将 $[l,r]$ 的边全部连接，设 $c_i$ 为每一个联通块的大小，那么：

$$G_{l,r}=\sum \dfrac{c_i(c_i+1)}{2}$$

也就是联通块内任意两点都是一种方案。

然后就可以用线段树分治+可回退并查集了，时间复杂度 $\mathcal{O}(n\log^2 n)$，但是实际上常数挺大的 T了一个点 或者可以考虑直接 $\texttt{LCT}$，应该速度差不多吧（bushi

2020.11.24

$\texttt{Location:NOIP2020}$

得分：$\texttt{156/400,Rank3}$

神仙 $\texttt{Ender\_zzm,rhdeng,ObsidianY}$ 出的好赛！

[11.24]-错误

$\texttt{T2}$ 花费时间太长，而且因为使用了 $\text{multiset}$ 而沦为暴力分......

$\texttt{T3}$ 可以乱搞的，然后删掉了......

[11.24]-部分正解

$\texttt{T1}$

这实际上是杨辉三角的一个经典性质，答案是：

$$\text{Fib}_{2n+1}$$

$\text{Fib}$ 是斐波那契数列。

至于证明，可以把杨辉三角画出来，根据组合数递推公式可以发现恰好某一对角线的和是前两个对角线和的和。

然后矩阵快速幂就可以了，时间复杂度 $\mathcal{O}(\log n)$。

$\texttt{T2}$

考虑构造一个通解。

先拿出整个序列中出现次数最多的数字 $x$，把其他数字平均地分在两个 $x$ 中间。如果有多个数字出现次数同为最大，那么就看做一个数字，然后把剩下的数字平均分。

至于正确性，可以将其他所有数字排序，然后轮流放在第一个空、第二个空......循环地放，显然不会有两个相同的数字放在同一个空中。那么直接可以推出答案，设最大出现次数为 $c$，出现次数为 $c$ 的有 $x$ 个数字，那么答案为：

$$\left\lfloor\dfrac{n-c\times x}{c-1}\right\rfloor+x-1$$

对于修改，开权值线段树就可以了。时间复杂度 $\mathcal{O}(q\log a)$。

$\texttt{T3}$

好题！

由于两个中有一个 $x,y$ 都加一，很烦，所以我们令新的坐标为 $(x-y,y)$，不难发现这样两个操作就变成了 $x+1$ 或 $y+1$。

然后考虑类似猫树的方式，对 $x$ 分治，每次求一个 $\text{mid}$，求出左边某点 $(x,y)$ 能到 $\text{mid}$ 这一列的哪些位置，并求出 $\text{mid}$ 这一列每个位置能否到右侧某一个位置，然后只考虑跨过 $\text{mid}$ 的询问。

发现这个算法只有可达/不可达，所以可以 $\text{bitset}$ 优化，找从左往右有哪些中间点可行，只需要将两个 $\text{bitset}$ 与起来调用 $\text{any()}$ 即可。

令 $n=\max\{x_i-y_i\},m=\max\{y\}$，那么时间复杂度为 $\mathcal{O}(\dfrac{n^2m\log m}{\omega} + q)$。

$\texttt{T4}$

好题！

无标号很烦人，所以考虑转化为有标号。由于无标号实际上就是对标号的置换，所以考虑求有标号的之后使用 $\text{Burnside}$ 引理。

考虑求某一个置换的不动点个数。设这个置换分成若干环 $l_i$，那么首先对于一个环内，若长度为 $x$ 的边在图中存在，那么所有环上距离为 $x$ 的点之间都有边。加上自环，一共有 $\left\lfloor\dfrac{l_i}{2}\right\rfloor+1$ 种长度的边。对不动点的贡献是：

$$\prod_i 2^{\lfloor\frac{l_i}{2}\rfloor+1}$$

对于两个环之间的边，发现若两点之间有边，则一次会连上 $\text{lcm}(l_i,l_j)$ 条边，所以一共 $\dfrac{l_il_j}{\text{lcm}(l_i,l_j)}=\gcd(l_i,l_j)$ 种边可以选。对不动点的贡献是：

$$\prod_i \prod_{j<i} 2^{\gcd(l_i,l_j)}$$

发现我们在上面没有在意置换具体是多少，而只是关心了每一个环的长度。那么考虑再乘上一种环的分配可以是多少个置换：

$$\dfrac{n!}{\prod l_i!\times \prod c_i!}\times \prod (l_i-1)!=\dfrac{n!}{\prod l_i\times \prod c_i!}$$

其中 $c_i$ 是长度为 $i$ 的环的个数。实际上就是分成这么多组，然后每一组可以做圆排列，长度相同会使方案算重，需要除掉。

$n!$ 和 $\text{Burnside}$ 前面的 $\dfrac{1}{n!}$ 正好消掉，所以答案就是：

$$\sum_{\{l_i\}} \dfrac{\prod_i 2^{\lfloor\frac{l_i}{2}\rfloor+1}\times \prod_i \prod_{j<i} 2^{\gcd(l_i,l_j)}}{\prod l_i\times \prod c_i!}$$

由于 $n\le 60$，所以可以暴力搜出所有划分方案，然后累加答案即可。

2020.11.26

$\texttt{Location:NOIP2020}$

得分：$\texttt{100/400,Rank5}$

[11.26]-错误

$\texttt{T2}$ 花费了超过 $\text{1h}$，实在不划算。

$\texttt{T3}$ 码量大，写锅了。而且最后没有时间写暴力了，还是要模拟考场情形写暴力啊......

[11.26]-部分正解

$\texttt{T1}$

考虑模拟，由于模式串很短，所以考虑找出所有匹配方案。

可以设 $S$ 的某一位与模式串的哪些位置可以匹配，对于下一位，只要看之前哪些位置可匹配，同时这一位也可以匹配，就把这里设置为可匹配。

更妙的写法是记录上一位能与模式串哪些位置匹配为 $\text{pre}$，那么当碰到 $*$ 或者 $[]$，就在当前更新这一位的时候，同时更新上一位的数组 $\text{pre}$，由于 $\text{pre}$ 是顺序枚举的，所以最新的更新也会被遍历到，这样可以极大减少码量。

令模式串为 $T$，那么时间复杂度为 $\mathcal{O}(|T|\sum |S|)$。

$\texttt{T2}$

对于这一类子树大小的问题，可以考虑计算每一个点的贡献。更一般地，对于某一些与某种特殊性质状态的大小有关的计数，可以考虑对每一个单点判断其成为合法状态的情况数。

期望显然是假的，只要最后 $\times \dfrac{1}{n!}$ 即可。

那么首先考虑把一条边下面的子树大小换成每一个点的贡献。对于一个点 $x$，不难发现只有 $x$ 到根的这条链上的边被删除才有可能让 $x$ 对答案有 $1$ 的贡献，但是不一定每一条边删除时 $x$ 都有贡献。先只管链上的边，设 $x$ 到根要经过 $d$ 条边，那么把 $x$ 到根的链上的边映射成其深度，删除顺序就变成了一个 $1$ 到 $d$ 的排列。

考虑一个排列有多少个位置代表的边被删除时 $x$ 对答案有贡献。不难发现当一个深度更深的边被删除之后，深度更浅的边被删除就不会使 $x$ 有贡献了。所以一个排列对答案的贡献就是前缀 $\max$ 的个数。

再使用一遍上面的 $\text{trick}$，考虑所有排列的前缀 $\max$ 的总和。那么单独考虑一个数 $a$ 在多少方案中成为前缀 $\max$。不难发现当 $a$ 是一个前缀 $\max$，则比 $a$ 大的都在 $a$ 之后，把这 $d-a+1$ 个数字排列，方案数为 $(d-a+1-1)!=(d-a)!$，因为 $a$ 必须放第一个，其他的随便排在后面。再考虑剩下 $a-1$ 个小的，他们可以随便插空，一开始有 $d-a+2$ 个空，每加入一个新数则空位 $+1$，所以总体方案数是：

$$(d-a)!\times (d-a+2)^{\overline{a-1}}$$

化一下柿子变成：

$$\dfrac{d!}{d-a+1}$$

那么对于 $1$ 到 $d$ 的所有数字，其方案数总和就是前缀 $\max$ 的个数，是：

$$\sum_{i=1}^d \dfrac{d!}{d-i+1}=d!\sum_{i=1}^d \dfrac{1}{i}$$

因此对于一个深度为 $d$ 的点，其贡献如上。那么 $\text{DFS}$ 一遍计算每一个点的深度，剩下的就只需要预处理前缀逆元即可。

时间复杂度 $\mathcal{O}(n)$。

$\texttt{T3}$

首先对于一个集合的点，对其他点有贡献的其实至多只有两个点，也就是其“直径”端点。建立虚树，边权是两点树上路径的长度，然后就可以求出所有的集合的“直径”。

对于一个点，实际上其答案就是与所有集合的“直径”中较远的点的距离的 $\min$。

找出每一个集合的“直径”在原树上路径的中点，如果在边上就把两边的点都设为其中点。可以考虑换根 $\text{dp}$，在每一个中点上挂上以其为中点的路径长度的 $\dfrac{1}{2}$ 的最小值。那么对于一个点 $x$ 的答案就是：

$$\min_p\{dis(x,p)+v_p\}$$

其中 $p$ 是一个中点。

$\text{DFS}$ 换根 $\text{dp}$ 即可。

同时可以考虑线段树。同样求出“直径”中点，考虑被中点分割的两部分，他们分别被一个点给贡献。可以化简一下柿子，然后得到一个关于点的深度的柿子，要求他的 $\min$ 的话，每一个中点会对树上某一些节点贡献值。

其贡献的点形如一棵子树或一棵子树中再去掉一棵子树，同时需要做 $\text{chkmax}$ 的操作。但是发现我们每次只需要查询单点，所以标记永久化加 $\text{dfn}$ 即可。

$\texttt{T4}$

考虑区间 $\text{dp}$。

设 $\text{dp[i][j][t][u]}$ 表示：

区间 $[i,j]$ 比 $i-1,j+1$ 更早被删除，删除 $[i,j]$ 时在 $j+1$ 之后位置上第一个没有被删除的点为 $t$，同时区间 $[i,j]$ 中所有 $[i,u]$ 中的点都先被删除，的时候的最大权值。

那么可以枚举区间 $[i,j]$ 中最晚被删除的点 $k$，再枚举左区间 $[i,k-1]$ 的 $t$ 为 $v$，然后就可以得到 $\text{dp}$ 方程：

$$\text{dp[i][j][t][u]}=\max_{k\in[u,j],v\in[k+1,j+1]}\{\text{dp[i][k-1][v][u]}+\text{dp[k+1][j][t][v]+w(i-1,k,j+1,t)}\}$$

其中 $w(a,b,c,d)=(p_a-q_b)^2+(p_b-r_c)^2+(p_c-s_d)^2$，也就是这四个点的贡献。

首先显然左区间继承原区间的 $u$，右区间继承原区间的 $t$，同时右区间中 $[k+1,v]$ 需要在 $v$ 之前被删除，否则左区间第一个能跳到的点不会是 $v$。

这样的话状态 $\text{dp[i][j][t][j+1]}$ 有意义却没有被更新。也就是 $[i,j]$ 都要在 $j+1$ 之前删除，这根据我们的定义是显然的。所以需要特殊更新一下，实际上也就是 $k$ 的枚举没有限制了。

可是这样的 $\text{dp}$ 会算漏一些情况，例如删除顺序 $31425$(数字小表示先删除)，但是可以证明这种删除顺序不会使答案更大，因为 $t$ 的取值只影响 $(p_{i+1}-s_{i+2})$，不会更劣。证明待补

所以时间复杂度是 $\mathcal{O}(n^6)$，然而常数极小，大概在 $\dfrac{1}{720}$ 的样子？可以通过。

2020.11.27

$\texttt{Location:NOIP2020}$

得分：$\texttt{191/300,Rank2}$

[11.27]-错误

$\texttt{T3}$ 爆 $\text{unsigned long long}$ 了，要开 $\text{double}$，还是要仔细计算才行。

$\texttt{T2}$ 想很久都想不出来......状态太差了。

[11.27]-部分正解

$\texttt{T1}$

给出以下定义：

危险集合：即将被其儿子感染的点的集合。
边缘集合：已经被感染且未封城，连接未被感染的点的集合。
危险儿子集合：每一个边缘集合中的点所连接的，可能被其感染的儿子的集合。

考虑分为被儿子感染或被父亲感染。

对于被儿子感染，只需要每次在某一个点被感染，或被感染的点被解封的时候，将其父亲丢入危险集合即可。

对于被父亲感染，发现父亲一定属于边缘集合，那么可以记录每一个点的危险儿子集合，当一个点被解封且未被感染，则将其加入其父亲的危险儿子集合，并将父亲加入边缘集合。

当试图判断判断一个点是否会被其儿子感染时，首先该点一定在危险集合中，其次他必须有一个未被封且感染的儿子。那么可以通过数组记录，每一个点有多少未被封且感染的儿子，每次儿子被感染/被封/解封时都更新其父亲的数组即可 $\mathcal{O}(1)$ 判断。

当一个城市被封，则使用懒惰删除法，若该点在父亲的数组中被计数，则将自己从父亲的数组中删除即可。

若一个城市解封，考虑以下情况：

• 若可以感染父亲，则将父亲的数组 $+1$，将父亲加入危险集合。
• 若可以感染儿子，则将自己加入边缘集合。
• 若可被父亲感染，则将自己加入父亲的危险儿子集合，将父亲加入边缘集合。
• 若可被儿子感染，则将自己加入危险集合。

再考虑进行一轮传播时的情形。

首先遍历危险集合，若一个点的数组值不为 $0$，则说明当前有一个未被封且感染的儿子可以来感染他。接着遍历边缘集合，对于边缘集合中每一个点，若其未被封，则遍历其危险儿子集合，试图感染这个危险儿子。结束一轮之后，清空危险集合、边缘集合与遍历过了的危险儿子集合。

最后是当一个点被感染的时候，对状态的影响。

首先自己一定加入边缘集合，若没有危险儿子也没有关系；当自己的父亲还未被感染，则自己加入父亲的数组，并将父亲加入危险集合即可。

如果使用 $\text{set}$ 模拟上述过程，复杂度 $\mathcal{O}((n+q)\log n)$，但是发现有重复元素也没有关系，所以换成 $\text{vector}$ 即可做到 $\mathcal{O}(n+q)$。

$\texttt{T2}$

$\text{zxyhymzg}$ 是我们的红太阳！

对于一个点 $x$，显然其到根的链上的所有黑点我们都会保留。对于其白点的祖先，若除了 $x$ 这棵子树之外的部分中存在一个黑点，那一定可以将该黑点翻上来，放在这个祖先的位置上。

那么现在单独考虑一个点对答案的贡献 又是你。

若该点为黑，则其贡献为子树内黑点的个数。因为我们一定有方法将其放在某一个黑点的上面。

若该点为白且只有一棵子树内有黑点，则贡献为 $0$。因为当我们考虑这棵子树中的黑点时，没有别的子树的黑点来替换这个白点，所以无法让这个点成为黑点，故贡献是 $0$。

若该点为白点且至少有两棵子树内有黑点，则贡献为子树内黑点的个数。当我们考虑一棵子树内的黑点时，就将另一棵子树内的黑点翻上来替换该白点，对每一个子树内的黑点都可以做这样的操作。

因此，首先树链剖分，对于一个黑点，将答案加上其子树内部的黑点个数；对于一个白点，若其包含黑点的子树个数 $\ge 2$，则也将答案加上其子树内部的黑点个数。

考虑激活线段树，当一个点变黑，则将该点激活，树剖向上更新链上黑点的贡献。再考虑暴力上跳，更新每一个祖先的有黑点子树个数，再对刚跳上来的点打上标记，当遇到一个被打上标记的边时跳出即可。不难发现一条边最多被遍历一次，所以这里复杂度是对的。

每次加入一个新点之后，只需要查询全局的和即可。时间复杂度 $\mathcal{O}(q\log ^2 n)$。

$\texttt{T3}$

距离是 $\sqrt{\sum_{i=1}^n (b_i-a_i)^2}$，去掉根号，单独考虑一个柿子：$(a_i-b_i)^2$，由于是二次函数，所以当 $a_i-b_i$ 越大，则其值越大且其导数越大。

因此我们希望每一个 $a_i$ 都尽量接近其 $b_i$，而有若干 $a_i\ne b_i$ 的时候，我们也希望其 $|a_i-b_i|$ 相等。

发现由于 $a_i$ 需要非负，所以当一个 $b_i$ 越大时，$a_i$ 就算要变小也更难变负。因此考虑将 $b$ 从大到小排序。

依次考虑用排在前面的多少个数字来填满 $C$ 的和，后面的都令其为 $0$。那么就可以算出前面的这些数字距离各自的 $b$ 多远，这个数字加上后面数字的平方和即为当前这种情况的最优答案，这里我们只需要近似，所以可以使用浮点数计算。

那么直接推过去，每次求出用前面某一长度的数字填满 $C$，后面设 $0$ 的答案，取 $\max$ 即可。不过这题比较毒，还需要实现一个分数类。需要注意的是，推平方和的时候可能爆 $\text{long long}$，开 $\text{double}$ 即可。

算上排序，时间复杂度 $\mathcal{O}(n\log n)$。

2020.11.28

$\texttt{Location:NOIP2020}$

得分：$\texttt{280/400,Rank2}$

[11.28]-错误

$\texttt{T2}$ 的调参挂了 $\text{20pts}$，实际上是乱搞的。

$\texttt{T4}$ 想到第一步，却没有继续往下想了......还是需要多研究部分分才能得到提示！

[11.28]-部分正解

$\texttt{T1}$

这题很CF

思考一下质数有什么共同的有效性质：除了 $2$ 之外都是奇数。

那么如果没有 $2$，则只需要奇偶分组染不同颜色即可。加入 $2$ 这个奇数之后，不难想到按照 $\bmod 4$ 进行分组。对于 $n\le 8$ 的情况可以手动构造颜色更少的方案，而对于 $n>8$ 容易证明三个颜色不可行，因此就 $\bmod 4$ 分组即可。

时间复杂度 $\mathcal{O}(n)$。

$\texttt{T2}$

貌似不是正解却拿了接近满分

考场做法：

发现在答案中，每一个 $b_i$ 的地位是平等的。所以一定有贪心：大的 $a_i$ 配小的 $b_i$，小的 $a_i$ 配大的 $b_i$。由于答案中还有一个 $\min\{b_i\}$，因此考虑枚举这个最小值。

枚举最小值，然后考虑让一些 $b_i$ 能够变得更大一些。发现我们一定优先增大 $a_i$ 小的 $b_i$，同时只要增大，就一定增大到可以增大的最大限度。

那么就一直这样按照 $a_i$ 从小到大的顺序推过去，然后就可以得到 $\min$ 一定时的最优答案。

但是我们不能直接枚举 $\min$，所以猜他是单峰的然后三分调参即可通过。

正解做法：

咕咕咕

$\texttt{T3}$

发现这个条件很奇怪，到达某点的步数等于该点的编号。想到天天爱跑步的问题类似，于是考虑写柿子解决。

设一个点的深度为 $\text{dep}_x$，那么对于一条从 $x$ 到 $y$ 的路径，我们把他拆成 $x$ 到 $\text{lca}$，和 $\text{lca}$ 到 $y$。

然后考虑 $x$ 到 $\text{lca}$ 的情况，另一边同理。

对于这条路径上的一个点 $a$，到达他走的路径是 $\text{dep}_x-\text{dep}_a$，那么若该点满足条件，则：

$$\text{dep}_x-\text{dep}_a=a$$

移项可得：

$$\text{dep}_a+a=\text{dep}_x$$

发现一边只与 $a$ 相关了，且这是在一条直上直下的链上，所以使用主席树，将某一个点的 $\text{dep}_x+x$ 放在主席树下标位置，就可以很轻松地做到 $\mathcal{O}(n\log n)$。

但是我们发现，每次我们只需要单点加，单点查询。那就用桶好了。把路径差分为根到 $\text{lca}$ 与根到 $x$，把查询挂在两个位置上，一个加一个减即可。

需要注意一下 $\text{lca}$ 可能不会被算到/会算重，所以需要特判一下。

时间复杂度 $\mathcal{O}(n+m)$。

$\texttt{T4}$

看到 $\left\lceil \dfrac{n}{2}\right\rceil$，那么可以考虑两两将电线分组，若 $n$ 为奇数则最后一个单独分组。每次对于一个组 $(x,y)$，我们希望 $x,y$ 中至少有一个有电。

考虑顺推这样的分组。首先将分组随意设定，然后每遇到一个平衡器就调整分组。同时我们认为到达一个平衡器的时候，当前的所有分组都满足至少有一个有电的条件。

对于一个平衡器 $(x,y)$，考虑他会产生什么影响。首先肯定的，他会让 $x,y$ 中至多一个有电，且若 $x,y$ 中存在至少一个有电，那么电可以转移到 $x,y$ 中任意一个。

那么考虑调整分组，对于平衡器 $(x,y)$。

• 若 $x,y$ 同组，那么没有影响，因为反正他们中间有一个有电，怎么导都不会让其消失。
• 若分组类似 $(x),(y,p_y)$，那么将分组调整为 $(x,y),(p_y)$。$x$ 一定一开始有电，那么我只需要令 $p_y$ 有电就可以满足分组。
• 若分组类似 $(x,p_x),(y,p_y)$，那么将分组调整为 $(x,y),(p_x,p_y)$。我只需要令 $x,p_y$ 或 $y,p_x$ 有电就可以满足分组。

现在推过所有的平衡器之后，会得到 $\left\lceil \dfrac{n}{2}\right\rceil$ 个分组。对每一个分组中，随意选择一个，令其有电，另一个没有（实际上可能有，但是不会用到就没有关系）。对于求平衡器状态，只需要逆推回去，然后判断一下在当前这种分组的变化情况中，该平衡器是应该向上还是向下即可。

不难发现通过这种构造方式，每一种情况都能被解决。所以答案一直是 $\text{YES}$。

时间复杂度 $\mathcal{O}(n+m)$。

2020.11.30

$\texttt{Location:NOIP2020}$

得分：$\texttt{242/400,Rank2}$

[11.30]-错误

$\texttt{T2}$ 的 $\text{AC}$ 自动机在根不为 $0$ 的时候可能访问 $0$，从而导致出锅。挂了 $\text{30pts}$。

$\texttt{T3}$ 本来可以得一些分的，但是上界设置出错导致抱灵......

[11.30]-部分正解

$\texttt{T1}$

本题名字为 $\text{aminusb}$，所以直接输出 $a_1-a_2$ 即可。 不是

发现在任意一种方案中，每一个位置上的值对答案的贡献总是 $-1$ 或 $1$。考虑一下一个点的系数之和，最后乘上其值求和即可。

发现若一个位置 $x$ 的联通块向前合并了 $l$ 次，则其系数是 $(-1)^l$。

那么只考虑 $x$ 之前的合并关系。显然第一个位置系数是 $1$，第二个位置的系数是 $-1$。从第三个位置开始，合并系数就两种都有可能了。但是，对于一个 $x\ge 3$，当我们找出任意一个合并次数为偶数的排列（显然不会是 $0$），交换前两个会对该系数产生贡献的位置，就会使合并次数变为奇数。不难发现这样的排列是一一对应的，所以对于任意的 $x\ge 3$，其系数之和是 $0$！

那么只需要输出 $a_1-a_2$ 即可，若 $n=1$ 则输出 $a_1$。

时间复杂度 $\mathcal{O}(Tn)$。

$\texttt{T2}$

当我们把根到一个点所经过的所有边上的数字拼在一起，会得到一个 $01$ 串，那么若一个点可行，则该长度为 $m$ 的匹配串一定是这个串的后缀。

这可以直接上哈希，可过。

同样，我们可以对原树所有点代表的串，与匹配串加在一起建立 $\text{AC}$ 自动机，不难发现其实原树就是一棵 $\text{trie}$ 了，只需要将匹配串插入即可。

建出 $\text{fail}$ 树，找到匹配串代表的节点。那么该节点的子树内的点，都有匹配串这个后缀。那么把以匹配串代表的节点在 $\text{fail}$ 树上的子树标记，然后在原树上 $\text{DFS}$，每当遇见一个标记点时，找到他的 $m$ 级祖先，则该 $m$ 级祖先的答案为当前节点。求 $m$ 级祖先可以直接维护一个栈，$\mathcal{O}(1)$ 搞。

需要注意的是，该题根节点不一定为 $1$，因此需要注意在建立 $\text{AC}$ 自动机的时候，有可能会访问到 $0$ 号节点，实际上他们都应该访问根节点。

时间复杂度 $\mathcal{O}(n)$。

$\texttt{T3}$

首先第一眼特别像校园旅行

考虑使用类似 $\text{Floyd}$ 的做法，令 $\text{dp[x][y][0/1/2]}$ 为 $x$ 到 $y$，恰好/多一个左括号/多一个右括号的最短路径长度。

这在做 $n^2$ 遍之后就能够保证正确性，但是时间不允许，关于括号深度的证明可以详见原题解。 就是懒

考虑他慢在哪里。实际上我们做了很多无用的转移，考虑使用 $\text{priority\_queue}$ 来进行优化。令 $\text{dp[x][y]}$ 为从 $x$ 到 $y$ 的合法最短路径长度，若 $x\ne y$，那么有两种转移方式：

• 在 $x,y$ 路径外面套一个括号，则可以转移到 $\text{dp[u][v]}$，满足 $u$ 到 $x$ 有一个左括号的边，$y$ 到 $v$ 有一个右括号的边。
• 寻找一个括号序列的断点 $w$，使得 $\text{dp[x][w]}$ 与 $\text{dp[w][y]}$ 均合法。

这样的时间复杂度是 $\mathcal{O}((m^2+n^3)\log n)$。

发现第一种转移中，我们每次都要两重循环，这非常慢。所以可以定义中间数组 $\text{g[x][y]}$ 表示从 $x$ 到 $y$ 的路径上，恰好最左边多了一个左括号的最短路径长度。每次从 $\text{dp}$ 更新 $\text{g}$，再从 $\text{g}$ 找右括号更新 $\text{dp}$。那么就维护两个堆，分别维护 $\text{dp}$ 与 $\text{g}$ 的最小值，每次去更小的更新，时间复杂度就神奇地降到 $\mathcal{O}((nm+n^3)\log n)$，当然这个堆需要支持 $\text{decrease-key}$，如果直接使用 $\text{\_\_gnu\_pbds::priority\_queue}$ 这种 $\mathcal{O}(1)$ $\text{decrease-key}$ 的话复杂度直接是 $\mathcal{O}(nm+n^3)$。

再考虑一下能不能不用 $\text{pbds}$。可以维护一个 $n^{\frac{1}{k}}$ 叉堆，其中 $k$ 是一个常数。那么当我们 $\text{decrease-key}$ 的时候，上浮复杂度是 $\mathcal{O}(k)$，但是 $\text{pop}$ 却需要 $\mathcal{O}(kn^{\frac{1}{k}})$。

然鹅，我们的操作中 $\text{decrease-key}$ 与 $\text{pop}$ 次数并不均衡，时间复杂度可以写成：$\mathcal{O}(k(nm+n^3)+kn^{\frac{2}{k}}n^2)$，当 $k\ge 2$ 时复杂度就是 $\mathcal{O}(nm+n^3)$ 的了。

$\texttt{T4}$

咕咕咕