整体二分板子题。

自己还能YY点东西...

大概就是递归下去二分。

每次对于一个二分区间$[left,right]$，设中点为$mid$，那么把在$[left,mid]$范围内满足条件的询问扔到一起，把满足不了条件的询问也扔到一起，然后分别塞给$[left,mid]$区间和$[mid+1,right]$区间。

然后递归下去即可。

对于这题复杂度很显然是$O(n\log ^2 )$。

考虑二分的每一层都有$O(n)$个询问要处理，这些询问全部check一遍（使用树状数组）的复杂度是$O(n\log  n)$的。

#include

设$f(vtx,n)$表示vtx为根的子树内，到vtx距离为n的点的个数。

设$g(vtx,n)$表示vtx内，如果在vtx再接上一个长度为u的链(目标为v)就能和v形成符合题目要求的三元组的点对个数。

转移的时候枚举子节点，先统计答案，然后合并状态。

对于边$(u,v)$，能贡献的答案为$g(u,x)\times f(v,x-1)+f(u,x)\times g(v,x+1)$。

然后合并进去,$g(u,x)+=f(u,x)\times f(v,x-1)+g(v,x+1)$以及$f(u,x)+=f(v,x-1)$。

注意要先在统计答案的同时合并状态，因为我们统计的是无序三元组。

复杂度$O(n^3)$，优化一下到$O(n^2)$。

考虑长链剖分优化。

每个点的状态直接从重子节点拖过来，然后其他节点的答案参考上面暴力合并进去。

#include

直接长链剖分优化。

一个点的答案直接从他的重子节点拖过来，然后暴力合并上其他非重子节点的答案。

每条长链开个数组即可。

复杂度为所有长链的长度和，$O(n)$。

#include

把你骨灰都给你扬了！

真是送分题...可惜因为心态原因考场上想出来正解了都没敢写..

首先考虑链的情况怎么做？

既然根不是链的端点，那么这条链一定分为两部分，把两部分的所有权值扔堆里，每次各拿出来两部分的最大值进行配对，然后扔到结果里。

最后加起来即可。

推广到树上呢？

很自然的想到写个DFS，这个DFS返回一个堆，表示这棵子树的答案。

然后对于一个点把他的子节点的堆拿出来每次取出所有的最大值合并

这样也是正确的，可惜时间复杂度和空间复杂度都可以被卡到$O(n^2)$。

怎么优化呢?考虑到一个到子树内叶子节点最远距离为x的点，堆里只会有x个取值。

所以我们可以长链剖分。

对于一个点，我们优先递归它的深子节点，然后把其他的子节点的答案合并到这个深子节点的堆上。

具体实现就是对于一条长链顶，我们新建一个堆，然后这条长链都使用这一个堆。

当从长链顶返回时，合并完答案后，删除这个堆即可。

时间复杂度为所有长链长度之和乘上堆的复杂度，即$O(nlogn)$。

#include

没看题解给做出来了，说明自己还有点水平。

先考虑下前40分怎么搞一个$O(n_a\times n_b)$的算法出来。

我们可以枚举每一个B串，然后看一下这个B串是哪些A串的前缀，设以B串$b_0$为前缀的A串集合为$A(b_0)$。

我们对于每一个A串建立一个点，设第$i$个A串对应的点为$a_i$，点权为这个A串的长度。

对于一条支配关系$(x,y)$，我们把$a_x$向$A(b_y)$中的所有点连边。

最后新建一个起点，这个起点向所有的A串的点连边，然后跑以这个点为起点的最长路即可。

如果遇到环，那么这个环一定是正环(我们没有建立0权点)，就说明存在无限长的合法串。

如何判断一个$B$串是不是另一个$A$串的前缀？哈希。

复杂度$O(n_a\times n_b)$，没有任何优化的空间。

40分。

可惜在考场上我连这40分都没有。

考虑换一种思路，比如后缀数组？

搞出来串S的后缀数组，定位到一个B串是哪一个后缀的前缀，然后直接二分出来往左往右到哪个位置仍然是以这个B串为前缀，然后向这个区间内长度比这个B串长的A串连边。

直接做还是$O(n^2)$的，主席树优化建图可以搞到$O(nlogn)$。

然而我不会后缀数组

再换一种思路，比如SAM?

后缀链接树上，任何一个点表示的字符串都一定是它子树内的点表示的串的严格后缀。

然而我们现在要求出来有哪些A串是一个B串的前缀。

所以把S串翻转一下，就变成了哪些A串是一个B串的后缀了。

我们通过树上倍增的方式在后缀链接树上定位到所有的A串和B串。

