3.2 青岛正睿

正睿OI

---

---

http://immortalco.blog.uoj.ac/blog/2102
http://opentrains.snarknews.info/
Gym Petrozavodsk

---

Day4 PM Test

https://www.cnblogs.com/SovietPower/p/10504127.html

A.智慧树(树形DP NTT Bluestein)

根据群里$dalao$的聊天记录，瞎猜理解了一波，重新理解了一遍DFT和NTT...会记在下面（$dalao$就忽略吧）（我当时是学了些啥啊）。

---

首先$70$分是直接用$NTT$优化背包（$dp_i=\left(\prod_{v\in son_i}dp_v+1\right)\cdot x^{a_i}$）。就是每次转成点值，对应相乘，再转回去。复杂度是$O(nm\log m)$。
蒟蒻表示虽然知道能这么做，但是不明白为什么做模$m$的循环卷积，这样还是对的。重学了一下，因为我们代的是$m$次单位根，如果单位根的次数$\geq m$，就又回去了，所以点值乘的时候就是对$m$取模的。

满分做法当然是，DP的过程中不转回系数表示，直接用点值表示做。统计答案时把点值累加，最后$IDFT$回去。
转移是$dp_i(\omega_m^k)=\left(\prod_{v\in son_i}dp_v(\omega_m^k)+1\right)(\omega_m^k)^{a_i}$，那个$+1$是个常数（虽然是在系数表示下的$+1$），所以直接在点值处$+1$就可以了。
最初的正变换是$n$次单点的$DFT$，直接每次代进$m$个单位根$O(m)$转成点值表示就可以了（$A_i(\omega^k)=(\omega^k)^{a_i}$），复杂度是$O(nm)$的。
注意到$m$不是$2$的次幂，而朴素$NTT$必须将多项式长度$m$补成$2^k$，但是这样代的单位根就不是$m$次单位根了。也就是多项式长度必须是$m$。
任意长度的$DFT$需要用到$Bluestein's\ Algorithm$，下面写。

补充一点...当时学$NTT$没注意（或者忘掉）的东西。。
令$n=2^k$，那么取素数$p=r\cdot2^k+1$（满足这样形式的素数叫费马素数，朴素$NTT$必须是这样的模数，因为要存在任意$2^i\ (i\leq k)$的单位根），那么$p$存在$n$次单位根，且$\omega_n=g^{\frac{p-1}{n}}$。
注意到这题模数$p=950009857$存在原根，且$m=2^k,49152,57984$都是$p-1$的约数，所以存在对应的$m$次单位根。

然而后几个点的$m\neq2^k$，不能直接$NTT$（上面提到了），需要$Bluestein$。但是各位$dalao$说可以快速插值或者多点求值。。
学了下（也没学，就是看了下是干嘛的），大概就是，用点值DP完之后，我们可以得到$m$个点值，快速插值就可以得到原多项式的系数表示了。
注意到$IDFT$实际就是，将$m$次单位根的逆元代入点值出来的多项式，以得到原多项式的系数表示（$c_k=\frac1m\sum\limits_{i=0}^{m-1}A(\omega_m^i)(\omega_m^{-i})^k$）。
所以也可以把点值的逆元代进去，多点求值就可以了。。
然而快速插值和多点求值都巨难写，而且常数大的恐怖吧。。（这辈子是不会写的.jpg）

正变换是$O(nm)$的，中间过程只有点值相乘也是$O(nm)$的，最后每个点用$Bluestein$ $IDFT$回去是$O(m\log m)$的。

---

然后，记一下$Bluestein's\ Algorithm$，用以解决任意长度$DFT$。更多相关题目戳这。
考虑$DFT$的形式：

$$\begin{aligned}y_k&=\sum_{i=0}^{n-1}a_i\omega_n^{ki}\\&=\sum_{i=0}^{n-1}a_i\omega_{2n}^{k^2+i^2-(k-i)^2}\\&=\omega_{2n}^{k^2}\sum_{i=0}^{n-1}a_i\omega_{2n}^{i^2}\omega_{2n}^{-(k-i)^2}\end{aligned}$$

注意到$\sum$是个卷积，可以用$FFT/NTT$计算。所以$Bluestein$的复杂度是$O(n\log n)$的。
具体：$k-i$可能是负的，所以对后一项右移$n$位，令$f_i=a_i\omega_{2n}^{i^2},\ g_i=\omega_{2n}^{-(i-n)^2}$，那么$y_k=\omega_{2n}^{k^2}\sum_{i}f_ig_{n+k-i}=\omega_{2n}^{k^2}(f\times g)_{n+k}$。

$IDFT$同理，可以直接令$\omega_{2n}=\omega_{2n}^{-1}$，代到$DFT$的式子里，也可以一样的推一下：

$$\begin{aligned}c_k&=\frac{1}{n}\sum_{i=0}^{n-1}a_i\omega_n^{-ki}\\&=\frac{1}{n}\sum_{i=0}^{n-1}a_i\omega_{2n}^{k^2+i^2-(k+i)^2}\\&=\frac{1}{n}\omega_{2n}^{k^2}\sum_{i=0}^{n-1}a_i\omega_{2n}^{i^2}\omega_{2n}^{-(k+i)^2}\end{aligned}$$

