臭不要脸的回到了机房，感觉大家越来越强了，膜拜。
想到什么写什么。
- 多校清北营训练「清华场」B. 绕口令/gym100162B
题意：定义一个字符串为好的当且仅当其中没有两个相邻字符相同，问你对 \(k\in[1,n]\)，能否删去原字符串中连续 \(k\) 个字符得到一个好的字符串。这里我们认为第一个和最后一个字符也是相邻的。
断环。删去一个长为 \(k\) 的段等于保留一个长为 \(n-k\) 的段。由于保留后不能出现相邻相同，所以可以把这个串中相邻相同的点作为分界点，把这个串分成若干个独立的问题，每个都只需要让开头结尾不同。然后思考一个 \(k\) 怎么才不合法：相当于这个串的任意一个长为 \(n-k\) 的子串都有首尾相同，即有长为 \(n-k-1\) 的循环节，kmp 即可。复杂度 \(\mathcal{O}(n)\)。
- A 【0518 A组】序列统计
\(p\) 是质数。记 \(min(l,r)=\min\{a_l\ldots a_r\}\)，\(max(l,r)\) 同理。
考虑 \(f_{n,k}\) 表示长为 \(n\)，取值范围 \([1,k]\) 的好序列数。考虑总的减不合法的，令 \(i\) 是最大的满足 \(max(1,i)=min(i+1,n)=x\) 的 \(i\)。前面 \(a_1\ldots a_i\) 方案数就是 \(x^i-(x-1)^i\)。由于不存在 \(j>i,max(1,j)=min(j+1,n)\ge x\)，且 \(max(1,i)=min(i+1,n)=x\)，则 \(max(1,j)=max(i+1,j)\)，即 \(a_{i+1}\ldots a_n\) 的取值范围为 \([x,k]\)，方案数就是 \(f_{n-i,k-x+1}-f_{n-i,k-x}\)。直接递推能得到转移式
考虑对 \(\mathcal{O}(n^4)\) 做法进行优化。记 \(g_{n,k,x,p=0/1}=\sum\limits_{i=1}^n(x-p)^{-i}(f_{i,k-x+1}-f_{i,k-x})\)，这个可以 \(\mathcal{O}(nk^2)\) 求。把 \(f\) 写成 \(f_{n,k}=k^n-\sum\limits_{x=1}^k(x^ng_{n-1,k,x,0}-(x-1)^ng_{n-1,k,x,1})\) 就也可以 \(\mathcal{O}(nk^2)\) 了。
由于 \(k\le 10^9\)，考虑容斥算 \(h_i\) 表示只用 \(i\) 种元素的好序列数，答案就是 \(\sum_i\dbinom{k}{i}h_i\)，前面的 \(f_{n,k},g_{n,k,x,0/1}\) 也只需要 \(\mathcal{O}(n^3)\) 了，略卡常。
- [ARC178C] Sum of Abs 2
思路比较简单，大概就是 \(b\) 排序后差分得 \(c_i=b_i-b_{i-1}\)，则 \(\sum\limits_{i=1}^{L-1}\sum\limits_{j=i+1}^L|b_j-b_i|=\sum\limits_{i=1}c_i(i-1)(L-i+1)\)。目标是让上式等于 \(a\)，求最小的 \(\sum c_i\)。注意到前面那个系数是对称的，可以前面取 0 后面再让 \(c_i>0\)，这样就不需要满足个数为 \(L\) 的限制了，直接 dp 是 \(kA\) 的，其中 \(k\) 是满足 \(A\ge(i-1)(L-i+1)\) 的 \(i\) 的个数，因为 \(A<(i-1)(L-i+1)\) 的 \(c_i\) 一定是 0。则 \(A\ge(i-1)(L-i+1)\ge\dfrac{L^2}{4}\)，\(k\le L\le 2\sqrt{A}\)，复杂度 \(\mathcal{O}(A\sqrt{A})\)。
- A 【0521 A组】merge
首先 \(\lfloor\dfrac{x\mid y}{2}\rfloor=\lfloor\dfrac{x}{2}\rfloor\mid\lfloor\dfrac{y}{2}\rfloor\)，所以定义 \(d_i\) 为 \(a_i\) 右移的位数，不考虑删除的时候一定有 \(\sum\limits_{i=1}^n\dfrac{1}{2^{d_i}}=1\)，答案就是 \(or_{i=1}^n\lfloor\dfrac{a_i}{2^{d_i}}\rfloor\)。加上删除操作后即能选出一个子集或起来等于 1，当 \(\sum\limits_{i=1}^n\dfrac{1}{2^{d_i}}\ge 1\) 时这一定是可以办到的，证明显然。不妨定义 \(f_{i,j}\) 表示前 i 个，或起来是 j 的最大的 \(\sum\limits_{i=1}^n\dfrac{1}{2^{d_i}}\)。找 \(f_{n,i}\ge 1\) 的最小的 i，复杂度 \(\mathcal{O}(Tnw2^w)\)。
注意到我们可以假设答案每一位全是 1，然后从高到低尝试将这一位改为 0，则合法当且仅当 \(a_i>>d_i\) 都是当前答案 ans 的子集，然后就 \(\mathcal{O}(Tnw^2)\) 了。
然后是神秘优化。寄一个 \(b_i\)，\(b_i\) 的第 j 位为 1 表示 \(a_i>>j\) 不是 ans 的子集。如果要把 ans 第 t 位从 1 改成 0，把 \(b_i\) 或上 \(a_i>>t\) 即可。\(d_i\) 的取值就是 \(b_i\) 最低的 0 的位置，这个可以 \(\mathcal{O}(1)\) 求，然后就 \(\mathcal{O}(Tnw)\) 了。
- B 【0515 A组】词典
很厉害的题。设 \(f_n=\sum\limits_{i=1}^n\lfloor1+\log_2 i\rfloor\)，\(d_n\) 为答案。有转移式
解释一下。可以把每个数丢到 trie 上，i 是左子树中数的个数。当 i>1 时，由于不能有一个是另一个的前缀，所以左儿子不能选，所以左儿子也要算一个 \(f_i\)。注意到 d,f 都是凸的，证明如下：
考虑用若干条斜率递增的一次函数刻画这个 d。注意到这样需要的一次函数很少，大概是 2000 条左右。题解说 \(f_n\) 是 \(n\log n\) 级别，\(d_n\) 是 \(n\log^2 n\) 级别，所以斜率是 \(\log^2 n\) 级别。对比较小的 n 暴力 dp 求出一些斜线，然后每次二分第一个不在这条直线上的点，这个可以二分。因为 d 是凸的，所以也可以二分斜率/三分。但是问题在于目前 \(d_i,d_{n-i}\) 可能还没求出来，怎么办捏？一种解决方法是我们假装当前已知的最后一条直线延伸到了无穷远，但是这样为什么是对的？
考虑分讨。如果 \(d_n\) 算对了显然不会有问题，所以只用看算错的情况。如果算错了说明前面必然有拐点，如果算出来没拐点就寄了。假设真正的 \(d_n\) 为 \(d'_n\)，由于斜率单增，所以 \(d_n-d'_n=k>0\)。假设是从 \(d_i,d_{n-i}\) 转移过来的，显然这个时候 \(d_{n-i}\) 应该也在新的直线上，因为 \(d_n\) 算错了。注意到此时 n-i 到 n 这一段的斜率就不满足单调递增的规律了，所以这种情况不可能存在。于是正确性得到证明。
分析一下复杂度。直线有 \(\log^2 n\) 条，二分拐点 \(\log n\)，二分决策点 \(\log n\)，找到对应直线 \(\log(\log^2 n)\)，大概是 \(\mathcal{O}(\log^4 n)\) 到 \(\mathcal{O}(\log^5 n)\)？可以提前打好表。
- A 【0515 A组】整除
特判 x=1，其他时候同乘 (x-1) 转化成 \(f(x)\times (x-1)\) 能被 \(x^m-1\) 整除。记 \(f(x)\times (x-1)=\sum\limits_{i=0}^{m-1}a_ix^i\)，注意到 \(x^y\) 等价于 \(x^{y\bmod m}\)，于是可以求 \(a_i\) 了。考虑如何 check 一个 x 是否合法，考虑不断进行以下操作：
-
找一个 \(a_i\ge x\)，将 \(a_i\) 减去 \(x\)，将 \(a_{(i+1)\bmod m}\) 加上 1；
-
找一个 \(a_i\le -x\)，将 \(a_i\) 加上 \(x\)，将 \(a_{(i+1)\bmod m}\) 减去 1；
当 \(\forall i,|a_i|<x\) 时，容易发现满足条件当且仅当所有 \(a_i\) 都等于 0、x-1 或 -x+1。所以当初始时 \(a_i\) 都为 0，则有无数解；否则考虑枚举 x，直接拿个 map、set 什么的模拟上面的过程。因为 \(\sum|a_i|\) 是 \(\mathcal{O}(n)\) 级别的，且我们只需要考虑不超过 \(\max|a_i|+1\) 的 x，且一次操作会让绝对值之和减少至少 x-1，复杂度 \(\mathcal{O}(n\log n\ln n)=\mathcal{O}(n\log^2 n)\)。
- A 【0522 A组】序列
终于场切一道题了，感动。
注意到这个合法子序列的条件相当于你标记若干个格子，初始时你的分数是 A，从左往右走到一个没有被标记的格子时失去 X 的分数，否则得到 \(a_i\) 的分数，要让任何时刻分数都不小于 0。考虑每一段 \((b_{i-1},b_i]\) 可以独立考虑，定义 \(f_{i,j}\) 表示前 i 段，贡献和为 j 的目前最大的分数。如果想让这个段没有贡献那我们直接标记每个格子，否则我们从左往右扫，每次遇到不合法时贪心的从之前的还没被标记的格子中取出 \(a_i\) 最大的标记上。因为在当前位置之前的格子对后面的分数的贡献都是一样的了，所以这样直接贪很对啊。复杂度 \(\mathcal{O}(mn\log n)\)。
- [AGC001E] BBQ Hard
原题是简单的，显然的组合意义，然后就会了。考虑加强版本，\(\sum(a_i+b_i)\le 2\times 10^7=M\)。
一种想法是根号分治。称 \(a_i+b_i\le B\) 的点为小点，否则为大点。小点到小点可以沿用原来的做法，\(\mathcal{O}(B^2+n)\)；大点到大点可以枚举一对点 \((i,j)\)，暴力 \(\mathcal{O}(\left(\dfrac{M}{B}\right)^2)\) 算组合数；小点到大点可以先枚举大点，注意到这样从小点开始一定会经过直线 \(y=-x\) 恰好一次，不妨枚举交点 \((x,-x)\)，显然 \(x\in[-B,B]\)，然后小点到他的方案在小对小得时候处理过了，他到大点的方案可以直接组合数，复杂度 \(\mathcal{O}(\dfrac{M}{B}\times B)=\mathcal{O}(M)\)；大点到小点类似处理。取 \(B=\sqrt{M}\) 即可 \(\mathcal{O}(M)\)。
另一种想法是范德蒙德卷积。
此时前面的 \(x\) 要满足 \(x\in[-a_i,b_i]\)，后面的要 \(x\in[-b_j,a_j]\)，拆成两部分，开个数组存对应 \(x\) 的和，扫一遍即可。复杂度 \(\mathcal{O}(M)\)。
- C 【0402 A组】乱斗之星（0524）/gym102394H
典。注意到 T 要么是 1 要么是 Tmax，考虑先选出一棵生成树，跑点分优化建图，剩下的 m-n+1 条边直接暴力贡献即可。这样就可以了 \(\ldots\) 吗？
当然不可以，这样做时间 2log，空间大常数 1log，完全过不去。注意到每个实点的出边边权都是一样的，考虑舍弃建图和 dij。以 T=1 为例，定义 \(f_i\) 表示 k=i 的答案，初始只确定了 \(f_1=0\)，其它都不确定。建立点分树，优先队列维护 \(d_i\) 确定且 \(d_i+c_i\) 最大的 i，每次取出来，遍历它在点分树上的祖先。假设当前这一层分治结构代表的分支中心是 p，其中有点 j 的 \(d_j\) 未确定，如果 \(dist(i,p)+dist(p,j)\le a_i\) 则可以直接 \(d_j\gets d_i+c_i\) 然后在这一层删去 j。如果事先对每一个分治结构内每个点按到分治中心的距离从小到大排序，则上述过程可以简单用一个指针查询与维护，均摊复杂度 \(\mathcal{O}(n\log n)\)。对于多出的 m-n+1 条边 (u,v)，我们依次钦定 u 和 v 为一个类分治结构的“分治中心”，内部的点就是 n 个点，类似上面那么做即可。求距离需要 \(\mathcal{O}(n\log n)/\mathcal{O}(n)-\mathcal{O}(1)\) lca 和 bfs。总复杂度 \(\mathcal{O}(n\log n+(m-n)n)\)。
- B 【0525 A组】简单题
题解声称可以证明最优解是 \(a_i=(2i-1)2^{\lfloor\log_3(2n/(2i-1))\rfloor}\)：
但是这样太不牛了，考虑一个正常人在考场上能想到的做法。考虑 \(a_i=i+n\)，这样一定合法了。然后从 n 到 1 枚举 x，看目前 a 中 x 的倍数是否只有一个，如果是的话就可以把它替换成 x，这样显然更优，而且效果是一样的。复杂度 \(\mathcal{O}(n\ln n)\)。
- A 【0525 A组】签到题
可以证明，当每种颜色都出现过，且任意相邻珠子的颜色都不同是有解的充要条件。必要性显然，下面的构造方法可以体现充分性。
n=3 时有解。当 n>3 时，我们考虑找到相邻的三个点 (x,y,z)，使得 \(a_x,a_y,a_z\) 两两不同，且 \(a_y\) 在所有珠子中出现次数 \(c_{a_y}>1\)，连接 (x,z) 就可以递归到一个 n-1 的子问题。
然后是满足条件的 n 个点中一定能找到这样的 (x,y,z)。因为三种颜色都出现过，所以一定能找到 \(a_x,a_y,a_z\) 两两不同的位置。如果 \(c_{a_y}>1\) 就找到了，否则考虑 z 的下一个珠子 w，\(a_z\neq a_w\)，因为 \(c_{a_y}=1\)，所以 \(a_w\neq a_y\)，所以 \(a_y,a_z,a_w\) 也两两不同，这样递归找一下一定能找到 \(c_{a_y}>1\) 的 y。实现很简单，直接做，随便做。
- B 【0402 A组】勾股计数（0524）
移项即 \(a^2=(c-b)(c+b)\)，考虑 \(d\mid a^2\)，当 \(d\equiv\frac{a^2}{d}\pmod 2\) 且 \(a\neq d\) 时，c,b 有正整数解。所以当 \(a\bmod 2=1\) 时，答案为 \(\frac{d(a^2)-1}{2}\)，否则一定有 \(d\equiv\frac{a^2}{d}\equiv 0\pmod 2\)，答案就是 \(\frac{d(\frac{a^2}{4})-1}{2}\)。于是核心在于求 \(\sum\limits_{i=1}^{\lfloor n/2\rfloor}d(i^2)\) 和 \(\sum\limits_{i=1,2\nmid i}^nd(i^2)\)。
先看 \(\sum\limits_{i=1}^nd(i^2)\) 形式的式子怎么求：
其中第三到第四步是因为需要 \(n/t^2\ge 1\)。记 \(h(n)=\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor=\sum\limits_{i=1}^nd(i)\)，则上式等于 \(\sum\limits_{i=1}^{\sqrt{n}}\mu(t)\sum\limits_{x=1}^{\lfloor\frac{n}{t^2}\rfloor}h(\lfloor\frac{n}{xt^2}\rfloor)\)。暴力枚举 t，整除分块算 x 和 h，预处理 \(\le n^{2/3}\) 的 h，可以证明复杂度是 \(\mathcal{O}(n^{2/3})\) 的。
考虑算 \(\sum\limits_{i=1,2\nmid i}^nd(i^2)\)，过程是类似的：
记 \(H(n)=\sum\limits_{i=1,2\nmid i}^n\lceil\frac{\lfloor\frac{n}{i}\rfloor}{2}\rceil=\sum\limits_{i=1,2\nmid i}^nd(i)\)，上式等于 \(\sum\limits_{i=1}^{\sqrt{n}}\mu(t)\sum\limits_{x=1,2\nmid x}^{\lfloor\frac{n}{t^2}\rfloor}H(\lfloor\frac{n}{xt^2}\rfloor)\)，也可以做到 \(\mathcal{O}(n^{2/3})\)。
- A 【0529 A组】苦痛之路
赛时想到做法，感觉时间复杂度不对没敢写，后面来不及了/fn
有 \(n=\prod\limits_{i=1}^k p_i^{e_i}\)，原问题即给若干个数安排指数 \(e'_i\)，使 \(\min e'_i=0,\max e'_i=e_i\)。考虑 \(e'_i\) 只有 0、\(e_i\) 和其他三种取值，容斥可以做到大概是 \(4^kk\) 左右的复杂度。进一步发现 \(e'_i\) 中有 0 没有 \(e_i\) 和有 \(e_i\) 没有 0 是本质相同的，精细一点就是 \(\mathcal{O}(3^k)\) 了。多测就把 \(\{e_i\}\) 记忆化一下即可，实测发现本质不同 \(\{e_i\}\) 只有大约 30000 种。
（一个优化是把相同的 \(e_i\) 合并到一起算，容斥的时候枚举每一种情况的个数。题解宣称这样做可以大幅减小常数，但实测比较粗放的实现是完全打不过精细实现的不优化的方法的，因为这个要算组合数什么的。感觉更细节的处理也无法优太多。）
- B 【0529 A组】丝之歌
超级无敌原神大王无敌题解。
\(\mathcal{O}(m2^n)\) 的暴力 dp 你是会的，考虑优化。就类似 meet-in-the-middle 的做法，把原点集分成两个，分别 dp，然后暴力枚举横跨两个点集的边选取情况，复杂度 \(\mathcal{O}(m2^m+2^c)\)，其中 m 是两个点集中较大的的大小，c 是横叉边条数。那么，怎么确定一个较优的划分方案呢？答案是，直接随机化即可。
题解给了一个很有理有据的证明，似乎证明了在题目数据下 c 的期望不超过 26。实际实现中可以先随便划分一下，然后类似爬山那样调整几次，似乎就可以通过了？常数还是比较稳的。
)
