非常套路。首先拆组合意义表示选 $2$ 条边。设 $F_i(x)$ 表示从 $i$ 走到 $fa_i$ 的生成函数，$[x^0]$ 表示没选边，$[x^1]$ 表示选了一条边，$[x^2]$ 表示选了两条边。走过一条边就乘一个 $(1+x)$，转移是 $F(x)=(1+x)(1+\sum(F_{son}(x)+F(x)))/deg$，化简一下就是 $F(x)=\frac{(1+x)(1+\sum F_{son}(x))}{d-(d-1)(1+x)}$，暴力求逆就行了。然后一遍换根可以求出从 $fa_i$ 走到 $i$ 的，然后就做完了。

T3

非常牛的题，再说。

Day 5

T1

难。

$50$ 分是二进制分组，询问次数是 $2\log n$。

给每个点标一个恰好有 $7$ 个 $1$ 的 $14$ 位二进制数，每一位上的 $1$ 向 $0$ 贡献一遍就行了，因为没有子集关系所以是对的。

T2

唐题。

先树剖，考虑编一个标号顺序。到一个点的时候，如果他是链头，就把整条链标上。然后 bfs 遍历距离他小于等于 $3$ 的所有点，给没有标号的标上号，这里 bfs 需要先把重儿子进队，然后再所有轻儿子进队（反过来也行），然后递归做。

性质很好：重链除了最上面三个点连续；子树除了重链和最高三层连续；一个点子树内距离他 $=k(k\leq 3)$ 的所有点，和他不在一条重链上的连续；这样就可以动态维护点权了。

对于一次询问，答案不超过 $3$，然后瞎判一下就行了，需要一个线段树上二分。

T3

$2^nn^2$ 很简单：一行一行的填，可以状压不同等价的列的最后一个字符，每次是一个 $0$ 或 $1$ 变成 $01$ 或 $0$ 或 $1$，要求第一个变的位置必须是 $0$ 变 $1$ 或 $0$ 变 $01$。状态总数是 $2^nn$ 的，转移类似插头 DP 可以做到 $\mathcal O(1)$。最后一个组合数算一下就行了。

正解挺厉害的还是。考虑第一个字符，如果他从 $0$ 变成了 $01$ 或 $1$，则这一行的第二个及之后的字符都是自由的。以这个为阶段 DP。

设 $f_{t,i,j,0/1/01}$ 表示当前有一个长度为 $i$ 的串，经过了 $t$ 次分裂操作之后变成了长度为 $j$ 的，其中第一个字符在第一次操作后变成了 $0/1/01$，并且整体合法的方案数。注意这个定义非常神秘。他的第一行是任意填的，即如果要使用 $f_{,,,1}$ 和 $f_{,,,01}$ 时需要保证第一个字符之前已经合法或者第一个字符是 $0$，使用 $f_{,,*,0}$ 时需要保证第一个字符之前已经合法。

首先对于 $f_{t,i,j,1}$，第一个字符从 $0$ 变成 $1$ 的话，第二个及之后的字符可以任意分裂。那就是 $\sum f_{t,i-1,j-1,*}$。

对于 $f_{t,i,j,0}$，第一个字符会在某个时刻从 $0$ 变成 $01$ 或 $1$。枚举时刻 $x$ 以及串在这个时刻的串长 $y$。在这个时刻之前方案数为 $f_{x,i-1,y-1,0/1/01}$，这个时刻之后为 $f_{t-x,y,j,1/01}$。

对于 $f_{t,i,j,01}$，还是考虑第一个字符什么时候发生变化，还是枚举 $x,y$，在这个时刻之前方案数为 $f_{x,i,y,01}$，这个时刻之后为 $f_{t-x,y,j,1/01}$。

初值 $f_{0,i,i,1}=1$。复杂度 $\mathcal O(n^5)$。

Day 6

T1