令$f_i=a_i\omega_{2n}^{i^2},\ g_i=\omega_{2n}^{-(2n-1-i)^2}$，那么$c_k=\frac{1}{n}\omega_{2n}^{k^2}\sum_if_ig_{2n-1-k-i}=\omega_{2n}^{k^2}(f\times g)_{2n-1-k}$。

上面是一般的做法（其实就是个$trick$），但是$dls$指出有更好一些的做法：
像这样写成平方需要$\omega_{2n}$（有些题可能不存在$2n$次单位根），就可以用：$ij=\binom{i+j}{2}-\binom i2-\binom j2$来替换：$y_k=\omega_n^{-\binom k2}\sum_{i=0}^{n-1}a_i\omega_n^{-\binom i2}\omega_n^{\binom{i+j}{2}}$。

随便扯一句废话：$m$必须要有单位根才能做（直接$FFT$做DP 精度会爆炸）

---

最后，还有个问题是卡内存。
$DFS$的时候先$DFS$重儿子，然后父节点可以直接继承重儿子的DP数组，再$DFS$轻儿子。这样我们只需要记录当前$O(轻链个数)$个$=O(\log n)$个DP数组。

关于类似的卡内存，有一道扩展题：
给定一棵$n$个点的树，每个点有一个重量和价值，你要选一个独立集，对于每个重量$1,2,...,m$，求出其最大价值和。要求复杂度$O(n^2m)$。
先DFS轻儿子子树，再考虑父节点，再考虑重儿子...状压现在有用的点的状态...（没听懂.jpg，望dalao解答）

---

B.组合数(数位DP Lucas)

直接考虑$Lucas$：

$$\binom{n}{i_1+i_2+...}=\binom{n/p}{(i_1+i_2+...)/p}\times\binom{n\%p}{(i_1+i_2+...)\%p}$$

区间限制可以$2^n$容斥成只有上界的限制，然后就是数位DP了（虽然不明显，但是考虑是$P$进制各位独立以及$P=2$的$Subtask$应该也可以想到）。因为每进制位上是互不影响的，所以当前贡献就是乘个$\binom{n\%m}{sum\%p}$，然后处理下一位。
考虑一些简单情况：$n=2,P=2$，转移时每一位枚举两个数填什么以及是否需要进$1$的位即可。状态就记三维$0/1$：第一二个数是否卡上界、是否进位。
当$n>2$时，同样每一位枚举每个数填什么即可，上界限制直接记$2^n$的状态。
当$P>2$时，就直接对每一位记进了多少的数。有$n$个数就先递归$n$次再枚举下一位，就是很暴力的开$lim\times n\times n\times n\times2^n$的数组表示第几位、第几个数、这一位前几个数的和是多少、进了多少、上界限制。
发现像$P=2$时从高位到低位做，每次转移枚举进了多少不太靠谱，考虑从低位到高位就没这个问题了。只需要处理一下上界的状态：在低位如果有第$i$个数超过上界，令$s[i]=1$；如果在高位第$i$个数小于上界，令$s[i]=0$。最后如果所有的$s[i]=0$就是合法的（没有超上界的数）。
PS：其实也不需要"每次转移枚举进了多少"，每一位先枚举$sum$是多少，再枚举$i_1,i_2,...$填什么，这样就可以从高位往低位转移了...
复杂度...因为有个$\log_p10^{17}$，要么$P=2$要么$P=7$最劣吧...
容斥+压状态有个$4^n$，但是容斥可以去掉，压是否卡上界卡下界。可能同时卡上下界，但是这种情况是不会同时出现的...？所以去掉$0$的状态用哈希表存状态就是$3^n$的了。

注意最高位的取值$lim$要加一，因为最后是可能会再进一位的。

其实会$P=2$和$Lucas$就很好想，但是真这么暴力的吗= = 不敢写.jpg

---

C.字符串

$5.6$：离线，按$x$从小到大做。建出$SA$，$LCP\geq x$的区间会分成若干个组，把每个组的数排序，启发式合并，维护出来后，就成了对于所有相邻对$(p_i,p_{i+1})$，查询是否存在$p_i\geq l,\ p_{i+1}\leq r$。对每个$l$维护最小的$r$，求左端点在$[l,r]$内，右端点的最小值？（$r=r-x+1$）每次二维数点。。？$O(n\log^2n+q\log n)$。
笛卡尔树
某个询问区间$i$被笛卡尔树上的一个区间$j$包含，那么把$i$扩展成$j$是不会更差的（最大值不变），且$LCP$只会越来越长。
所以答案要么是笛卡尔树上的一个区间，要么是顶到询问区间，要么是一端顶到笛卡尔树区间，一段是顶到询问区间，这四种情况。
求$[l,r]$的子串中最大$LCP$是多少。二分答案求是否有$LCP[l,r-x+1]\geq x$，复杂度$O(\log^2n)$。（$O(\log n)$求区间是否有$LCP\geq x$）
对笛卡尔树上每个区间（共$n$个）预处理，复杂度是$O(n\log^2n)$。