一个B串被挂到了点vtx上，就说明vtx上长度不小于A的串，和vtx子节点里面的所有串，都以B为后缀。

我们再把所有的A串挂到后缀链接树上，然后对于每个A串新建一个两个点v1和v2，v2的点权为这个A串的长度，同时v1有向v2的边。

然后假设点vtx有A串被挂上去了，那么首先把vtx拆成in和out两个点，out的出边为原先vtx的出边，in的入边为原先vtx的入边，同时in向out连一条边。

对于挂在vtx上的每一个A串，我们把他们按照长度从小到大排序，设vtx上的第i个A串为$vtx_A(i)$，那么我们首先把in向$vtx_A(i).v1$连边（表示走到这个点后可以选择这个A

串），然后把$vtx_A(i).v1$向$vtx_A(i+1).v1$连边，代表选择了一个长度小的A串后，选择长度比它大的也一定合法。

然后再考虑B串，设点$vtx$上的第$i$个B串为$vtx_B(i)$，我们仍然建立点$v1$和$v1$，然后找到长度大于等于vtx_B(i)且在同一个点上的长度最小的A串$a_0$，然后从$vtx_B(i).v1$向$a_0.v1$连边，代表这个B串是这个点上长度大于等于它的A串的后缀，然后$v2$向$vtx.out$连边，代表这个B串是子树内所有A串的后缀。

然后考虑支配关系，对于一个支配关系$(a,b)$，定位到A所对应的$v2$点和b所对应的$v1$点(表示从A串a下面可以接以B串b为后缀的所有A串)，连边即可。

然后跑DAG上的最长路，如果存在环说明有无限长的合法串。

树上倍增不要写错了，注意树高的处理。

倍增的2的幂的上界为$ceil(maxdepth)$，其中maxdepth为树最深的深度，从0开始。

#include

题意

$n,q\leq 10^9,k\leq 3000$.

题解

$$ \text{枚举满足条件的天数} \\ \left( 1+Q \right) ^n\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) \frac{Q^i}{\left( 1+Q \right) ^n}\sum_{0\le j\le i}{j^k}} \\ =\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) Q^i\sum_{0\le j\le i}{j^k}} \\ \text{设}f\left( n \right) =\sum_{0\le i\le n}{i^k} \\ \text{故原式}=\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) Q^if\left( i \right)} \\ \text{将}f\left( i \right) \text{按照牛顿级数展开则有} \\ f\left( i \right) =\sum_{0\le j\le k+1}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} i\\ j\\ \end{array} \right)} \\ \text{原式}=\sum_{0\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) Q^i\sum_{0\le j\le k+1}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} i\\ j\\ \end{array} \right)}} \\ =\sum_{0\le j\le k+1}{\Delta ^jf\left( 0 \right) \sum_{j\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) \left( \begin{array}{c} i\\ j\\ \end{array} \right) Q^i}} \\ =\sum_{0\le j\le k+1}{\Delta ^jf\left( 0 \right) \sum_{j\le i\le n}{\frac{n!i!}{i!\left( n-i \right) !j!\left( i-j \right) !}Q^i}} \\ =\sum_{0\le j\le k+1}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} n\\ j\\ \end{array} \right) \sum_{j\le i\le n}{\frac{\left( n-j \right) !}{\left( n-i \right) !\left( i-j \right) !}Q^i}} \\ =\sum_{0\le j\le k+1}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} n\\ j\\ \end{array} \right) \sum_{j\le i\le n}{\left( \begin{array}{c} n-j\\ i-j\\ \end{array} \right) Q^i}} \\ =\sum_{0\le j\le k+1}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} n\\ j\\ \end{array} \right) Q^j\sum_{0\le i-j\le n-j}{\left( \begin{array}{c} n-j\\ i-j\\ \end{array} \right) Q^{i-j}}} \\ =\sum_{0\le j\le k+1}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} n\\ j\\ \end{array} \right) Q^j\sum_{0\le i\le n-j}{\left( \begin{array}{c} n-j\\ i\\ \end{array} \right) Q^i}} \\ =\sum_{0\le j\le k+1}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} n\\ j\\ \end{array} \right) Q^j\left( Q+1 \right) ^{n-j}} \\ =\sum_{0\le j\le k+1}{\frac{n^{\underline{j}}}{j!}\Delta ^jf\left( 0 \right) Q^j\left( Q+1 \right) ^{n-j}} \\ \text{由于}k\text{比较小所以暴力高阶差分即可。} \\ $$

#include

