HNOI2019
[HNOI2019]鱼
枚举(C)点，维护以(C)为端点的射线，鱼尾巴部分很好维护，考虑鱼头。
先枚举(B,D)点，设(B,D)点的中点为(K)。
那么(A,B,C,D)合法需要满足：(K)在(AC)上，(slope_{BD}*slope_{AC}=-1)。
求出(BC)的方向向量后，第二个限制很好满足，考虑第一个限制。
首先(K)要在直线(AC)上，我们知道：与一个向量点积相等的点在一条垂直其直线上。
那么得到向量(AC)的垂直向量(即向量(BD))，设为(P_1P_2)，则(P_1K)与(P_1P_2)的点积为定值。
其次(K)要在线段(AC)上，我们知道：与一个向量等距的点在一条平行于其的直线上。
所以依旧使用向量(P_1P_2)，则(P_1K)与(P_1P_2)的叉积的合法范围为一个区间，预处理后二分解决。
[HNOI2019]JOJO
用(cx)表示字符(c)连续出现(x)次，比如(aaabbaaaabbaaacc=a3 b2 a4 b2 a3 c2)。
先考虑(Sub3)(不需要可持久化)，考虑在当前串后面再接一段为(Border)的条件，显然只有第一段和最后一段可以不全。
按上述规则对用(cx)表示后的串求(kmp)，即上面的串的(next)数组为：(0 0 0 2 3 0)。
查询就是暴力跳(next)，使得新加字符的长度不断递增，贡献形如等差数列。
然后考虑可持久化，由于可以离线所以可持久化是假的，我们可以构建树形结构然后(dfs)解决。
暴跳(next)此时复杂度也假了，可以对每个字符构建(kmp)自动机，在(dfs)对其进行相应的维护即可。
[HNOI2019]多边形
仔细观察可以发现整个多边形其实是一个二叉树结构。
暴力(dp)初始解，发现变换只会对二叉树产生微小改变，直接把原贡献除掉再乘新的贡献出解。
[HNOI2019]校园旅行
对于(30\%)，设(f_{x,y})表示(x,y)之间是否合法，暴力(bfs)转移(写(dfs)的都退役了)。
对于(70\%)，改良上面算法，让两边分开转移，即设(g_{l,r,0/1})表示(l,r)之间，轮到谁转移。
考虑对于全黑边、全白边、黑白交替边各保留一棵生成树，然后再做上述算法。
这样显然有问题，考虑问题在哪里，然后修锅。
考虑两端分别走到了黑点，我们要使得两边的黑段长度相同，由于可以来回走，所以只需要使得他们奇偶性相同。
但是二分图上无论怎么走奇偶性都不会改变，所以若原图不为一个二分图，那么就在生成树上额外加一个自环。
[HNOI2019]白兔之舞
令(T)为转移矩阵，那么(Ans_t=sum_{i=0}^{L}inom{L}{i}T^i[k|i-t])
单位根反演：(Ans_t=frac{1}{k}sum_{i=0}^L inom{L}{i}T^isum_{j=0}^{k-1}w_k^{j(i-t)}=frac{1}{k}sum_{j=0}^{k-1}w_{k}^{-jt}(1+T^iw_{k}^j)^L)
令(f_j=(1+T^iw_{k}^j)^L)，则(Ans_t=frac{1}{k}sum_{j=0}^{k-1}f_j(w_k^{-t})^j)。
显然是个逆(dft)形式，所以现在我们只需要支持一个任意长度(dft)了。
由于(w_k^{ij}=w_k^{{inom{i+j}{2}}-{inom{i}{2}}-{inom{j}{2}}})。
令(delta=w_k^{-1})，则(Ans_t=frac{1}{k}sum_{j=0}^{k-1}f_jdelta^{inom{j+t}{2}-inom{j}{2}-inom{t}{2}}=frac{1}{k}delta^{-inom{t}{2}}sum_{j=0}^{k-1}(f_jdelta^{-inom{j}{2}})delta^{inom{j+t}{2}})。
来发卷积即可。垃圾出题人卡常数，注意矩乘时把(27)次取模变为(9)次取模。
[HNOI2019]序列
推推式子可以发现，对于把一段划分为一个值，这个值取平均数最优。
然后不难发现：最终方案中划分段越多，答案越优。
然后有(O(mn))的贪心做法：从前往后维护每一段中位数，当中位数非递增时则将尾部两段合并。
考虑支持快速修改，核心思想依旧是模拟上述过程。
首先正着做一遍、倒着做一遍求出前缀与后缀的答案，设为(pre,suf)。
那么假设修改(A_p)，我们的目标就是找出最终方案中(p)所在段([l,r])，答案就是(pre_{l-1}+ans_{l,r}+suf_{r+1})。
首先考虑固定一个右端点(r)，如何求左端点的落点(l)。
设当前段平均数为(m_1)，新来的左边段的平均数为(m_2)。
若(m_2>m_1)，则两段需合并在一起，(m_1')与更前方平均数的差距缩小，否则就不需要并在一起。
故这个左端点(l)可以直接二分。
然后考虑如何求出正确的右端点，同样二分，(check)当前段与之后一段的平均数大小关系即可。
ZJOI2019
[ZJOI2019]麻将
麻将形态的(DP)现在已经麻木了。先考虑给一副牌判断能不能胡。
设(f_{i,a,b,0/1})表示前(i)各花色，(E_{i-1,i,i+1})有(a)个顺子，(E_{i,i+1,i+2})有(b)个顺子，是否有对子 的 最大面数。
转移暴力就完事了。
爆搜一下发现(f)状态数很少，所以(dp)套(dp)。
设(g_{i,j,F})表示前(i)种花色拿了(j)张牌，(f)走到状态(F)的不胡方案数，转移大暴力。
答案(Ans=frac{sum_{j=0}^{4n-13}g_{j}j!(4n-13-j)!}{(4n-13)!})，注意(f)转移时记得把选牌方案的组合数算上。
[ZJOI2019]线段树
考虑一个操作(1)对所有线段树的影响，设((f_i,g_i))分别表示(i)点有(tag)、(1 o i)有(tag)的概率。
那么设区间([l,r])在线段树对应路径(P)。
分(P)上(不包括端点)、端点(l,r)、(l,r)子树内(不包括(l,r))、路径(P)侧链、其它共五类点进行讨论即可。
[ZJOI2019]Minimax搜索
把答案做前缀和，求(w(S)leq k)的方案数，最后再差分求解。
设初始状态下(1)号节点的权值为(w)。
若我们要使得(w'>w)，则只需要修改(val<w)的点。使得(w'<w)的方案同理。
我们只需要让上述两种方案的一种成立即可，所以不妨容斥，算两种方案都不成立的方案数。
以修改(val<w)的点的方案数为例。
设(f_u)表示(u)点(< w)的方案数，这里直接改设(f_u)为概率方便计算。
对于奇数层，(f_u=prod f_v)。对于偶数层，(f_v=1-prod(1-f_v))，总复杂度为(O(n^2))。
一个比较妙的转化：令(g_u=[dep_u is odd]f_u + [dep_u is even](1-f_u))。
则转移统一为：(g_u=prod_v (1-g_v))。
注意到(k)每增加(1)，至多只会有两个点的(g)发生变化，所以动态(dp)即可。
注意到：(g_t=prod_{i=1}^t (1-g_{p_i})=c_{p_1}prod_{i=1}^t(1-g_{p_{i-1}})......)。
暴力展开后会发现：(g_t=prod_{i=1}^t(1-g_{p_i})=g_{[l,m]}+(-1)^{m-l+1}g_{[l,m]}g_{[m+1,t]})，线段树直接维护。
[ZJOI2019]语言
考虑对每个点开一棵线段树，直接维护该点的可达点是哪些。
对于一次修改，设(S)表示修改的点集，那么我们就是要给(S)中的每一棵线段树加上(S)这个集合。
树上差分后线段树合并即可。
具体来说线段树中维护(>0)的值的个数，不难发现这个东西是支持线段树合并的。
[ZJOI2019]开关
考虑求出概率生成函数(f(x)=sum_{i=0}^{infty} E(X=i)x^i)，那么答案就是(F(1)')。
对于要按奇数次的点(i)，构造(H_{i}(x)=frac{e^{frac{p_i}{P}}-e^{frac{-p_i}{P}}}{2})，
同理对于要按偶数次的点(i)，构造(H_{i}(x)=frac{e^{frac{p_i}{P}}+e^{frac{-p_i}{P}}}{2})。
那么(H(x)=prod_{i=1}^n H_i(x))，但这不能保证第一次结束时就停止，所以令(G(x)=prod_{i=1}^n(frac{e^{frac{p_i}{P}}+e^{frac{-p_i}{P}}}{2}))。
那么令(F(x))为(f(x))的指数型生成函数，则(F(x)G(x)=H(x))，即(F(x)=frac{H(x)}{G(x)})。
令(h(x))、(g(x))分别为(H(x))、(G(x))的概率生成函数，则(f(x)=frac{h(x)}{g(x)})，即(f(1)'=frac{h'(1)g(1)-h(1)g(1)'}{g(1)^2})。
以求(g(1),g(1)')为例，设(G(x)=sum_{i=-P}^P a_ie^{frac{i}{P}x})。
那么(G(x)=sum_{i=-P}^P a_isum_{j=0}^{infty}frac{({frac{i}{P}}x)^j}{j!})，故(g(x)=sum_{i=-P}^Pfrac{a_i}{1-{frac{i}{P}}x})。
一个大问题在于，当(i=P)时，(g(x))在(x=1)处不收敛。但不难发现，(g(x),h(x))同乘(prod_{i=-P}^P(1-{frac{i}{P}}x))后答案不变，设为(g_2(x),h_2(x))。
那么(g_2(x)=sum_{i=-P}^P a_iprod_{j=-P,j
eq i}^P (1-{frac{j}{P}}x))。
(g_2(1))很好求，关键看(g_2(1)')怎么求。
首先暴力展开后有([prod_{i=1}^n (1-c_ix)]'=sum_{i=1}^n(-c_i)prod_{j
eq i} (1-c_jx))。
所以(g_2(1)'=sum_{i=-P}^P a_isum_{j=-P,j
eq i}^P (-frac{j}{P}) prod_{k
eq j,k
eq i} (1-frac{k}{P}x))，当(x=1)时，只有(j=P)或(i=P)有意义，故(g_2(1)')可快速求。
BJOI2019
[BJOI2019]奥术神杖
把答案取个对数，那么几何平均数就变成了算术平均数。
然后就是愉快的分数规划后(AC)自动机上(dp)。
[BJOI2019]勘破神机
对于(m=2)，就是(Fib)数列。对于(m=3)，打表可得递推式：(f_{2n}=4f_{2n-2}-f_{2n-4})。
问题变为求(sum_{i=1}^n inom{f(i)}{k})。
做一些简单的变形：(sum_{i=1}^n inom{f(i)}{k}=sum_{i=1}^n frac{P(f(i),k)}{k!}=sum_{i=1}^n frac{sum_{j=0}^k S(k,j)(-1)^{k-j}f(i)^j}{k!})。
交换求和顺序后，只用求(sum_{i=1}^n f(i)^t)即可。
构造(f(i))母函数，可以得到通向公式：(f(n)=AC^n+BD^n)。
那么(sum_{i=1}^nf(i)^t=sum_{i=1}^n (AC^i+BD^i)^t=sum_{i=1}^n sum_{j=0}^t inom{t}{j}(AC^i)^j(BD^i)^{j-t})，交换(sum)后可得等比数列。
注意几个细节：((1))(3,5)在给定模数下无二次剩余，故需要扩系。 ((2))特判等比数列(q=1)的情况。
[BJOI2019]删数
对于数(k(kleq n))，若有(c_k)个，则称存在区间([k-c_k+1,k])。最后([1,n])未覆盖长度即为答案。
考虑增加了全局加减后如何维护上述答案。
可以通过平移区间([1,n])来实现，由于只有(kleq n)的限制且每次只移动(1)格，所以顺带维护即可。
[北京集训2019]图的难题
一张图(<V,E>)合法当且仅当它的任意导出子图(<V',E'>)满足(|E'|leq 2|V'|-2)。
那么非法即：(|E'|-2|V'|>-2)。
左边是最大权闭合子图形式，上个网络流求一下(max)。
[北京集训2019]生成树计数
设生成树权值和(Val=sum_{i=1}^n val_i)，那么(Val^k=(sum_{i=1}^n val_i)^k=k!sum_{k=sum_{i=1}^nc_i}frac{val_i^{c_i}}{c_i!})。
用变元矩阵树定理，每条边的权值变为多项式(sum_{j=0}^{k} frac{val^k}{k!})，那么答案就是(k![x^k])。
其中除法可以写(O(k^2))的多项式求逆。
[北京集训2019]完美塔防
首先判掉炮台打炮台的不合法方向。
其次每个空地只会被两个不同方向进入的炮台打到，因为光路可逆，同方向进入的炮台会互打。
剩下的就是(2-sat)裸题了。
十二省联考2019
[十二省联考2019]字符串问题
限制倒过来看就是：把(A,B)串反过来，(A_{i+1})存在一个后缀(B)，满足(B)被(A_i)支配。
后缀的话就可以考虑建后缀自动机然后跳(parent)树了。
把(A,B)的反串一起建后缀自动机，然后把(A,B)都挂到(parent)树上，其中(A o Tree,Tree o B,B o A)。
最后形成了一个(DAG)，拓扑序(dp)求最长路。
[十二省联考2019]春节十二响
先考虑合并两条链，显然是按照大小关系从大往小合并最优。
一棵树并没有什么变化。
[十二省联考2019]骗分过样例
子任务(1sim 3)直接输出(19^x)，记得(x)对(varphi(mod))取模。
子任务(4)，发现模数在(10^6)数量级，暴力枚举得到(mod=1145141)后转(Task_{1sim 3})。
子任务(5)，
排序后可以找到两个(x)只相差(2)的结果，设为(a_0,a_2)，那么(mod|(19^2a_0-a_2))。
先用(int128)存(19^2a_0-a_2)，枚举其约数得(mod=5211600617818708273)，然后转(Task_{1sim 3})。
子任务(6sim 7)，由于某些原因发现(19^x)爆(int)竟然存在循环节？然后暴力就行了。
子任务(8sim 10)，判素数，用(Miller)算法暴力。
子任务(11sim 13)，求(mu)。
先筛出(n^{frac{1}{3}})以内的素数，把这些素数的贡献暴力判掉。
那么剩下的数无非三种情况：(p,pq,p^2)。(p^2)很好判，(p)用(Miller)算法判，剩下的就是(pq)。
子任务(14)，暴力判是否为原根。
子任务(15)，任务同子任务(14)，但区间变大，模数变小。
首先找一个原根(比如(g_0=6))，然后把(xin [1,mod))表示为(g_0^y)。
考虑(x)不为原根的条件：存在(q|mod-1)，满足(x^{frac{mod-1}{q}}=g_0^{yfrac{mod-1}{q}}equiv 1)，即(q|y)。
所以若(x=g_0^y)是(mod)的一个原根，则(yperp (mod-1))，把(q)筛出来后暴力。
子任务(16)，坚信出题人会卡你，所以在(1.5*10^9)附近暴力，得到(mod=1515343657)，转(Task_{13})。
[十二省联考2019]皮配
学校可以分为三类：(k)所特殊学校，与特殊学校同城市的学校，其它。
对于第三类，派系与阵营之间互不影响，分别(O(n^2))进行(dp)即可。
对于第二类，我们可以把他们对阵营的贡献加到第一类上，然后对派系做(O(n^2))的(dp)。
对于第一类，按照城市分层，暴力做(O(kM^2))的不满(dp)。
最后做前缀和，然后把上述三类学校的答案合并即可。
[十二省联考2019]希望
题目大意：在树上求(K)个联通块，这(K)个联通块存在交(T)，且存在点(v)到(K)个联通块的并的最远距离不超过(L)。
考虑枚举(K)个联通块的并，然后就可以套一个经典容斥：点(-)边容斥了。
我们以计算包含某个点(u)的方案数为例。
设(f_{u,j})表示子树合并到(u)点，子树内最远距离不超过(j)的方案数+1，那么(f_{u,j}=1+prod_v f_{v,j-1})。
设(g_{u,j})表示子树外(但包括(u)点)最远距离不超过(j)的方案数，换根(dp)，转移(g_{v,j}=1+g_{u,j-1} prod_{t
eq v,tin son(u)} f_{t,j-2})
考虑优化，(f)是一个比较显然的长链剖分，关键还是看(g)。
依旧考虑长链剖分，对于重链，暴力把轻链的(f)合并即可。
对于轻链，注意到我们最终只需要使用(g_{u,L})与(g_{u,L-1})，
设(v)子树内的最远点深度为(d)，则(dp)的第二维我们只会用到([L-d,L])，故可以只转移这部分。
而这部分的深度依旧是轻链深度，所以总枚举长度依旧会是线性。
然后来解决前后缀(f)之积的问题，注意到转移与(f)的转移很像，所以我们可以按照(f)逆序转移(g)。
这样对(f)数组进行撤销操作得到前缀，同时在转移的过程中维护后缀，从而避免了可持久化。
注意到：当(v)转移到(u)，且(v)的深度不及(L-1)时，我们要支持后缀乘法。除此之外我们还要支持全局加法。
可以通过打标记的方式实现，维护全局标记((a,b))表示(x o (ax+b))即可。
还有一个特别恶心的地方在于由于转移中存在(+1)，所以(f,g)可能会变成(0)，即可能出现后缀乘(0)。
所以再额外维护一个标记(cov)表示([cov,L])的(f/g)都是(0)，转移时顺带移动(cov)标记即可。
把逆元线性处理了，复杂度可以做到严格(O(n))。
细节(N)多警告，真(TM)难调。
GXOI2019
[GXOI2019]旅行者
关键点生成树，从起点与终点分别跑(Dij)，对每个点记录它的最近归属起点、终点。
然后枚举边，把路径拼起来更新答案。
[GXOI2019]特技飞行
令人发指的二合一。关于(c)的计算，旋转坐标系后二维数点。
关于(a,b)的计算，我们可以抽象出一个模型：
有一列带标号小球，每次可以选择交换两个球或不交换，这两种操作分别有收益(a,b)，要求最后排列不变，求最少步数。
我们首先假设都交换，得到排列(P_2)，我们可以用(b-a)的代价使得排列中两个位置((x,y))交换，问变回原排列的最少步数。
从前往后做，每次只交换实际位在枚举位前的点，从增量的角度看，会发现每一步的交换必定可以交换，所以模拟就好了。
SNOI2019
[SNOI2019]数论
枚举(a_i)，那么就是要统计((a_i+kA)\% Bin {S_B})的(k)的个数。
我们知道，步长为(A)的移动在模(B)意义下会形成(gcd(A,B))个环，所以直接把每个环的前缀和做出来。
[SNOI2019]通信
把通信站拆点，然后网络流模型比较显然。
考虑优化连边，注意到我们是给前缀连边，所以可以(cdq)分治，内部把左侧通讯站排序然后前缀连边。
TJOI2019
[TJOI2019]甲苯先生的滚榜
好久没写(Treap)了刚好写一下。
[TJOI2019]唱、跳、rap和篮球
容斥有几个非法：(Ans=sum_{j=0}^{lfloor frac{n}{4}
floor} (-1)^j inom{n-3j}{j}F(j))
其中(F(j))就是(4)个指数形生成函数的卷积，用(ntt)优化。
[TJOI2019]甲苯先生的线段树
第一问相当的简单，设答案为(S)。
考虑第二问，直观想法：枚举(lca)深度(d_1)，两个端点深度(d_a,d_b)。
但是不难发现，若(d_1<d_a,d_b)，则(lca)段对值的影响绝对大于后半段的影响。
所以枚举(d_a,d_b)后，(lca)其实唯一确定。问题转化为：求两个长度为(a',b')的数，使得两者计算值之和为(S')。
设两个数的和为(Sum)，则易得他们的计算值(Calc(Sum)=2Sum-popcount(Sun)=S')。
不妨枚举(popcount)，设(f_{i,j,0/1})表示从低到高做了(i)位，放了(j)个(1)，当且位是否被进位，暴力转移即可。
复杂度为相当不满的(O(d^5))。
JSOI2019
[JSOI2019]精准预测
设(S_{x,t})表示居民(x)在(t)时刻还存活的状态，设(D_{x,t})表示死了的状态。
(2-sat)的模型应该还是比较清晰的：
对于(0,t,x,y)：(D_{x,t} o D_{y,t+1})，(S_{y,t+1} o S_{x,t})。对于(1,t,x,y)：(S_{x,t} o D_{y,t})、(S_{y,t} o D_{x,t})。
除此之外，还有：(D_{x,t} o D_{x,t+1})、(S_{x,t} o S_{x,t-1})两种边要编满。
显然我们可以只把与(x)有关的时刻拿出来，其它的点丢弃，然后前缀连边，这样点数就优化到了(2(n+m))。
不难发现这是一个(DAG)，故(x)的答案个数为：(S_{x,t+1})不能到达(D_{y,t+1})、且(S_{y,t+1})不能到达(D_{y,t+1})的(y)的个数。
拿个(bitset)拓扑排序。空间太小就分几批处理。
[JSOI2019]神经网络
令人发指的二合一。
首先对每棵树求把它划分为(j)条链(注意：首尾异构，若链长>1则方案数要乘二)的方案数。
设(f_{u,j,0/1})表示昨晚(u)子树内，已有(j)条链，当前点是否向上延伸的方案数。首尾异构的乘二可以在链的最高点计算。
设第(i)棵树划分为(j)条链的方案数为(val_{i,j})
其次是把枚举每棵树划分为多少段，求把这若干条链拼接在一起，且同色不相临的方案数。
有标号的环计数考虑破环为链，然后钦定一棵特殊的树放在开头，若这棵树分为(l)条链，则方案数为求出值除(l)。
容斥，用多项式完成排列组合。
对于非特殊树，构建指数形生成函数：(F_i(x)=sum_{j=1}^{sz_i} val_{i,j}sum_{k=1}^{j}(-1)^{j-k}inom{j-1}{j-k}frac{x^k}{k!})。
对于开头的特殊树，注意这里还需要一个容斥来处理首尾相同。
先求总方案，再减首尾相同的方案，故生成函数为：(E_i(x)=sum_{j=1}^{sz_i}frac{val_{i,j}}{j}sum_{k=1}^j(-1)^{j-k}inom{j-1}{k-1}(frac{x^{k-1}}{(k-1)!}-frac{[j>1]x^{k-2}}{(k-2)!}))。
全部卷起，系数之和来就是答案。
[JSOI2019]节日庆典
一个位置(p)要是最小循环的开头，则([p,n])需要满足：在当前串后面接一个串(t)后，能够成为最小后缀。
然后就舒服了，我们知道，这样的位置不会超过(logn)个。
再证一遍，设有两个备选后缀(a,b)，其中(|a|>|b|>lfloor frac{|a|}{2}
floor)。
那么首先(b)要是(a)的一个(border)，有(|b|>lfloor frac{|a|}{2}
floor)，所以(a)一定存在一个周期(cw)。
我们不妨令(a=cwcwc,b=cwc)。
那么(at=cwcwct,bt=cwct)。因为(ct>cwct)，所以(t>w)。故(cwcwct<cwct)，即(at<bt)，故(b)一定不合法。
我们现在就只需要暴力维护这(logn)个备选集合就好了。
不难发现，所有维护、查询过程中的(lcp)求解都为(lcp(1,i))，故用(Z-Algorithm)预处理(lcp(1,1sim n))即可。
[SDOI2019]
[SDOI2019]热闹又尴尬的聚会
首先，度数最小的点在删点后度数不会变大。
所以很容易得到第一问的做法：不断删除当前度数最小的点，每删一个点就更新一次答案。设最终答案为(p)。
注意到这个过程中，每次取出的点度数不会超过(p)。
所以我们每次取出一个点，就把相邻点删掉，这样每次删掉点的个数不超过(p+1)，最终点数满足(qge lfloor frac{n}{p+1}
floor)。
[SDOI2019]移动金币
我们把两个金币之间的距离看作一堆石子，经过一定转化后问题变为：
有(m)堆石子，石子之和不超过(n)，博弈规则如下：每次可以从第(i)堆中取(t>0)个石子，然后把这(t)个式子放入第(i-1)堆。
其中当(i=1)时取出的石子被丢弃，不能操作者败。
不难发现这其实是一个阶梯博弈，我们知道：阶梯博弈先手必胜的条件为：奇数层石子数异或和为(0)。
容斥，我们转求先手必败的方案数。
考虑拆位，我们枚举每一位到底有几个(1)，那么当且经当每一位(1)的个数都为偶数时，先手必败。
即对于每一个二进制位(e)，构造生成函数(F_e(x)=sum_{i=0}^{m}inom{m}{i}[i\%2=0]x^{2^ei})，直接暴力卷积。
[SDOI2019]连续子序列
(TMD)这种题出在考场上谁做的出来啊？
根据(OEIS)，这个数列有这样一种神奇的生成方式：从({0})开始，每次(0 o 01,1 o 10)。
那么我们可以根据逆运算(01 o 0,10 o 1)缩小序列的规模。同时有结论：对于长度(>3)的序列，只有唯一合法缩小方案。
然后我们就可以记搜了，记搜的每一层，我们对当前串(SK)枚举缩小方案(划分方案)，当长度(leq 3)的时候特判出解。
[SDOI2019]世界地图
设(T_{[l,r]})表示只考虑区间([l,r])的点和边时的最小生成树。
假设询问([l,r])，此时我们已经知道了(T_{[1,l-1]})和(T_{[r+1,n]})，现在要加入(1sim n)的一列边，然后求最小生成树。
每加入一条边，必定就会删掉一条边(第一条除外)，考虑删掉的边的位置。
不难发现，为在(T_{[1,l-1]})中是第(1)列点路径的并，在(T_{[r+1,n]})中是第(n)列点路径的并，其实就是虚树。
所以我们其实不用维护(T_{[1,l-1]})，只需要维护以第(1)列的点为关键点的虚树，其中虚树边权是路径上的最大边权。
每次询问，把两棵虚树以及(1sim n)的边拿出来跑最小生成树即可。
如何求上述虚树？其实是一样的，对于(T_{[1,i]})维护以第(1)列、第(i)列为关键点的虚树，则第(i)列的答案从第(i-1)列转移即可。