从后向前直接贪心就是对的。拿个数据结构维护一下就行了。

T2

挺深刻的。

看成是一个链上，要挂若干个点，最小化直径。

类似最小直径生成树的套路，枚举中心所在位置，最小化到他的点的最大值的最小值。如果落在边上是一个单调栈之类的东西。

T3

首先考虑 $AB$ 性质。对于序列的最后一个 $A$，其在操作序列中一定是相邻的 $AC$。把这个东西插到前面的位置里有 $2b-1$ 中方案。归纳，答案是 $(2b-1)!!$。$A$ 性质也是一样的。

太难了，以后再补。

day 7

T1

贡献不大好拆。考虑边分树找边。把所有边权为 $0$ 的并起来之后，剩下的只需要连前驱和后继跑 kruskal 就行了？

一开始写的是 boruvka，但是跑不动啊。kruskal 的正确性不大会证啊。

T2

太变态了这题。

首先如果确定了选哪些菜以及他们的 $a$，可以通过邻项交换证明，按照 $b$ 从大到小排序就是最优的：设有 $(a_1,b_1)$ 和 $(a_2,b_2)$，前者排在前面的条件是 $\max(b_1,a_1+b_2)<\max(b_2,a_2+b_1)$。整理得 $\min(b_2,b_1-a_1)>\min(b_1,b_2-a_2)$。显然等价于 $b_1>b_2$。

然后考虑如果给定了所有的 $a$，要在其中选 $k$ 个的最小代价。就是要最小化 $\max_i(\sum_{j=1}^i a_j+b_i)$。从后向前做，所以按照 $b$ 从小到大排序，$f_{i,j}$ 表示考虑了 $[1,i]$，一共选了 $j$ 个菜，此时的最大值是多少。转移是 $f_{i,j}=\min(f_{i-1,j},\max(f_{i-1,j-1},b_i)+a_i)$。

这个东西看上去不好做，但是如果去掉了 $b$ 他就是凸的，所以其实他是有一些凸的感觉的。考虑算到了 $i$，对于所有 $\leq b_i$ 的 $f$，他以后就永远固定是这个值了，因为第二种转移以后肯定都大于 $b_i$。所以上面的 DP 等价于在做这样一件事：维护一个小根堆，每次加入 $a_i$，不断弹出值。使得弹出的和成为小于等于 $b_i$ 的最大值，然后把堆顶 $top$ 修改为 $top-(b_i-sum)$，$sum$ 修改为 $b_i$。

下面的计数感觉想了好久才懂啊。首先暴力就是压下来一整个堆的结构还有记录一下弹出的值的和。设 $f_{i,j,l,r,s}$ 表示考虑了 $i$ 个数，选了 $j$ 个，钦定以后小于 $l$ 的需要加进来，$>r$ 的不能加进来。对于当前的 $b$，如果 $s<b<s+r$，那说明 $r$ 以后没有被加入，修改了之后 $r+s-b$ 没有被加入。

如果 $s-l<b<s$，那说明 $l$ 加入了，即以后的某个时刻 $b-(s-l)$ 加入了，那后面小于 $b-(s-l)$ 的都需要被加入。妈的太神秘了，就这样理解吧。

T3

数论题滚蛋。

Day 8

有傻逼 A 挂了。

T1

枚举 $y$，选的一定是最小的 $k$ 个 $x$，扫 $y$ 的时候线段树维护即可。

T2

挺唐的感觉。

先判掉不合法。找到区间 $mx$，小于 $mx$ 的数若有 $low$ 个，大于的数有 $up$ 个。

考虑 $low=0$：填相对顺序。$f_{i,j}$ 表示填了 $i$ 个数，当前有 $j$ 个空可以填。可以转移到 $f_{i+1,k\leq j+1}$。画一下：

拉直之后可以看出是格路计数，反射容斥一下可以得到答案是 $\binom{2up}{up}-\binom{2up}{up-1}$。