$$ \text{定义差分算子}\Delta f\left( x \right) =f\left( x+1 \right) -f\left( x \right) \\ \Delta ^kf\left( x \right) =\Delta ^{k-1}f\left( x+1 \right) -\Delta ^{k-1}f\left( x \right) \\ \text{定义算子}E,Ef\left( x \right) =Ef\left( x+1 \right) \\ \text{故}\Delta ^kf\left( x \right) =\Delta ^{k-1}Ef\left( x \right) -\Delta ^{k-1}f\left( x \right) \\ \text{除掉}\Delta ^{k-1}f\left( x \right) \text{可得} \\ \Delta =E-1 \\ \text{故}\Delta ^k=\left( E-1 \right) ^k=\sum_{0\le i\le k}{\left( \begin{array}{c} k\\ i\\ \end{array} \right) E^i\left( -1 \right) ^{k-i}} \\ \text{故}\Delta ^kf\left( x \right) =\sum_{0\le i\le k}{\left( \begin{array}{c} k\\ i\\ \end{array} \right) \left( -1 \right) ^{k-i}E^if\left( x \right)} \\ =\sum_{0\le i\le k}{\left( \begin{array}{c} k\\ i\\ \end{array} \right) \left( -1 \right) ^{k-i}f\left( x+i \right)} \\ =k!\sum_{0\le i\le k}{\frac{f\left( x+i \right)}{i!}\times \frac{\left( -1 \right) ^{k-i}}{\left( k-i \right) !}} \\ \text{所以}x\text{固定时可以通过多项式乘法在}O\left( k\log k \right) \text{的时间复杂度内计算}f\left( x \right) \text{的0到}k\text{阶差分。} \\ \text{对于}k\text{次多项式}F\left( x \right) ,\text{定义牛顿级数} \\ F\left( x \right) =\sum_{0\le i\le k}{\Delta ^iF\left( 0 \right) \left( \begin{array}{c} x\\ i\\ \end{array} \right)}=\sum_{0\le i\le k}{\Delta ^iF\left( 0 \right) \frac{x^{\underline{i}}}{i!}} \\ \text{故题目的式子} \\ Q\left( f,n,x \right) =\sum_{0\le i\le n}{\begin{array}{c} f\left( i \right) \left( \begin{array}{c} n\\ i\\ \end{array} \right) x^i\left( 1-x \right) ^{n-i}\\ \end{array}} \\ =\sum_{0\le i\le n}{\begin{array}{c} \sum_{0\le j\le i}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} i\\ j\\ \end{array} \right)}\left( \begin{array}{c} n\\ i\\ \end{array} \right) x^i\left( 1-x \right) ^{n-i}\\ \end{array}} \\ =\sum_{0\le j\le n}{\Delta ^jf\left( 0 \right) \sum_{j\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) \left( \begin{array}{c} i\\ j\\ \end{array} \right) x^i\left( 1-x \right) ^{n-i}}} \\ =\sum_{0\le j\le n}{\Delta ^jf\left( 0 \right) \sum_{j\le i\le n}{\frac{n!i!}{i!\left( n-i \right) !j!\left( n-j \right) !}x^i\left( 1-x \right) ^{n-i}}} \\ =\sum_{0\le j\le n}{\Delta ^jf\left( 0 \right) \sum_{j\le i\le n}{\frac{n!}{\left( n-i \right) !j!\left( i-j \right) !}x^i\left( 1-x \right) ^{n-i}}} \\ =\sum_{0\le j\le n}{\Delta ^jf\left( 0 \right) \frac{n!}{j!\left( n-j \right) !}\sum_{j\le i\le n}{\frac{\left( n-j \right) !}{\left( n-i \right) !\left( i-j \right) !}x^i\left( 1-x \right) ^{n-i}}} \\ =\sum_{0\le j\le n}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} n\\ j\\ \end{array} \right) \sum_{j\le i\le n}{\left( \begin{array}{c} n-j\\ i-j\\ \end{array} \right) x^i\left( 1-x \right) ^{n-i}}} \\ =\sum_{0\le j\le n}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} n\\ j\\ \end{array} \right) \sum_{j\le i+j\le n}{\left( \begin{array}{c} n-j\\ i\\ \end{array} \right) x^{i+j}\left( 1-x \right) ^{n-i-j}}} \\ =\sum_{0\le j\le n}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} n\\ j\\ \end{array} \right) x^j\sum_{0\le i\le n-j}{\left( \begin{array}{c} n-j\\ i\\ \end{array} \right) x^i\left( 1-x \right) ^{n-i-j}}} \\ =\sum_{0\le j\le n}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} n\\ j\\ \end{array} \right) x^j\left( x+\left( 1-x \right) \right) ^{n-j}} \\ =\sum_{0\le j\le n}{\Delta ^jf\left( 0 \right) \left( \begin{array}{c} n\\ j\\ \end{array} \right) x^j} \\ =\sum_{0\le j\le n}{\Delta ^jf\left( 0 \right) x^j\frac{n^{\underline{j}}}{j!}} \\ \text{对于}m\text{次多项式}f\left( x \right) ,\text{显然}\Delta ^kf\left( x \right) \text{在}k\text{超过}m\text{时为}0. \\ \text{在已知点值的情况下，我们可以使用上面的结论在}O\left( k\log k \right) \text{的时间内计算出多项式}f\left( x \right) \text{在}x=\text{0处的0到}k\text{阶差分。} \\ \text{复杂度}O\left( m\log m \right) $$