---

Day5 AM Test

http://www.zhengruioi.com/contest/250

A.无向图

建出一棵$DFS$树，给每条非树边设一个不同的权值，树边权值为跨过它的非树边权值集合。一个边集是割集当且仅当边权异或和为$0$。
集合异或不好做。给每条非树边赋一个随机long long范围内的权值，每条边的权值就是跨过它的非树边的权值异或和。判断$10$条边中是否存在异或和为$0$的子集。线性基+高斯消元，$n^2$？
只适合边比较少的，边多的话Hash正确率会低。
正确率：$1\times(1-2^{-64})\times(1-2^{-63})\times...$（项数取决于加的边数）。

是割集当且仅当异或和为$0$。一条边是割集，当且仅当其权值为$0$。两条边是割集，当且仅当两边权值相同或一条边的权值为$0$。

---

B.线段树

考虑访问到哪些点。肯定在某个位置分成两部。先只考虑左边部分，都是某个节点的右儿子，假设第一个访问到了$i$，那下一个访问的就是$i$不停往上走碰到第一个啥...的节点的右儿子$i'$。这样$i\to i'$连一条边能形成一棵树，然后不断向上走直到越界...？
左端点$=l$，右端点$\leq r$的最大的区间，作为最初始分割的位置。
然后差分后就是求树上两条链之间的距离。。树上莫队。。

---

C.玩游戏

---

Day5 PM ACM

比赛链接。

C.Placing Medals on a Binary Tree(模拟)

本质是一个二进制的加法。可以直接用数组存，大于$10^6$的不管，其它的每次暴力进位。

---

D.Routing a Marathon Race(DFS)

$Description$
给定一张$n$个点$m$条边的无向图，每个点有一个权值。求一条从$1$到$n$的路径，使得代价最小，输出最小代价。
一条路径的代价定义为，路径上所有点以及和这些点相邻的所有点的权值和。
$n\leq40,\ m\leq\frac{n(n-1)}{2}$。
$Solution$
容易发现，如果选择从$u$走到$v$，那么一定不会再回到$u$的其它相邻节点（不如直接走过去）。
这样从点$u$爆搜的话，每次移动都会删掉$dgr_u$个点。
那么复杂度是：$T(n)=c\times T(n-c)$，最差情况下是$c=3$，复杂度约是$3^{\frac n3}$。
注意边数是$N\times N$啊不除$2$！！！（mdzz）
https://www.cnblogs.com/SovietPower/p/10573137.html

---

E.Non-redundant Drive(点分治)

$Description$
给定一棵$n$个点的树。在每个点$i$你可以补充$g_i$的油量，经过一条边需要花费边长的油量。你可以选择从任意一个点出发，任意在树上走直到油量耗尽或不能走（不能重复经过同一个点）。求最多能经过多少个点。
$n\leq10^5$。
$Solution$
点分治。对每个分治重心$rt$，求出从$rt$到子树内某个点至少需要多少初始油量、从子树内某个点到$rt$，会剩下多少油量。然后sort一下合并即可。注意不要合并来自同一棵子树内的路径，记两个来自不同子树的最大值就行了。
https://www.cnblogs.com/SovietPower/p/10576150.html

---

F.Parentheses(构造)

比着样例猜一波。

---

Day7 AM Test

A.

$x_1\neq x_2\neq x_3\to -[x_1=x_2]-[x_2=x_3]-[x_1=x_3]\\+[x_1=x_2,x_2=x_3]+[x_2=x_3,x_1=x_3]+[x_1=x_2,x_1=x_3]-[x_1=x_2,x_2=x_3,x_1=x_3]$，
...
除了$A(x)^4$都最多是三项的卷积，可以枚举三个区间容斥暴力算。
$2x_1+x_2+x_3=s$，解是$\lfloor\frac{s+1}{2}\rfloor(\lfloor\frac s2\rfloor+1)$
$x_1\in[l_1,r_1],\ x_2\in[l_2,r_2]$
$(x_1+x_2\geq l_1+l_2)-(x_1+x_3\geq l_1+r_2+1)-(x_1+x_2\geq l_1+l_1+1)+(x_1+x_2)\geq r_1+r_2+2$
$x_1+x_2+x_3+x_4=s$的非负解个数$\binom{s+3}{3}$
$\sum_{e_2\leq }$

---

B.

$dp[i][s]\times\binom ap\binom bq\to f[i-1][s-(p+q)2^i]$。
$s$的后$i$位不变；$\lfloor\frac{s}{2^{i+1}}\rfloor<a+b$。
只需要枚举$\lfloor\frac{s}{2^{i+1}}\rfloor$，是$O(k)$级别的。
预处理$p+q$，枚举$p+q$。

解不定方程的解的个数 数位dp

---

C.

---