如果有了 $low$，一旦 $f_{i,j}$ 转移到了 $k\not= j+1$，那 $low$ 就全不能填了。而且 $low$ 内部一定得从小到大填。那枚举 $up$ 一开始走的一个极长链 $i$，方案数是 $(\binom{2up-i}{up}-\binom{2up-i}{up-1-i})\binom{i+low-1}{low-1}$。拆开之后可以组合恒等式 $\mathcal O(1)$ 算。

T3

考虑倒着做。列生成函数：

\[\begin{aligned} F_1(x)&=x^B\\ F_i(x)&=F'_{i-1}(x)+xF_{i-1}(x)\\ ans&=[x^A]F_n(x)\\ G_i(x)&=F_i(x)e^{x^2/2}\\ G_1(x)&=x^B e^{x^2/2}\\ G_i'(x)&=F_i'(x)e^{x^2/2}+xF_i(x)e^{x^2/2}\\ &=G_{i+1}(x)\\ G_n(x)&=(x^Be^{x^2/2})^{(n-1)}\\ F_n(x)&=e^{-x^2/2}(x^Be^{x^2/2})^{(n-1)}\\ \end{aligned}\]

暴力求就行了。或者有个什么组合意义，就是每次可以选择加球（从小到大的标号加），或者选任意一个球取走。

Day 9

没打 T3 暴力，被暴力老哥极限反杀。

T1

暴力 DP 是维护 vector<pii> $f_{i,j}$ 表示 $i$ 子树内用了 $j$ 个块，pair 记的是当前所在块的大小和已经确定的块的平方和。

和一个子树合并了之后，按照 $(fi,se)$ 做一个偏序，发现不是很能过。按照 $(fi,fi\times fi+se)$ 做偏序并只保留前 $100$ 个就过了？？？

T2

你怎么知道我双 $\log$ 草过去了并成为了赛时唯一通过？/kx

考虑拆贡献，对于第 $i$ 行的点，由 Lucas 定理得，最后一行有 $2^{\text{count}(i)}$ 个点对他有贡献。再枚举是第 $j$ 位做的贡献。预处理 $t_x$ 表示 $\text{count}(n-i)=x$ 的 $i$ 之和。

其余点的 GF 显然是 $\frac{1}{1-x}$，列一下这 $2^{\text{count}(i)}$ 个点每个点的 GF，你先要求第 $j$ 位上全都是 $0$：

\[\begin{aligned} F_0(x)&=\frac{1-x^{2^j}+x^{2\times 2^j}-x^{3\times 2^j}\dots}{1-x}=\frac{1}{(1-x)(1+2^jx)}\\ F(x)&=F_0^{2^i}(x)(\frac{1}{1-x})^{n-2^i}=(\frac{1}{1-x})^n(\frac{1}{1+2^jx})^{2^i} \end{aligned}\]

再考虑怎么统计答案，是一个组合数奇数位求和的形式：

\[\begin{aligned} &[x^m]\sum_{k\equiv 1\pmod 2}\binom{2^i}{k}x^{k2^j}\times t_i2^jF(x)\\ =&[x^m]\frac{(1+x^{2^j})^{2^i}-(1-x^{2^j})^{2^i}}{2}\times t_i2^jF(x)\\ =&\frac{1}{2}[x^m]((\frac{1}{1-x})^nt_i2^j-(\frac{1-2^jx}{1+2^jx})^{2^i})\\ =&\frac{1}{2}[x^m](\frac{1}{1-x})^nt_i2^j(1-(\frac{1-2^jx}{1+2^jx})^{2^i}) \end{aligned}\]

后面一坨只需要对于所有 $i$ 求出 $\displaystyle (\frac{1-x}{1+x})^{2^i}$。暴力做 FFT 就过了，但是存在线性做法。

\[\begin{aligned} G(x)&=(1-x)^{a}(1+x)^{b}\\ G'(x)&=-a(1-x)^{a-1}(1+x)^{b}+b(1-x)^{a}(1+x)^{b-1}\\ (1-x)(1+x)G'(x)&=(-a(1+x)+b(1-x))G(x)\\ (n+1)g_{n+1}-(n-1)g_{n-1}&=(b-a)g_n+(a-b)g_{n-1} \end{aligned}\]

递推就行了。最后 $\frac{1}{(1-x)^n}$ 一起乘，复杂度就是 $\mathcal O(m(\log n+\log m))$。

T3

不会做喵。太难了喵。但是分治好像比较容易理解。

Day 10

挂了 $10$ 分，但是还是登顶了。

T1

拍成序列，条件等价于一个区间有序，做完了。

T2

首先有暴力状压 DP。然后考虑当前 DP 到了 $i$，后面有 $n-i$ 个数，有 $n-i+1$ 个间隔，只需要记录每个间隔里有多少数即可。复杂度大概是 $3^{\frac{n}{3}}\text{poly(n)}$。

T3

好难。

Day 11

T1

喜欢保龄。

显然是 dp of dp 状压 LDS 的 DP 数组。对于一个状态 $S$，如果在序列末尾加入一个数字 $x$，就是把 $\leq x$ 的第一个 $1$ 抹除，然后把第 $x$ 位设成 $1$。

注意到如果 $x\in S$ 那就不变。设 $f_{S}$ 表示 $S$ 集合到达的最远的 $i$，需要找到 $f_S$ 后面第一个位置，满足 $a_i$ 和 $a_{i+1}$ 都不在 $S$ 内部。可以记录 $nex_{i,j,k}$ 表示 $i$ 后面第一个出现 $j,k$ 的位置，但是空间爆了。所以定长分块，按照 $a^2$ 大小分块，块内暴力扫一遍检查有没有连续两次出现不合法位置，块外用刚刚的方法记录数组即可。时间复杂度 $\mathcal O(n+2^aa^2)$，空间 $\mathcal O(n+2^a)$。

T2

喜欢折半。

经过一些推导可以得到，答案就是，对于每条边考虑经过他的所有路径，设其长度从小到大是，$a_1,a_2\dots a_k$，则答案是 $\max_i{a_i+k-i+1}$。线段树合并维护这个东西即可。

T3

Day 12

T1

喜欢保龄。

考虑选出性价比最大，即 $b_i/a_i$ 最大的 $(a_0,b_0)$。可以证明除了这一对外，最多选 $a_0$ 个对。证明方式是抽屉原理，考虑把除了这个的对排成一排，对 $a$ 做前缀和，如果有超过 $a_0$ 个对那就一定有一段 $a$ 的和是 $a_0$ 的倍数，可以替换。所以可以 DP 出 $f_{i,j}$ 表示 $a$ 的和最多是 $i$，$b$ 的和最大是多少。

对于 $x$ 比较小可以暴力，对于 $x>a_0\times maxa$，前面的 $a_0\times maxa$ 个对的贡献可以凸包统计。对于更大的一定有 $f_x=f_{x-a_0}+b_0$，这部分只有 $a_0$ 个，可以解一个均值不等式求出。

T2

喜欢保龄。

通过牛鬼蛇神的搜索搜出操作，让一个点的度数变成 $n-1$ 即可。

T3

喜欢保龄。

考虑一次操作，对于一个 $x$，找到一次操作后，谁会变成 $x$，记为 $f_x$。要求的就是 $f^d_x$。

先删去 $[1,a_1-1]$。然后按照 $1$ 分块，遇到一个 $p$ 的时候，令块长加一。则操作就是，记录一个 $pos$，初始为其所在块内 $x$ 是第几个位置。向后跳的时候，找到下一个块中除了 $p$ 以外的第 $x$ 个空位，并更新 $pos$。

最终所在块是好求的，要求的就是 $pos$。可以发现从左到右，$pos$ 的变化为，对于一个 $p_i$，把所有 $\geq p_i$ 的 $pos$ 加一，可以从左到右扫描序列，用一个平衡树随便维护。

Day 13

菜就多练。

T1

暴力状压子树点集，并记录根，每次向上合并即可。

T2

从后向前状压，看成加入一个体积为 $2^i$ 的，并让 $m$ 加一。会影响的只有最后 $\log$ 个位置或者一次大的进位。记录加一次数和上一位剩余值，分类讨论即可。

T3

对于 $maxa\leq 10^12$ 的部分，可以分解质因数并给每个质因数随机赋权做 hash。

但是值域非常非常大。考虑如果能有一个集合 $S={x_1,x_2\dots x_k}$，满足 $\forall i\not= j,(x_i,x_j)=1$，并且每个数都可以表示成若干个 $x$ 的乘积，那也是可行的。

考虑如何构造 $S$，增量构造，维护一个队列，每次取出队头 $x$，对于所有 $y\in S,(x,y)\not=1$，令 $d=(x,y)$，从 $S$ 中删除 $y$，加入 $\frac{y}{d}$ 和 $\frac{x}{d}$，并在队列中加入 $d$。因为每加入一个数，所有数的乘积至少除 $2$，初始乘积是 $V^n$，所以最多有 $n\log V$ 个数。依然随机赋权哈希，

Day 14

喜欢保龄。

T1

显然是从后向前做，不断合并联通块。中间的情况一定是一堆 SCC 形成了一条链，边被删去之后他可以反向，大多数情况较好维护，只需要把这个边跨过的所有点缩起来即可。但是一种情况不好做：那就是这个边连接了 $(i,i+1)$ 这两个 SCC，并且这两个 SCC 的大小都是 $1$。那此时他们两个其实是不应该缩起来的，这种情况以后处理。

但是初始是不好做的。注意到一个点 $i$ 如果有至少两个点不与他相邻，那 $i$ 和不与他相邻的所有点都要缩在一起。那先把所有之间没有连边的点缩起来，缩的大部分是对的。但是有一种情况：两个点的度数都是 $n-2$，并且他们初始不在一个 SCC 里面，并且他们之间没有可达性关系。这样他俩是不应该缩起来的。但是我们仍然可以先把他们先用并查集缩起来，然后跑一遍 tarjan。如果跑出来的结果是他俩自成一个 SCC，那暂时还是把他们看成两个点。否则他俩本来就可以缩起来，令答案减一。这个和第一段中不好处理的情况是一样做的。如果暂时还没有真正答案减一的话，那定义一个顶标，把并查集的根的权值设成 $1$。如果一旦对他进行任何操作（连接到他的边翻转或是加入别的 SCC），那就可以令答案加一。

T2

不知道。

维护 $f_{i}$ 表示 $i$ 是 $1$ 的概率，每次转移是修改 $x$ 和 $fa_x$ 两个点。

这个东西在树上是对的，因为断开之后两边就互不影响了。但是环上有问题：他们是不独立的。但是这个只有断环边的时候会有影响，所以暴力枚举断的第一条环边的两端的状态即可。复杂度 $\mathcal O(n)$。

T3

考虑 $k=0$。要求是对于所有 $i$，前 $2i-1$ 个至少选了 $i$ 个左括号。那堆维护一下即可。

考虑 $k$ 增加 $1$ 的时候，可以调整法证明，要么是括号不变，选一个位置干掉，或者是一对 () 变成了 )(，或者是一对 )( 变成了 ()，并且把他们两个之一的权值清零。

)( 变 () 没有任何条件，线段树维护分治信息即可。左括号看成加一，右括号看成减一，而 () 变 )( 需要满足，( 和 ) 之间没有出现 $0$，看成没有出现区间最小值，可以维护一万种信息。

My Friends(按换友链时间排序)