#include

$$ \sum_{1\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) i^k}=\sum_{1\le i\le n}{\begin{array}{c} \left( \begin{array}{c} n\\ i\\ \end{array} \right) \sum_{0\le j\le k}{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} i^{\underline{j}}}\\ \end{array}} \\ =\sum_{1\le i\le n}{\begin{array}{c} \left( \begin{array}{c} n\\ i\\ \end{array} \right) \sum_{0\le j\le k}{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} j!\frac{i!}{\left( i-j \right) !j!}}\\ \end{array}} \\ =\sum_{1\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right) \sum_{0\le j\le k}{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} j!\left( \begin{array}{c} i\\ j\\ \end{array} \right)}} \\ =\sum_{0\le j\le k}{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} j!\sum_{1\le i\le n}{\left( \begin{array}{c} n\\ i\\ \end{array} \right)}\left( \begin{array}{c} i\\ j\\ \end{array} \right)} \\ =\sum_{0\le j\le k}{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} j!\sum_{1\le i\le n}{\frac{n!i!}{i!\left( n-i \right) !j!\left( i-j \right) !}}} \\ =\sum_{0\le j\le k}{\begin{array}{c} \left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} j!\sum_{1\le i\le n}{\frac{n!}{\left( n-i \right) !j!\left( i-j \right) !}}\\ \end{array}} \\ =\sum_{0\le j\le k}{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} \frac{n!}{\left( n-j \right) !}\sum_{1\le i\le n}{\frac{\left( n-j \right) !}{\left( n-i \right) !\left( i-j \right) !}}} \\ =\sum_{0\le j\le k}{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} \frac{n!}{\left( n-j \right) !}\sum_{1\le i\le n,n-i\le n-j}{\left( \begin{array}{c} n-j\\ n-i\\ \end{array} \right)}} \\ =\sum_{0\le j\le k}{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} \frac{n!}{\left( n-j \right) !}\sum_{j\le i\le n}{\left( \begin{array}{c} n-j\\ i-j\\ \end{array} \right)}} \\ =\sum_{0\le j\le k}{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} \frac{n!}{\left( n-j \right) !}\sum_{j\le i+j\le n}{\left( \begin{array}{c} n-j\\ i\\ \end{array} \right)}} \\ =\sum_{0\le j\le k}{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} \frac{n!}{\left( n-j \right) !}\sum_{0\le i\le n-j}{\left( \begin{array}{c} n-j\\ i\\ \end{array} \right)}} \\ =n!\sum_{0\le j\le k}{\frac{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\}}{\left( n-j \right) !}2^{n-j}} \\ =\sum_{0\le j\le k}{\left\{ \begin{array}{c} k\\ j\\ \end{array} \right\} n^{\underline{j}}2^{n-j}} \\ \text{下降幂直接暴力计算即可。} \\ $$

#include

又是一道送分题...没救了

可能会考虑二分答案？

二分一个答案x，把大于等于x的数字设置为1，其他设置为0，然后设$f(x)$表示使得x号点为1，那么x的子树内的叶子节点至少需要几个1.

然后发现后面这个check和前面二分的x没有任何关系。

然后直接跑出来f(1)，我们就知道了要让根节点最大，我们至少需要几个1.

然后把f(1)从大到小钦定给k,k-1,k-2...1。最后一个被钦定的元素就是答案。

#include

普及题我都不会做...我还能说什么...

首先原题等价于删掉首尾后，剩下的部分是一个合法的括号序列。

所以先判掉首尾不合法。

然后从第2个元素扫到第n-2个元素，统计出空白的位置和前缀和（记左括号为1，右括号为-1）

如果前缀和为负，那么就先安排上一定数量的左括号。

如果前缀和为正，那么就先安排上一定数量的右括号。

如果前缀和为0，那么左右括号安排相等的数量。

然后我们知道了左右括号各需要多少个，从头开始扫，遇到空位优先放左括号，放完了再放右括号。

最后检查一遍是否合法即可。

#include