R1 T2
求\(\sum_{i=1}^n f(i)\)，其中\(f(n)\)表示\(n\)的最大平方因子。\(n\leq 10^{14}\)，\(100\)次询问。
单次询问显然可以Powerful Number，复杂度是\(O(T\sqrt{n})\)，卡的就是你（
打表发现构造出来的\(h\)只在完全平方数处有值，于是可以用经典trick优化到\(O(\sqrt{n}+T\sqrt[3]{n})\)，具体是什么trick一会再说。
有一个简单直接、不用打表找规律的做法是，考虑枚举这个平方因子\(k^2\)，然后计算哪些数包含它作为最大平方因子。
这些数除掉\(k^2\)之后应该没有平方因子了，而一个数\(n\)没有平方因子就是\(\mu^2(n)=1\)。所以我们的答案就是
\[\sum_{k}^{\lfloor\sqrt{n}\rfloor}k^2S_{\mu^2}(\lfloor\frac{n}{k^2}\rfloor)\]后面这个看起来很难受，但是没见有人可以反演掉\(\mu\)啊?
反正是经典结论，我们直接给出神仙推导吧 :
考虑一件非常显然的事情，无平方因子，等价于最大平方因子等于\(1\)，然后你就看到了一个\(\epsilon\)函数的形式!
我们令\(g(n)\)表示\(n\)的最大平方因子的平方根，也就是\(g(n)\)是最大的\(k\)满足\(k^2\vert n\)。构造这样一个函数之后，我们知道对于任意一个\(d\)，有\(d\vert g(n)\Leftrightarrow d^2\vert n\)。同时\(g(n)=1\)也等价于\(n\)的最大平方因子是\(1\)。
\[\mu^2(n)=[g(n)=1]=\sum_{d\vert g(n)}\mu(d)=\sum_{d^2\vert n}\mu(d)\]然后我们拆这个前缀和
\[\begin{aligned}&\sum_{i=1}^n\sum_{d^2\vert i}\mu(d)\\=&\sum_{d}\mu(d)\sum_{d^2\vert i}^n1\\=&\sum_{d}\mu(d)\lfloor\frac{n}{d^2}\rfloor\end{aligned}\]这样就可以\(O(\sqrt{n})\)地求\(\mu^2\)前缀和了。
如果直接这么搞的话，复杂度是\(O(\int_{1}^{\sqrt{n}}\sqrt{\frac{n}{x^2}}\ \mathrm{d}x)=O(\sqrt{n}\log n)\)。
不过，为什么要直接搞?显然有个整除分块的形式，看起来可以更快的。
容易发现\(\lfloor\frac{n}{d^2}\rfloor\)的取值只有\(O(\sqrt[3]{n})\)种，这是好的，所以我们可以整除分块一下，并通过线性筛预处理\(\mu\)前缀和，把这个优化到\(O(\sqrt[3]{n})\)单次。新的复杂度是\(O(\int_{1}^{\sqrt{n}}\sqrt[3]{\frac{n}{x^2}}\ \mathrm{d}x)=O(\sqrt{n})\)，好吧还是不行。
然后发现外面还有个整除分块，再试一试?然而复杂度还是没有变化。看来这个做法也只有部分分了。
那么我们回去看那个Powerful Number吧!
对于这个题，我们构造\(g=\mathbb{1}\)，打表发现\(h\)只在完全平方数处有值，所以我们可以考虑一下Powerful Number的式子能不能更快地计算 :
\[\sum_{i}h(i^2)S_{g}(\lfloor\frac{n}{i^2}\rfloor)\]呃是可以的。具体如何实现?
我们考虑利用之前那个数量的估计，直接分开枚举这两类数即可。另外据说可以直接魔改整除分块，不是很了解原理，这里就不说了。
事实上，刚才那个根号的做法，也可以通过奇妙方法来转化成同样的做法，本质是大致相同的。
R1 T3
独立集的\(T(n)=T(n-1)+T(n-4)+O(n)\)算法，算出来大概是\(O(1.1^n)\)之类的东西?
每次找一个度数至少是\(3\)的点，决策选/不选然后dfs下去，如果没有这样的点说明是环或者链，直接dp一个答案返回。这样不选就是删一个点，选就是删四个点，复杂度就是上面的东西，并且常数很小，好像吊打std了。
R2 T1
定义\(f(n)\)为\(n\)质因子分解中最高次数和最低次数的积，求\(\sum_{i=1}^nf(i)\)，\(n\leq 10^{12}\)。
\(10^{12}\)让人想到Powerful Number，发现非Powerful Number的最低次数全是\(1\)，而Powerful Number又已经搜出了质因子分解，那么问题就变成了求\(\sum_{i=1}^n g(i)\)，其中\(g(n)\)表示\(n\)质因子分解中最高次数。
我们类似R1 T2做法，枚举一个\(e\)，计算有多少\(g(n)=e\)的\(n\)。那么我们再枚举一个\(k\)，计算有多少个数最大\(e\)次因子是\(k\)即可，这等价于除掉\(k^e\)后不存在\(e\)次因子。这东西就没法用\(\mu^e\)之类的来表示了，我们直接按照上面的做法用\(\mu\)来容斥，得到
\[n\text{没有}e\text{次因子}\Leftrightarrow\sum_{d^e\vert n}\mu(d)=1\]太麻烦就不换求和号了。容易得到一个\(O(\sqrt[e]{n})\)单次求这个的算法，那么我们的复杂度就是\(O(\sqrt[2]{n}+\sqrt[3]{n}+\sqrt[4]{n}+\dots)=O(\sqrt{n})\)，打完这个打一个Powerful Number就好了，总复杂度还是\(O(\sqrt{n})\)。
R2 T2
太经典了。有一棵树，树上每个点有一个0/1点权，现在要你把点们排成一排，要求儿子必须在父亲右边，求最小逆序对数。\(n\leq 10^5\)。
考虑那个位置的限制到底是在干什么，实际上它说的是一棵子树里所有点都必须在根的后面，而根的各子树之间可以穿插。如果你从头开始扫这个序列，你应该会看到一个指针在树上乱跳，但是每次跳到一个结点，它的父亲都已经跳过了。
考虑一个合并算法，我们每次取出一个点，把它接到父亲后面并把它删去，此时它子树里的点可以直接扔进序列后面的条件就变成了它的父亲被扔进去，所以我们把它的儿子们向父亲连边。
这题的结论是，如果一个点 0的个数比1的个数 最大，那么它一定会直接接在它父亲后面。开个堆维护即可。
为什么这是对的?可以用邻项交换的思想证明。
R2 T3
ARC087F?
草，绝了。有一棵树，你要找到一个置换，使得每个点到它置换到的那个点在树上的距离之和最大，并计算方案数。\(n\leq 1000\)，可以出到\(5\times 10^4\)。(\(5\times 10^4\)就是rqy式数数题了)
结论是，类似于点分治，我们每次找到重心，然后把子树胡乱置换一下，保证每个点换到不同的子树去，得到的就是最大的。要计算方案数可以使用背包，同时可以分治法法塔优化成2log。
为什么这个结论是对的?考虑重心是唯一(二)满足没有超过一半的子树的点，如果有这样的子树那么这棵子树里就有点必须待在原来的子树里面，所以一定不比重心优。这个背包感觉好复杂，完全不会/cy
R3 T2
收录于 ICPC2020济南站 L 题解。
R3 T3
给横轴上\(n\)条横着的线段，纵轴上\(n\)条竖着的线段，随机一个排列把这些线段对应起来，然后每一对确定一个矩形，求这个矩形并的期望面积。\(n\leq 10^5\)。
先进行一个类似于离散化的操作，对于横着的线段从每个端点引一条竖线，竖着的反过来，就得到一堆小方形。我们考虑每个出现在并中的概率然后乘上面积加起来就是答案。
容斥。一个方形出现的概率，只跟覆盖它的横着的线段和竖着的线段的数量有关，化一下式子发现变成了卷积，然后法法塔即可。
R4 T1
字符集01，给一个串，求最短的没作为子串出现过的串，多个则最小化字典序。\(\vert S\vert\leq 2^{24}\)。
最神的一步转化是，给一个长度\(l\)，那么字典序最小的没出现过的长为\(l\)的串就是把所有长为\(l\)的子串拿出来取\(\mathrm{mex}\)。然后我们从\(\lg n\)向下枚举\(l\)，每次值域都会减半，我们同时进行去重，复杂度就是带二倍常数的\(O(n)\)，比SAM不知高到哪里去了。
R4 T2
lxl的神仙数据结构题。不打算做。
upd : 看完了，收录于 二轮省集。
R4 T3
将会整理进 状压dp。
R5 T1
随机一个长\(n\)的排列，求这个排列中\(n\)前面，没有任何一个数比它后面所有\(k\)个数都大的概率，膜质数。\(n,k\leq 10^6\)，有\(10\)组数据。
先转为方案数。考虑一个dp，设\(dp(i)\)表示长为\(i\)的合法排列数量，那么我们枚举\(i\)的位置，这就要求它前面是合法的，而后面随意。我们用二项式系数选出放在前面的，于是转移就是……我不知道!
发现问题出在，我们需要保证\(i-1\)不合法，也就是说它后面\(k\)个必须包含我们枚举的\(i\)，那么我们可以修改状态定义为，\(dp(i)\)表示长为\(i\)的合法排列，且\(i\)在最后\(k\)个里面的数量，这样就可以转移了。答案可以用类似的方法求得。
R5 T3
给一棵树，支持换根，求所有点高度的异或和，其中高度的定义是到子树里某个叶子的最长距离。\(n,q\leq 10^5\)。
本来这题还有个博弈论的皮，不过没啥意思就没放。
考虑每个点只可能有两种贡献，也就是以它为根的时候，前两深的它的子树的深度。
还是比较厉害。考虑一个点出发的最长路径，有一个重要结论是端点中至少一个是直径端点，同时路径一定经过树的center也就是直径中点。我们以直径中点为根提起来，那么每个点都不能贡献最深的子树了，此时一次换根就是翻转两条到根的链的贡献，容易用树剖维护。
R3.5 T2
树，点权从0变1，动态重心。
可以使用静态LCT上二分随便做/cy
可我不会写/cy
R3.5 T3
有标号基环树计数。
考虑做有向基环树，无向基环树就是有向的除以\(2\)也就是环的定向方案数。
考虑有向基环树的\(\exp\)就是每个点随便连出一条边的图，方案数是\(n^n\)，然后对这个取\(\ln\)再减去自环、二元环再除以\(2\)就得到了答案。
R6 T2
两棵树，一棵黑色，一棵白色，边有边权。两棵树并起来构成一张图，求对于\(k=0,\dots,n-1\)，恰有\(k\)条黑边的MST上的边权和。\(n\leq 5\times 10^3\)。
容易想到wqs二分，但是跑不过。
考虑不进行二分而是从\(\infty\)到\(-\infty\)枚举附加权值，每次要想让黑边数量+1，需要找到一条黑边使得它端点在当前MST上构成的路径上最大白边边权最大，然后通过下调附加权值，让这条黑边比那条白边更小就好了。每次这样做之后我们重新dfs计算，可以使用Tarjan LCA做到接近线性，当然更好的方法是直接拿着更新的边去更新所有经过它的路径。写起来不很简单，但也不很麻烦?没写（
R6 T3
\(n\times n\)的矩阵，一开始全是\(0\)，给\(n\)个矩形，每个里面均匀随机一个位置然后给它\(+1\)，问最后行列式的期望。\(n\leq 10^5\)。有一档部分分是每一行有一个横条状的矩形。
最基本的结论是，这个等价于先给每个矩形\(+1\)，然后跑一遍行列式，最后除以选择的方案数也就是每个矩形大小的乘积。根据行列式和期望的线性性是显然的，但是我当场弃题，这告诉我们要善于猜结论。
然后就很简单了，对于那个部分分，我们可以直接进行差分，每一列减去上一列行列式不变。这样就变成了每一行有两个数，一个\(1\)一个\(-1\)，当然这个条延伸到最后一列的时候就没有\(-1\)了。
考虑如何求这个行列式，我们干一件匪夷所思的事情 : 建一张图，有\(n+1\)个点，每一行的\(1\)的列向\(-1\)的列连边，没有\(-1\)视为\(-1\)在位置\(n+1\)。
这张图的意义是什么?每条边代表消元的时候用一个\(1\)消去另一个\(-1\)或者反过来，这依赖于边的方向，而我们没给边定向。这个消元会产生新的\(-1\)和一个\(1\)，也就是这样的消元具有封闭性。
如果有一个环，我们沿着环消一圈，会刚好全消成\(0\)，此时行列式必定为\(0\)；否则它就是一棵树，因为是\(n+1\)个点\(n\)条边。看到边的意义，容易想到我们需要给边定向。如果用\(n+1\)去消的话，相当于用一个只有一个\(1\)的行去消，那么消掉所有儿子之后就变成了子问题，所以我们得到了做法 : 对于每条边，用父亲消儿子。消完之后得到了一个每行每列只有一个\(1\)或者\(-1\)的矩阵，求个逆序对然后看一看\(-1\)个数的奇偶性就可以求出行列式。
对于原问题，考虑你随机完\(n\)个位置之后，把行列拆开分成两个矩阵，矩阵\(X\)的第\(i\)行第\(j\)列有值当且仅当你随机的第\(i\)个位置列标号是\(j\)，另一个矩阵\(Y\)是类似的当然行列要反过来。然后你会发现这两个矩阵的积就是你随机出来的矩阵，因此它们的行列式之积就是你随机出来矩阵的行列式。然后你发现\(X\)实际上是每一列有一个竖条，\(Y\)是每一行有一个横条，于是就转化成了之前的情况。(大概是?没写过)
R7 T1
有一个只有0或2的字符串，选出尽可能多的不交的2020子序列。\(n\leq 5\times 10^7\)，当然是随机数据。
直接贪可以获得80pts!好家伙。
贪心的问题在于，你不知道当前这个0应该贡献给2020中的第一个0还是第二个0。
分析性质，我们发现如果每个字符只出现一次就很好做，只需要贪心就好了。这里每个字符出现了两次，我们考虑把它劈成两半，从前往后匹配20，从后往前倒着匹配20，相遇的时候取一个\(\min\)就是答案。
R7 T2
树，有一些点上有一个棋子，现在要移动这些棋子，要求移动完之后它们不重合并且连通，求最小步数。每次可以移动到一个相邻的点，并且移动的过程中棋子可以重合。\(n\leq 5\times 10^3\)。
考虑如果我们随便找一个点作为根，然后让所有棋子都移到它旁边来，这个可以用一个树形dp解决。
我们设\(dp(u)\)表示\(u\)子树内所有点都移到\(u\)旁边来的最小步数。你发现这样转移是错误的，因为可能出现一棵棋子多的子树把棋子移到棋子少的子树里面的情况，所以我们修改状态设计，设\(dp(u,i)\)表示\(u\)子树内有\(i\)个点移出去了，所有点都移到\(u\)的最小代价。当然移出去了计算的是移动到父亲的代价。这个\(i\)可能是负的，表示移进来的棋子数量。然后使用经典的树上背包合并的方法，单次复杂度\(O(n^2)\)。可以百度一下，这里给出我百度到的第一篇。
考虑到实际上这个东西复杂度是\(n\)乘上棋子数量，而我们随机一个位置期望\(n\)除以棋子数量次就可以随机到最优解中有棋子的位置，所以我们得到了一个\(O(n^2)\)的随机化做法。
实际上可以不随机化，结论是带权重心上最后一定有棋子。如果没有的话，那么必然。
R7 T3
一个\(n\times n\)的棋盘，左上和右下都有一个三角形被挖掉了，两个三角形边长分别是\(t,s\)。现在要往棋盘里放\(n\)个车，每个车可以横着攻击一行、竖着攻击一列，求放的车互不攻击的方案数。\(n\leq 10^5\)。保证挖掉的两个三角形边长加起来不超过\(n\)，换句话说不会存在一行或者一列同时被挖了两头。
本来是排列计数，但是排列计数的直观表示就是Rooks Problem，所以就直接放车了（
考虑如果只有左上角被挖掉也就是\(s=0\)，那么我们考虑放的过程，第一次可以放\(n-t\)个，第二次因为已经放过一行要减一行，但是因为是三角形还要加一行，所以还可以放\(n-t\)个。可以这么放\(t\)次，而第\(t+1\)次开始就每次减一行了，所以答案是\((n-t)^t(n-t)!\)。
如果还有右下角被挖掉了，我们需要减去放进了右下角的方案数。
直接算不是很好算，考虑容斥。钦定\(k\)个车放进去的方案数，相当于先往右下角三角形里面放\(k\)个，然后剩下的随便放，这是一个\(s=0\)的问题。如果我们设\(f(n,k)\)表示往大小为\(n\)的三角形里面放\(k\)个的方案数，那么要算的就是
\[\sum_{i=0}^n(-1)^if(s,i)(n-i-t)^t(n-i-t)!\]那么问题变成怎么求\(f\)了。想了几个做法之后，你发现可以这么搞 : 我们考虑最后一列，如果不放车，剩下的方案数就是\(f(n-1,k)\)；否则，因为接下来还要放\(k-1\)个车，不管接下来怎么放，最后一列总是有\(n-k+1\)个位置是空的，所以方案数是\((n-k+1)f(n-1,k-1)\)。递推式是
\[f(0,0)=1,f(n,k)=f(n-1,k)+(n-k+1)f(n-1,k-1)\]这样递推就可以得到一个\(n^2\)做法。
仔细观察，这个\(f\)的递推式，怎么这么像斯特林数?
我们考虑两类斯特林数是
\[{n\brack k}=(n-1){n-1\brack k}+{n-1\brack k-1},{n\brace k}=k{n-1\brace k}+{n-1\brace k-1}\]根据那个系数很容易确定一个变量的替换。打出表来看一看，你发现有\(f(n,k)={n+1\brace n-k+1}\)，这可真是太棒了，于是我们套用求一行第二类斯特林数的方法就可以\(O(n\log n)\)解决这个问题。
R8 T1
给两个串\(s,t\)，每次可以加一个字符或者删一个字符，求\(s\)到\(t\)的编辑距离。如果答案超过\(k\)，输出-1。\(\vert s\vert,\vert t\vert\leq 10^5\)，\(k\leq 100\)。
场上想了个维度交换优化，应该是对的，但是细节很多……
我们设\(dp(i,j)\)表示通过修改\(s\)的前\(i\)个，可以匹配\(t\)的前\(j\)个的最小修改次数。容易发现\(\vert i-j\vert>k\)的时候一定是-1，并且这个dp的值是单调递增的，所以对于这样的状态可以省略，复杂度就是\(O(k\vert s\vert)\)，当然认为两个串长度同阶。
R8 T2
在\([0,N-1]\)中选\(n\)个互不相同的整数，数之间没有顺序，求异或起来是\(0\)的方案数。由于\(N\)巨大，用一个串\(S\)给出它的二进制表示，然后\(N\)由这个串重复\(k\)次得到。\(n\leq 7,\vert S\vert\leq 10^4,k\leq 10^5\)。实际上\(k\)可以达到\(10^{18}\)。
有一个部分分是\(k=1\)。考虑容易求出数可以相同并且有顺序的方案数，这可以用一个数位dp解决。具体地，我们设\(dp(p,lim)\)表示从高往低考虑到第\(p\)位，有\(lim\)个数达到了上限，转移的时候，枚举多少个数选1，这些数里面有多少是达到上限的。复杂度是\(O(n^2\vert S\vert)\)。
怎么搞出不能相同并且没有顺序的方案数呢?容易想到预处理容斥系数，我们爆搜一下每一个等价类的大小，如果一个等价类大小是奇数那就相当于出现一次，偶数就是没有出现过，就可以统计上面数位dp中每种情况被算的次数，然后得到一个容斥系数，用这个来统计答案就好了。复杂度玄学，反正能跑（
\(k\)很大的时候，我们把转移预处理成矩阵的形式，然后先对\(S\)乘一遍，接下来对矩阵自乘\(k\)次得到答案，可以用矩阵快速幂加速。复杂度是\(O(n^3(\vert S\vert+\log k))\)。
R8 T3
有一棵边权非负的树和一个序列，大小都是\(n\)，一开始序列中每个点都是树上一个点，支持区间跳到父亲，查询区间点到根距离的最小值。\(n,q\leq 10^5\)。
lxl题，所以考虑分块。
考虑整块。这里的最小值有一个性质，就是如果点\(u,v\)在同一块，只考虑整块操作，\(v\)是\(u\)的祖先，那么\(u\)再也不会比\(v\)更优了。所以我们可以干这么一件事，整块操作的时候爆力跳父亲，并且给跳过的点打上标记，如果一个点跳到了有标记的点，那么它就没有用了可以扔掉。这样树上每个点在每个块只会跳到一次，一共有\(\Theta(\sqrt{n})\)块，所以复杂度是\(O(n\sqrt{n})\)。
考虑零散部分。我们当然要爆力重构啦!但是直接重构会增加\(n\)的势能，我们考虑保留这一块在树上打的标记，并且让每个点先跳完它之前整块操作的时候没跳的部分，这个可以维护一下每个点跳了多少步和这一块跳了多少步来实现。使用长链剖分la，复杂度是\(O(n\sqrt{n})\)。
R6.5 T1
qlr ak!
裸的树套树，明天写一写（
R6.5 T2
给一个字符串，从左往右选出尽量多的长为\(k\)的子串使得它们不相交，并且字典序单调递增。
考虑字典序，当然是用SA来判断。排序之后问题变得非常简单，直接搞一个贪心选过去就好了。
R6.5 T2.5
出现在题解里面的神秘题目，性质类似于NOIO tg T1。
R6.5 T3
\(n\times m\)的方阵，每个格子可以为黑白，\((i,j)\)的权值为\(ai+bj\)，给定初始每个格子的颜色，可以翻转某些行或列，求黑格子的权值和的最大值。\(n\leq 10^6,m\leq 10,\vert a\vert,\vert b\vert\leq 10^6\)。一档部分分是一开始全黑。
好题。
考虑全黑怎么做。我们爆搜列是否翻转，然后因为全是黑的，每行此时的情况是一样的，所以一行的权值是行号的一次函数，反过来也是，那么两个一次函数的交点可以二分求得，复杂度\(O(2^m\log n+nm)\)。
考虑不是全黑怎么做。还记得WC T2吗?每行的情况只有\(2^m\)种可能，每一种内部都是一次函数，我们对于每一种分别二分一次，复杂度\(O(4^m\log n+nm)\)，可以通过。
R9 T1
Alice和Bob玩游戏，三维空间中有\(n\)个棋子，两个人轮流操作，每一次操作先选择一个棋子，然后Alice一步可以随意减少\(x,y\)两维，Bob一步可以随意减少\(y,z\)两维，两个人都可以一步同时把三维减少\(1\)。不能移动到负数坐标，也不能不移动，动不了就输了，问胜负情况。\(n\leq 10^5,x,y,z\leq 10^{18}\)。
我当场打表找规律!尝试了各种东西，然后甚至开始枚举规律，还是没有成功（
实际上很简单，我们可以用超现实数的理论随便杀。考虑一个局面是三个奇怪的东西的和，其中\(x\)维是\(x\)，\(z\)维是\(-z\)，而\(y\)维是\(\ast_y\)，那个Nimber。我们在加这些东西的时候，就是把\(x\)维和\(z\)维加起来，\(y\)维异或起来，然后就变成了一个棋子，记为\((x,y,z)\)。后面事实可以证明这样是对的。
考虑一个棋子怎么做，我们考虑如果\(x+z\neq 0\)，由于Nimber是非常接近\(0\)的，它们无法改变胜负，所以\(x+z\)的正负性已经决定了胜负。如果\(x+z=0\)，那么就要看\(y\)，如果它不是\(\ast_0\)那就先手必胜，否则后手必胜。
你发现我们没有考虑那个同时减少\(1\)的操作，但是还是过了题，原因是它确实没用（
R9 T2
给定\(a,b\)，定义一个01串的权重是\(at_0+bt_1\)，那两个分别是它里面的数0,1量。定义一个01串的划分为把它拆成若干段，满足任意一段都不是另一段的前缀，在所有这些方案中分出来段数最大的方案。求划分的段数为\(n\)的01串中，权重最小的串的权重。\(n\leq 10^{18},1\leq a,b\leq 10\)。
容易想到从互不为前缀的串出发进行构造，此时保证划分段数为\(n\)就比较困难，因为很容易就会搞出划分段数\(>n\)的东西。题解给了一个绝妙想法，如果一个串划分段数\(>n\)，那么一定有一个子串划分段数\(=n\)，而这个子串的权重一定更小，所以我们就把问题转化成了求划分段数\(\geq n\)的串权重的最小值。
考虑一个dp，设\(dp(i)\)表示\(i\)个串互不为前缀的最小权重，那么枚举多少个串第一个字符是0，就把这些串分成了互不为前缀的两部分，两部分之间就没有影响了!可以写出转移方程 :
\[dp(i)=\min_{j=1}^{i-1}(dp(j)+aj+dp(i-j)+b(i-j))\]发现这是一个\(\min,+\)卷积，同时可以猜测并验证\(dp(n)\)是个下凸函数，所以我们可以用闵可夫斯基和合并凸包的科技把这个\(O(n^2)\)的dp优化到\(O(n)\)。
具体怎么做?这是两个下凸函数\(dp(n)+an,dp(n)+bn\)的闵可夫斯基和，而下凸函数的闵可夫斯基和的结论是最优决策点的两边大小单调不降，换句话说从\(dp(i-1)\)到\(dp(i)\)，最优决策点要么不变要么\(+1\)，我们只需要从\((0,0)\)开始每次决策选哪一边，然后更新代价就好了。复杂度优化为\(O(n)\)。
出题人Kewth说的是差分之后归并起来做前缀和，本质是相同的，但是这个好像更闵可夫斯基和合并凸包一些。每次我们求出来一个\(dp\)，就求出差分，分别\(+a,+b\)扔到\(dp(n)+an,dp(n)+bn\)的差分序列最后，然后归并一次计算出下一项。
但是这还是太拖拉机了。完全跑不了\(10^{18}\)。
剩下的优化简直是神了。用Kewth说的差分的思想，我们考虑利用差分的性质。
为了写起来方便，我们先搞三个函数\(f(n)=dp(n),g(n)=dp(n)+an,h(n)=dp(n)+bn\)，那么容易知道\(\Delta g(n)=\Delta f(n)+a,\Delta h(n)=\Delta f(n)+b\)。又因为\(\Delta f\)是由\(\Delta g,\Delta h\)归并起来的，所以对于任意一个\(\Delta f(k)=d\)，一定存在一个\(k^\prime\)使得\(\Delta g(k^\prime)=d\)或者\(\Delta h(k^\prime)=d\)，代入上面的式子就得到\(\Delta f(k^\prime)=d-a\)或\(d-b\)。
我们考虑设\(c(d)\)表示\(\Delta f\)中\(=d\)的数量，那么答案就是\(\sum c(d)d\)。当然这里需要额外考虑最后一段。
考虑上面的式子，可以画一个函数图象加深理解，总之我们可以写出一个方程\(c(d)=c(d-a)+c(d-b)\)。为什么?考虑\(\Delta f(n)=d-a\)的是一个长为\(c(d-a)\)的连续段，\(\Delta f(n)=d-b\)的是一个长为\(c(d-b)\)的连续段，假设它们分别是\([l_1,r_1],[l_2,r_2]\)，那么它们可以转移到的位置就应该是\([l_1+r_1,l_2+r_2]\)，这个东西长度刚好是\(c(d-a)+c(d-b)\)。
如何计算?理性猜想(一看就是指数级)并打表你可以发现段数很小，实际上段数是\(O((a+b)\log n)\)级别，所以爆算即可。
很多年后回来看这个，感觉当时对闵和理解不是很深刻。随便看看吧。
R9 T3
是格点三元组计数问题。Pick定理+毒假筛，重工业，这不好。
R10 T1
给两个\(n,m\)次的首一多项式\(F,G\)，假设它们的所有根分别是\(u_1,\dots,u_n,v_1,\dots,v_m\)，求多项式
\[\prod_{i=1}^n\prod_{j=1}^m(z-u_i-v_j)\]的最高\(L\)次项系数。可以证明系数全是整数。膜998244353。\(n,m,L\leq 10^5\)。
rqy的带项式。看到求最高次先reverse，看到一堆\(\prod\)先取\(\ln\)。
\[\begin{aligned}&\ln\prod_{i=1}^n\prod_{j=1}^m(1-(u_i+v_j)z)\\=&-\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^\infty\frac{(u_i+v_j)^kz^k}{k}\\=&-\sum_{k=1}^\infty\frac{z^k}{k}\sum_{i=1}^n\sum_{j=1}^m(u_i+v_j)^k\end{aligned}\]遇到了僵局，考虑直接二项式定理硬展 :
\[\begin{aligned}=&-\sum_{k=1}^\infty\frac{z^k}{k}\sum_{i=1}^n\sum_{j=1}^m(u_i+v_j)^k\\=&-\sum_{k=1}^\infty\frac{z^k}{k}\sum_{i=1}^n\sum_{j=1}^m\sum_{t=0}^k\binom{k}{t}u_i^tv_j^{k-t}\\=&-\sum_{k=1}^\infty\frac{z^k}{k}\sum_{t=0}^k\binom{k}{t}\left(\sum_{i=1}^nu_i^t\right)\left(\sum_{j=1}^mv_j^{k-t}\right)\\\end{aligned}\]先看最里面的东西，好像还是遇到了僵局。
但是别忘了\(u,v\)是根，这是一个经典问题，我们对\(F^R\)取个\(\ln\)就会出现奇妙的事情
\[\ln F^R=\sum_{i=0}^n\ln(1-u_iz)=\sum_{j=1}^\infty\frac{z^j}{j}\sum_{i=0}^nu_i^j\]所以实际上这个东西可以\(\ln\)一次得到。
考虑预处理第二个\(\sum\)里的内容，发现是一个二项卷积 :
\[\begin{aligned}c_k&=\sum_{t=0}^k\binom{k}{t}\left(\sum_{i=1}^nu_i^t\right)\left(\sum_{j=1}^mv_j^{k-t}\right)\\\frac{c_k}{k!}&=\sum_{t=0}^k\left(\frac{\sum_{i=1}^nu_i^t}{t!}\right)\left(\frac{\sum_{j=1}^mv_j^{k-t}}{(k-t)!}\right)\\\end{aligned}\]卷就是了。搞完了做一个\(\exp\)，复杂度\(O(L\log L)\)。
R10 T2
树上吉老师线段树合并。写起来比较恶心。反正我没写过（
R10 T3
zhx著名送命题 九维dp。
R11 T2
给一棵有边权的树，每次给一个编号区间和一个\(k\)，查询在这个区间里面选\(k\)个点，把它们连起来所需的代价的最大值。\(n\leq 3\times 10^5,q\leq 10^4,k\leq 100\)，边权是正的。
这是 CometOJ #8 F 黄金体验 的魔改版。做法不是很一样。原题是带修改的全局查询，使用lct维护链剖分。
好题。看数据范围知复杂度，这题是\(O(n\log n)-O(k)\)之类的东西。
首先是一个经典问题，全局单次询问怎么做?据说这个trick用的很多，不过我搜了搜也没搜到/kk
我不会讲。这里给出CometOJ #8及题解的地址。比较感性，但是很对。
结论是，随便找一个带权直径的端点，对树进行边权意义下的长链剖分，那么取前\(k-1\)长的长链的链底加上根就是答案点集。
好了接下来我们也会合并了。要合并两个点集，我们可以直接合并直径，然后建立虚树进行剖分，使用归并排序+st表lca建虚树就可以做到\(O(k)\)。
考虑建立线段树，每个点维护区间的点集，那么就有了一个\(O(kn)-O(k\log n)\)的拖拉机做法。
其实还可以优化。为了砍\(\log\)，我们考虑用st表代替线段树并使用四毛子，假设块大小是\(B\)，那么预处理复杂度是\(O(\frac{kn\log n}{B})\)，查询是\(O(B+k)\)，那么取\(B=\Theta(k)\)可以得到复杂度是\(O(n\log n)-O(k)\)。
这里面各种性质实在是太感性了。除此之外这是一道四毛子好题。
R11 T3
定义一条链的权值是链上所有点编号的异或和，维护一个森林，支持加边，删边，查询森林中所有树上的所有重链放到一起，权值的第\(k\)小。如果一个点有多个子树大小最大的儿子，取其中编号最大的。加边的时候新树的根改为第二个操作点，删边的时候深度更大的点自动成为新树的根。\(n\leq 10^5,m\leq 5\times 10^5\)，时限5s。
lxl重工业。类似lct，我们用若干平衡树维护这个重链剖分结构，同时每个点开一个可删堆维护子树最大的轻儿子，全局开一个平衡树维护答案。这里选择Splay并不会让你复杂度更优。
这个工业基础算法核心是，边的变化量很少，而轻边变成重边可以合并两端的平衡树，重边变成轻边可以拆开平衡树，每次变化的操作复杂度是一个\(\log\)的。
\(\mathrm{Link}(u,v)\): 只考虑\(u,v\)都是根的情况，否则先做两次还没实现的\(\mathrm{Reroot}\)就好了。
我们发现\(v\)的重儿子可能会变成\(u\)，而\(u\)的重儿子一定不变，这样只需要检查一下是否有\(\mathrm{size}(u)>\mathrm{size}(\mathrm{son}(v))\)就好了。当然这里\(\mathrm{son}\)指的是重儿子。
\(\mathrm{Cut}(u,v)\): 只考虑\(v\)是根的情况。否则先做\(\mathrm{Reroot}\)就好了。
跟\(\mathrm{Link}\)相同，只需要考虑如果\(u\)就是\(v\)的重儿子，就找到\(u\)儿子中子树最大的换一下重儿子。
\(\mathrm{Reroot}(u)\): 把\(u\)到根路径翻转，爆力当然是枚举这条路径上的点看重儿子的变化情况。我们考虑什么情况下重儿子一定不会变。
重儿子变化分为三种，要么是原来的重儿子变成了父亲，一个轻儿子变成了重儿子；要么是重儿子变成了轻儿子，父亲变成了重儿子；要么是重儿子变成了父亲，父亲变成了重儿子。
假设当前考虑到\(t\)，我们设以点\(t\)为根，\(u\)所在的子树、最大轻儿子的子树、父亲的子树大小分别是\(su(t),ss(t),sf(t)\)，换根之前、之后\(t\)的子树大小分别是\(s_0(t),s_1(t)\)。显然有\(su(t)+ss(t)\leq s_0(t),sf(t)+ss(t)\leq s_1(t)\)。
第一种表示出来就是\(su(t)>ss(t)>sf(t)\)，那么\(sf(t)\leq\frac{1}{2}s_1(t)\)。这个点数不超过\(\log n\)，可以从原来的根开始不停二分得到。
第二种表示出来就是\(sf(t)>ss(t)>su(t)\)，那么\(su(t)\leq\frac{1}{2}s_0(t)\)。这个点数不超过\(\log n\)，可以从\(u\)开始不停二分得到。
第三种表示出来就是\(su(t),sf(t)>ss(t)\)，这个好像不是很好办。不过仔细想一想，你发现它连出去的重边换了方向，但是连进来的重边也换了方向，否则连进来的一定不是第三种，我们已经处理过了。所以它的重链是不变的，不用处理。
复杂度\(O((n+q)\log^2 n)\)。
R12 T1
给一棵\(n\)个点的树，求每次删掉至少一个点，删\(k=1,...,n\)次把它删空的方案数，要求每次删之后树还是连通的。\(n\leq 400\)，时限3s。
毒瘤场（
考虑既然是T1，有没有什么简单做法，比如考虑删完是连通的可以考虑每次删若干条边……你发现全都需要恐怖的容斥。这不好。
当然容易想到dp，但是这个删完连通就很麻烦。
我们转化一下，在每个点上面写一个删除时间，那么 每次删完连通 就变成 时间\(\geq k\)的连通。
不过如果随便写时间我们可能得到有的时刻没有删点，仔细想一想这是一个二项式反演的形式，可以直接容斥掉。
考虑一个树形dp。设\(dp(u,i)\)表示删光\(u\)子树，并且\(u\)在时刻\(i\)删掉的方案数。
然后你发现没法转移，因为你只知道\(u\)啥时候删不够，\(u\)必须要跟子树里的点连通，这相当于限制删\(u\)的时刻，所有跟\(u\)不连通了的点都必须已经删完了。所以我们加一维，设\(dp(u,t,i)\)表示在时刻\(t\)(及之前)删光\(u\)子树，并且\(u\)在时刻\(i\)删掉的方案数。
考虑转移，我们枚举最后一次删了什么点。如果删的包含\(u\)，那么\(u\)的子树全空了，并且这要求\(u\)的各棵子树在这一时刻也被删完，并且\(u\)的儿子们也是子树中最后被删的(不然不连通)，所以方案数是
\[\prod_{u\rightarrow v}\sum_{j=1}^i dp(v,j,j)\]如果删的不包含\(u\)，那么删完\(u\)之后没删的点一定都在\(u\)的同一棵子树里，同时这棵子树的根一定不比\(u\)早删除(不然不连通)，其它子树在此之前已经删完了。我们枚举这棵子树，可以写出方案数
\[\sum_{u\rightarrow v}\left(\sum_{j=i}^{t}dp(v,t,j)-dp(v,i,i)\right)\left(\prod_{u\rightarrow w,w\neq v}\sum_{j=1}^i dp(w,j,j)\right)\]为什么要减去那个东西?因为我们讨论的是最后一次删的不包含\(u\)的情况。
使用前缀和优化，复杂度\(O(n^3)\)。
R12 T2
有\(n\)个球和一个无限长的白色板还有一个数\(m\)，现在你要从头开始给色板染色，你可以选择
把当前格子染成红色，然后选\(m\)个球扔掉。球不够则不能染。
把当前格子染成蓝色，然后选\(m-1\)个球扔掉。球不够则不能染。
把当前格子不染色，然后结束染色。
问有多少种不同的染色方案。两个方案不同，当且仅当有一个球是否被扔掉的情况不同，或者有一个格子最后的颜色不同。\(n\leq 10^{14},m\leq 2000\)，膜998244353。
考虑一个dp，设\(dp(n)\)表示有\(n\)个球、只考虑前两种染色的方案数，那么就有
\[dp(n)=\binom{n}{m}dp(n-m)+\binom{n}{m-1}dp(n-m+1)\]拆啊!
\[\frac{dp(n)}{n!}=m!\frac{dp(n-m)}{(n-m)!}+(m-1)!\frac{dp(n-m+1)}{(n-m+1)!}\]你就看到了一个常系数齐次线性递推。容易矩阵快速幂做到\(O(m^3\log n)\)，这已经很快了，但还不够快。
爆力拆答案的式子!
\[\begin{aligned} S(n)&=\sum_{i=1}^nn!\frac{dp(n)}{n!}\\ &=\sum_{i=1}^nn!\frac{dp(n-m)}{(n-m)!}+\sum_{i=1}^nn!\frac{dp(n-m+1)}{(n-m+1)!}\\ &=\frac{n!m!}{(n-m)!}\sum_{i=1}^n(n-m)!\frac{dp(n-m)}{(n-m)!}+\frac{n!(m-1)!}{(n-m+1)!}\sum_{i=1}^n(n-m+1)!\frac{dp(n-m+1)}{(n-m+1)!}\\ &=\frac{n!m!}{(n-m)!}S(n-m)+\frac{n!(m-1)!}{(n-m+1)!}S(n-m+1)\\ \frac{S(n)}{n!}&=m!\frac{S(n-m)}{(n-m)!}+(m-1)!\frac{S(n-m+1)}{(n-m+1)!} \end{aligned}\]也许是我naive了，并不知道有没有 前缀和和原序列的递推式相同 这种性质。
反正我们可以对这个做一次多项式取膜。答案就是\(n!(z^n\bmod{(z^m-(m-1)!z-m!)})\)。复杂度是\(O(m\log m\log n)\)。当然如果爆力实现多项式运算，码量会减小114514倍，复杂度是\(O(m^2\log n)\)，也可以通过这题。
R12 T3
给定\(n,m\)，构造一系列集合\(A_1,\dots,A_n\)，其中每个集合\(A_i\)是由\(A_{i-1}\)加入那些满足 \(\varphi(x)\in A_{i-1}\)且\(x\)的所有质因子大小都不超过\(m\) 的数得到的。求\(A_1,\dots,A_n\)的大小。\(n\leq 5\times 10^4,m\leq 10^7\)。
一道神仙题，省选完了再补。省选要出这种题也只可能放T3吧。
R13 T1
有一个长为\(n\)的序列，给定\(m\)个区间，要求每个区间里面的数拼起来是\(9\)的倍数，求序列的方案数，膜1e9+7。\(n\leq 10^9,m\leq 15\)。
考虑是\(9\)的倍数，当且仅当每一位加起来是\(9\)的倍数。这样应该可以设状态了吧?
好像还是有难度。我们当然用前缀和拆掉这个东西，那么就变成了，有若干个前缀和，每个限制相当于其中两个前缀和的差必须是\(9\)的倍数，也就是他们膜\(9\)相等。
然后就变成了限制一些位置必须相等，剩下的随便选，求方案数。
首先肯定要预处理出连通块。
注意这里有个小问题，就是一个数跟上一个数选相同的有两种方案，也就是填0和9。但是跟上一个数不同的话，每种不同有一种方案。
如果不考虑这个多出来的方案，那么答案就是\(10^{连通块个数}\)(也许你觉得底数不是\(10\)，因为我没说清楚，这个不重要)。但是考虑的话做法就完全不同了。
最爆力的方法是，爆搜钦定每个连通块的情况，然后中间可以预处理一个方案数，用矩阵快速幂优化方案数的递推，复杂度是\(O(9^mm+m\log n)\)。完全跑不过。
方案数怎么预处理?我们设\(f(i)\)表示长为\(i\)的区间，两边相同的方案数，\(g(i)\)表示两边不同的方案数，那么讨论最后一个跟倒数第二个是不是相同，有转移
\[\begin{aligned} f(i)&=2f(i-1)+g(i-1)\\ g(i)&=9g(i-1)+8f(i-1) \end{aligned}\]嗯。事实上你还可以解出通项直接快速幂，不过瓶颈不在这里。
状态很妙。考虑以填的数字作为阶段进行状压dp，我们设\(dp(i,S)\)表示填到数字\(i\)，已经处理了集合\(S\)中的连通块的方案数。转移的时候枚举一个子集表示哪些填了数字\(i\)，然后扫一遍计算已经填好的点之间的贡献，复杂度\(O(3^mm+m\log n)\)。
R13 T2
给平面内三个整点点集\(A,B,C\)，每个点集都在同一直线上，问有多少种方案选出三个点\(a\in A,b\in B,c\in C\)，使得\(c\)是\(a,b\)的中点。\(n\leq 10^5,\vert x\vert,\vert y\vert\leq 10^5\)，五组数据，时限3s。
计算几何还是要大分类的。
中点太怪了。写个式子 :
\[\begin{aligned} x_c&=\frac{x_a+x_b}{2}\\ y_c&=\frac{y_a+y_b}{2} \end{aligned}\]呃，先去掉那个可恶的系数吧
\[\begin{aligned} 2x_c&=x_a+x_b\\ 2y_c&=y_a+y_b \end{aligned}\]呃这是一个很好的式子。我们分别设两条直线的解析式是\(f_A(x),f_B(x)\)，那就有
\[\begin{aligned} 2x_c&=x_a+x_b\\ 2y_c&=f_A(x_a)+F_B(x_b) \end{aligned}\]竖线可以特判掉。这是一个二元一次方程组，我们对每个\(c\)解出来，然后看是否有这样的\(a,b\)就好了，还是可以用map完成。
但是如果一个点集完全是一个点，没有什么解析式，那么只需要枚举一个\(c\)，然后拿map查另一个点集就好了。
但是如果\(A,B\)的两条直线平行，就会出现线性相关，此时无解好说，无穷解的话就需要考虑一下。
发现平行且无穷解，当且仅当\(A,B,C\)都平行并且\(C\)恰好在\(A,B\)中间，那么此时横坐标对了纵坐标一定对，所以我们可以直接用呐塔塔卷这个横坐标，就做完了。
R13 T3
原题AGC007 E Shik and Travel。
带边权的完全二叉树，从\(1\)出发遍历一遍树并回到\(1\)，把访问叶子的顺序记录下来，最小化两个相邻叶子之间距离的最大值。\(n,v\leq 2^17=131072\)。完全二叉树说的是内部结点都有两个儿子。
最小化最大值，显然二分啊（
二分之后，发现贪心不是很可以(因为是遍历一遍，每个点只能走一次)，可以考虑子树的合并，设\(dp(u,i,j)\)表示从\(u\)出发遍历完\(u\)子树，第一个叶子的距离是\(i\)，最后一个叶子的距离是\(j\)，有没有可能。
转移的时候，我们合并两个儿子，具体地，\(dp(u,i,j)\leftarrow dp(u,i,j)\ \mathrm{or}\ dp(lc,i,k)dp(rc,l,j)(k+l\leq mid)\)。可以前缀和+bitset优化，复杂度是\(O(\frac{n^3\log n}{w})\)，显然过不了。
题解给出了奇妙的性质。对于两个状态\(dp(u,i_1,j_1),dp(u,i_2,j_2)\)，如果\(i_1\leq i_2,j_1\leq j_2\)，那么后面那个完全没有用。所以我们知道有用的状态具有一些单调性。如果把一个点的状态按\(i\)升序排，有用的状态的\(j\)一定是降序的。所以我们可以用two pointer来优化这个转移，具体地，可以枚举左儿子的一个有用状态，此时右儿子的一个前缀都可以转移，我们用two pointer维护这个前缀，然后每次转移\(i\)最大，也就是\(j\)最小的那个就好了。复杂度降为\(O(n^2\log n)\)。
如何优化?启发式合并，我们在小的那一边枚举一个点，同时批量处理大的那一边，复杂度降为\(O(n\log^2 n)\)。
论文哥还是很良心的（
qlr ak!好吧差50pts。
R14 T1
有一个没有权的网络，现在要选一些点，使得\(s\)到\(t\)的每条路径上都有至少\(k\)个选择的点，最小化选择的点权。\(n\leq 200,m\leq 512,k\leq 5\)。
显然是最小割，所以我们先拆点。
看到\(k\leq 5\)你就知道要分层。我们建\(1,\dots,k\)一共\(k\)层，那么问题转化成，我们让每一层都搞一个割，并且一个点不能重复割。
不能重复割，可以限制两条边不能同时割，这个好像很难。
题解给出的做法是，每层的入点向下一层的出点连边，表示如果流流到了入点这里才被割掉或者直接没有被割掉，那么下一层的这条边割掉了也没有用了。这样就可以保证每条边只被割一次。
然后你一看这个网络就知道，总的源点是第一层的源点，总的汇点是最后一层的汇点。
R14 T2
\(n\times m\)的网格，问随机画一个三角形，边界上的格点个数期望。三角形不能是三点共线。膜998244353。\(n,m\leq 10^6\)。
考虑对于每条边计算贡献。注意我们需要去掉一个端点来避免重复计算。那么假设两边长\(a,b\)，众所周知边上格点数就是\(\gcd(a,b)\)。然后这条边可能有\((n-a)(m-b)\)种位置，枚举一个\(\gcd\)，会得到两个调和数复杂度的东西。然后我们乘上\(nm-2\)，也就是另外一个点的方案数，就得到了三个点随便选(三个点不相同)的格点数。
接下来我们需要减去共线的情况。我们枚举最长的边，然后考虑第三个点有\(\gcd(a,b)-1\)种情况在这条线段上，然后乘个数量减去就好了。复杂度是\(O(n\log n)\)。
R14 T3
给一堆串，你要建一棵Trie，使得每个串都可以表示成这棵Trie上的一条祖孙链，求Trie的最小结点数。\(n,\vert S\vert\leq 200\)。
考虑建一张有向图，\(s_1\rightarrow s_2\)的边权是\(s_1\)最长的存在于\(s_2\)中的前缀，并加入一个空串，那么问题转化为最大内向树，可以使用朱刘算法在\(O(n^3)\)时间内解决。
R15 T1
你有一块黑板，一开始上面有\(n\)个数的序列\(a\)，你每次可以选择黑板上的一个数，把它左移一位，或者跟黑板上另一个数异或起来再写回去，注意操作不会删掉操作数。求\([0,m]\)之间有多少个数可以被写出来，膜998244353。
由于除了\(n\)以外，这些数实在是太大了，都用二进制给出，\(n\leq 20\)，\(a_i,m\)不超过\(8\times 10^3\)位。
rqy式玄学题。考虑把数表示成系数膜2的多项式，那么异或对应加法，左移对应乘\(z\)，然后这就变成了线性组合，根据著名结论一堆多项式可以线性组合出来的一定是它们\(\gcd\)的倍数。设这个\(\gcd\)为\(F\)。
如何计算一个多项式的倍数个数?考虑我们不管怎么确定一个多项式的前\(\deg(M)-\deg(F)+1\)位，剩下的\(\deg(F)-1\)位总有唯一的方法确定，因为这个东西膜\(F\)位数不超过\(\deg(F)-1\)。不过如果前面都跟\(M\)相同，那么我们需要做一次取膜求出来这个数后面是多少，然后判断是否\(\leq M\)。
当然我们bitset压位做多项式运算，跑的飞快。
R15 T2
有一个长\(n\)的01串，每次可以交换一对逆序对，求有多少种方案换成有序。膜给定的质数\(p\)。\(n\leq 2\times 10^5,p\leq 10^6\)。如果得到的答案膜\(p\)是\(0\)，那么输出它包含的\(p\)的个数，和除掉\(p\)之后得到的数膜\(p\)的值。
最后当然是变成$0…01…1$这样的，并且$01$内部的顺序分别没有变。考虑我们把$0$编号为$01,…,0{c_0}$，$1$同理，把操作序列写成每次选择一个$1i$和一个$0_j$交换，那么一个操作序列合法当且仅当交换$1_i,0_j$的时候$1_i$真的在$0_j$前面一位，并且每一对逆序的$1_i,0_j$出现恰好一次。可以发现这个等价于$1{i+1},0j$和$1_i,0{j-1}$都已经换完了，于是这就转化成杨表计数。和 雅礼集训2017 D11 path 一样做即可。
R15 T3
随机一个序列，对于每个前缀求出中位数。\(n\leq 3\times 10^7\)，时限2s。
所有人都拿了70pts(3e5)，没有人拿到100pts/jy
概率题。
做法是，二叉堆在数据随机的情况下是期望\(O(1)\)的。
对顶堆，但是我们在中间维护一个长为\(B\)的有序数组。
每次插入一个数，跟有序数组的左边和右边比较，如果不该插到中间就直接扔进堆，复杂度期望\(O(1)\)；
如果要插到中间，我们爆力插入，然后看是弹掉左边还是弹掉右边，复杂度是\(O(B+\log n)\)，概率是\(\frac{B}{i}\)，其中\(i\)是已经放的个数；
如果出现两边堆不平衡导致中位数不在中间了，我们爆力重构，复杂度是\(O(B\log n)\)，概率……这相当于中位数在中间一条线段上随机游走，概率是\(\Theta(\frac{1}{B^2})\)。
总的算起来是\(O(n+\sum_{i}\frac{B^2+B\log n}{i}+\frac{n\log n}{B})=O(n+B^2\log n+B\log^2 n+\frac{n\log n}{B})\)。取\(B=\Theta(\log n)\)即可。
R16 T1
求\([1,n]\)有多少整数可以写成两个自然数平方和。\(n\leq 10^{11}\)。
呃，这是一道模板题?
发现\(f(n)=[n\text{是二平方和}]\)是一个积性函数，因为是二平方和当且仅当所有\(4n+3\)型质因子全是偶数次。这个函数在质数处全是\(0\)，质数幂处随便算，直接套min_25筛即可。
但是如何线筛?我们跑完一遍线筛之后，用\(4n+3\)型质数再筛一遍即可。也可以线筛中直接处理。
当然最好的方法是分段打表。
R16 T2
数轴上有一堆棋子，每个棋子有一个初始位置，它们会跳，每个棋子每一轮有\(\frac{1}{2}\)的概率跳到关于第\(i-1\)个棋子的对称点，\(\frac{1}{2}\)的概率跳到关于第\(i+1\)个棋子的对称点。棋子要跳\(k\)轮，每一轮要跳的棋子都是相同的，按照给定的序列\(a_{1,\dots,m}\)的顺序来跳。问最后每个棋子位置的期望。\(n,m\leq 10^5,k\leq 10^{18}\)。
考虑期望的线性性，因为对称点很线性。
我们可以直接按照给的式子，分别跳到两个对称点并除以\(2\)就是位置的期望，而根据期望的线性性，把期望当成真的位置，如此递推\(k\)轮就得到了答案。复杂度\(O(mk)\)。
如何优化?矩阵快速幂，复杂度\(O(m^3\log k)\)，显然不行。
看一看这个式子\(x^\prime_i=x_{i-1}+x_{i+1}-x_i\)，你是不是想到了CF上一类每次可以操作一个数的题?
我们作差分\(s_i=x_i-x_{i-1}\)，那么上面的一步操作之后，我们得到\(s^\prime_i=x^\prime_i-x_{i-1}=x_{i-1}+x_{i+1}-x_i-x_{i-1}=s_{i+1}\)，也就是说这样一次操作相当于交换两个\(s\)。求出每个循环，然后膜一下看看转到哪里就好了。
R16 T3
有一个串，定义\(\mathrm{lcp}(i,j)\)为后缀\(i,j\)的\(\mathrm{lcp}\)，\(\mathrm{lcs}\)反过来(前缀的lcs)，求
\[\sum_{i=1}^n\sum_{j=i+1}^n\gcd(\mathrm{lcp}(i,j),\mathrm{lcs}(i,j))\]ull自然溢出，\(\vert s\vert\leq 2\times 10^5\)。
考虑\(\mathrm{lcp},\mathrm{lcs}\)拼到一起，实际上相当于从\(i\)出发和从\(j\)出发左右扩展，扩展出两段相等的，所以\(i,j\)同时左右移直到两边，这一堆贡献都可以预处理出来。
建立SAM，每个点考虑它里面所有本质相同子串的贡献，那就是先选两个，然后计算贡献。可以在SAM上线段树合并求出数量，然后对贡献打前缀和搞出这个结点所有本质不同子串的贡献，因为它们长度是一个区间。复杂度\(O(n\log n)\)。
R17 T1
有三种东西，第一种值为\(a\)，第二种是\(b\)，第三种可能是\([0,\frac{b}{2}]\)中任意整数。毒瘤拿了\(n\)个东西，问有没有可能值的和是\(m\)。多组数据，\(T\leq 10^6,n,m,a,b\leq 10^{18}\)。保证\(a<b\)。
有CF内味了。
考虑一上来全选\(b\)，还不够\(m\)那就无解。然后考虑换一些\([0,\frac{b}{2}]\)，如果我们换了一个，就可以得到\([(n-1)b,(n-1)b+\lfloor\frac{b}{2}\rfloor]\)，换了\(k\)个就是\([(n-k)b,(n-k)b+k\lfloor\frac{b}{2}\rfloor]\)。
你会发现它们的交刚好是\([0,(n-1)b+\lfloor\frac{b}{2}\rfloor]\)，这是因为\(2\lfloor\frac{b}{2}\rfloor\geq b-1\)，只要换两个就可以填满。除此之外还可以不换，这是\(nb\)。
如果\(m\)不在那个大区间里面，考虑换几个\(a\)，也就是说我们可以让整个可行区域左移\(b\)再右移\(a\)，也就是左移\(b-a\)，那么此时只有可能是把\(nb\)左移到了\(m\)，判断是否有\((nb-m)\bmod{(b-a)}=0\)即可，复杂度\(O(T\log n)\)。
R17 T2
仙人掌上计数的奇怪问题，省选完再补。
R17 T3
给\(n\)个可达的点和一堆圆，如果两个点可达那么连线也可达，求有多少个圆里面全是可达的。\(n,m\leq 5\times 10^5\)。
真实的数据结构+计算几何题!
显然先凸包，然后变成了圆是不是在凸包里面。
转化成把凸包收缩一个半径，判断圆心在不在凸包里面。这个收缩说的是每条线段沿法线向内部移动。
先离线，然后我们按半径从小到大排序，从空的凸包开始扩张。这个空的就是凸包直径的中点，或者如果直径很多就是一条线段。我们用极角序平衡树维护线段，每次扩张到一条线段出现，就把它插入平衡树。每次遇到一个查询，因为凸包上的边在扩张到这个查询之前不会变，所以我们通过在这棵平衡树上找到圆心的极角对应的\(O(1)\)条直线，可以直接知道这个点扩张到那个时刻之后是不是在凸包里面。复杂度\(O((n+m)\log n)\)，细节……呃。
好像是CometOJ原题?
这一场名字有点怪（
R18 T1
模拟!模拟不好。
R18 T2
最短路，有一次使用玄学移动的机会，如果从\(i\)玄学移动到\(j\)，代价是\((i-j)^2\)。\(n\leq 2\times 10^5,m\leq 4\times 10^5,w\leq 10^9\)。
先拆式子，变成\(i^2+2ij+j^2\)。怎么看怎么像 回家路线 。
不考虑分层图。反正只有一条边连接两个点，我们从\(s,t\)分别跑一遍最短路，记为\(d_1(u),d_2(u)\)，目标就是最小化\(d_1(i)+i^2+d_2(j)+j^2+2ij\)。直接李超树维护。
R18 T3
怪题。省选完了再补。
R19 T1
有一个序列\(a_0\)，你这样计算\(a_i\)
\[a_{i,j}=\sum_{k=1}^j[a_{i-1,k}=a_{i-1,j}]\]，需要支持\(a_0\)单点修改，或者查询\(a_{x,y}\)的值。\(n\leq 10^5,a_i\leq 10^4\)。
打表题。
直接硬想，知道每次所有相同的会变成\(1,2,3,...\)这样的，然后重新搞相同的，事实证明很少的几轮，实际上是三轮之后就一定可以循环，我们可以打表修改的贡献，发现就是一堆乱七八糟的东西，可以分块，维护每个块的值域vector。
R19 T2
有一个棋盘，有一些格子挖去了，你要画一条哈密顿回路，同时有一些限制是某个格子处必须拐弯，最小化违反的限制数量。\(n,m\leq 25\)。
发现25大概不是状压dp了，而25^2=625可能是n^5之类的东西?
网络流。黑白染色，建立二分图(源连黑，白连汇)，源点到黑点连容量\(2\)，费用\(0\)表示每个格子需要连两条边；白点到汇点相同。这就得到若干个哈密顿回路。
考虑那个限制说的是，如果不拐弯就要付出\(1\)的代价，那么我们给每个黑点建立两个点分别表示横着和竖着的，然后横点连向它左右的点，竖点连向上下的点，容量为\(1\)，费用为\(0\)。为了表示连两个相同方向的要付出代价，两个不同方向的则不用，黑点向横点连两条边，一条容量\(1\)费用\(0\)，一条容量\(1\)费用\(1\)，竖点相同。跑最小费用最大流。
R19 T3
跟T1类似，式子变成了
\[a_{i,j}=\bigoplus_{k=j}^{j+l-1}a_{i-1,k}\]，并且只求一次最终序列\(a_t\)，其中\(\oplus\)是异或，为了式子好看。\(n,l\leq 3\times 10^5,t\leq 10^{18}\)。加强版 : 序列变成环。
倍增。类似于 CCC2016 生命中的圆，本质都是异或两次会消去的性质。
见到这类异或的题，就可以考虑利用异或的线性性直接拆开贡献，并对单个的情况进行打表。
R20 T1
有个长\(n\)的数组\(a\)，定义\(f(l,r)\)为数组\(a\)的子段\(a[l,r]\)中单调不降子段的个数。有一个长\(m\)的下标数组\(p\)，每次查询下标数组的一个区间\([x,y]\)，你需要选出一个\(i\in[x,y]\)，最小化 对于所有\(j\in[x,y]\)，\(f(p_i,p_j)\)的最大值。\(n\leq 5\times 10^5,m\leq 10^5,q\leq 10^5\)。
呃简单题，就是有点麻烦。
考虑区间单调不降子段个数怎么计算，容易想到我们可以搞一个划分，每一段是一个极长单调不降子段，那么只需要考虑跨过的段的总和，并特殊处理掉两边，做一些预处理(对段做前缀和，计算每个位置在哪一段)，复杂度是\(O(1)\)的。
这个最大值最小可以想到二分，但是有一些别的性质可以先考虑。把\(p\)上的区间排序之后，对于\(p_i\)，\(f(p_i,p_j)\)关于\(p_j\)是一个单谷函数，也就是说最大值在两端取到，也就是说实际上我们最小化最大值，最小化的是对于最小的\(p_{j_0}\)和最大的\(p_{j_1}\)，\(\max(f(p_i,p_{j_0}),f(p_i,p_{j_1}))\)的值。
然后我们就固定了两个点，得到了两个函数，\(f(p_i,p_{j_0})\)关于\(p_i\)单调递增，而\(f(p_i,p_{j_1})\)单调递减。三分变二分，搞出两个函数的交点，然后在区间中找前驱后继即可。这个最大值和前驱后继可以主席树实现。复杂度\(O(n+(m+q)\log n)\)。
R20 T2
有一棵白色的树，你每次随机两个点(可以重合)，然后把它们的链染成黑色，问期望多少次之后染成全黑。\(n\leq 120\)，膜998244353。
很久之后来补了题解。
显然min-max容斥，然后这是几何分布，问题是算一个点集\(T\)被随到的概率。考虑删去这个点集之后，树变成若干连通块\(F(T)\)，选在连通块内部就不行，所以概率是\(\frac{\frac{1}{2}n(n+1)-\frac{1}{2}\sum_{a\in F(T)}s_a(s_a+1)}{\frac{1}{2}n(n+1)}\)。直接做是\(O(2^nn)\)的。
注意到\(\sum_{a\in F(T)}s_a^2\)这个东西只有\(O(n^2)\)级别，所以我们可以考虑枚举这个东西的值，计算\(T\)的容斥系数之和。经典题是 Gym102978H Harsh Comments。
设\(dp(u,i,j,0/1)\)表示\(u\)子树中选择了若干个连通块并且\(u\)在其中一个，这个连通块大小是\(i\)，这些连通块的\(\sum_{a\in F(T)}s_a(s_a+1)=j\)，没选的点个数奇偶性是\(0/1\)的方案数；\(g\)表示\(u\)不在一个连通块中的方案数。\(g\)的转移显然，\(dp\)的转移是卷积，复杂度据说是\(O(n^6)\)，完全跑不动。
考虑如何优化。这里是计数背包，转移是二维卷积，我们把第二维改成法法塔，就把变成了\(O(n^4\log n)\)，继续优化就换成点值即可。讲道理这题挺好的。
我第一眼看没秒这个dp，是因为之前的式子算的是什么选在连通块之间就可以，然后那个式子带有离谱交叉项，所以说还是应该优先考虑局部性强的东西。
R20 T3
维护一个平面，支持插入点，查询有多少个点的三元组构成的三角形包含原点。在边界上不算包含。\(n\leq 4\times 10^5\)，2s。
平衡树，按极角排序，那么三角形包含原点说的就是对于一个点，另两个点和它的极角差一个大于180度，另一个小于180度，也就是说钦定这个点之后，方案数就是分别往两边转179.99999999度得到的点数乘起来。
这个怎么维护?两个区间加即可。复杂度\(O(n\log n)\)。