Day 1
T1
感觉能做。
首先考虑给定了一个序列如何判是否合法。如果确定了三种子序列分别的出现次数，暴力 DP 是记录 A,B,C,AB,BC,CA 的出现次数的方案是否合法。
从前向后扫 $s$ 串，如果当前出现了一个字符 A，他可以单独成一个新的序列，可以拼到 C 上，也可以拼到 BC 上。
感性理解就是因为三个串是循环同构的，考虑如果新成一个序列，他后面还要接 B,C，拼到 C 上面还需要接一个 B，拼到 BC 上面后面就没有限制了。
显然单独成串严格强于拼到 C 上严格强于拼到 BC 上。因为所有条件最终都需要满足，所以考虑先满足严格的条件一定不劣。理性理解可以通过邻项交换来证明决策包容性。
这样就有贪心：确定了三种子序列的出现次数后，新出现的字符尽量单独成段，其次尽量拼到一个字符上，再次才是拼到两个字符上。设 $x_{0/1/2}$ 表示三种字符当前出现次数，$X_{0/1/2}$ 表示三种字符的上界，可以推出序列合法的充要条件就是保证时时刻刻 $x_i-X_i\leq x_{i+2\bmod 3}$。
一个串可能有多种合法的子序列划分方式。考虑容斥，钦定一些可选方案必须满足。设 $S$ 表示钦定 $x\in S$ 个 ABC 需要满足，$T$ 表示钦定 $y\in T$ 个 BCA 需要满足，则限制可以变为：
容斥系数是 $(-1)^{\lvert S\rvert+\lvert T\rvert}$。容易发现只和 $S,T$ 中的最大，最小值有关。并且考虑对于一对 $x$ 的最小，最大值 $(x,y)$，如果 $x,y$ 中间还有可选方案，则所有 $S$ 的容斥系数之和为 $0$，所以只需要考虑两个相邻的可选方案。选单独一个的容斥系数是 $1$，选相邻两个的容斥系数是 $-1$。对于 $y$ 也同理，这样只需要做 $\mathcal O(n^2)$ 次计算方案数，而计算方案数可以用一个简单的 $\mathcal O(n^3)$ DP 解决。注意常数优化。
上面的容斥也是点减边，因为合法的取值都是一段区间，但是直接发现是一段区间可能不是那么的明显（可能也比较明显，本身就是关乎最大最小值的限制）。
T2
做不了一点。
生成方式等价于 $p_i=\mathrm{popcount}(i)\bmod 2$，也等价于 $P_k=P_{k-1}+\mathrm{flip}(P_{k-1})$，其中 $P_k$ 表示生成 $k$ 步的 $P$ 序列，加号是字符串拼接，$\mathrm{flip}$ 是翻转。
首先有 $\mathrm{flip}(S_i)=\mathrm{rev}(S_i)$，可以简单归纳证明。
性质 $1$：$01$ 序列 $S$ 合法的充要条件是存在一个位置 $p$，使得 $\mathrm{rev}(S[1\dots k])$ 是 $P$ 串或者 $\mathrm{flip}(P)$ 的前缀，$S[k+1\dots n]$ 也是 $P$ 串或者 $\mathrm{filp}(P)$ 的前缀。
必要性显然。充分性：对于一个充分长的 $S_k$，设 $S’_k$ 表示 $\mathrm{rev}(S_k)$，则有以下结构在 $P$ 中存在：
\[S_k,S'_k,S'_k,S_k,S'_k,S_k,S_k,S'_k\]取第一个和第二个，前后缀分别是 $P’$ 和 $P’$。取第二个和第三个，前后缀分别是 $P$ 和 $P’$。取第四个和第五个，前后缀分别是 $P$ 和 $P$。取第五个和第六个，前后缀分别是 $P’$ 和 $P$。所以上述条件是序列合法的充要条件。
对原序列直接通过这个进行计数会有问题，因为一个序列可能会有多个合法的拆分方式。考虑如何处理算重的情况。下面开始展示魔法了。。。
性质 $2$：串 $S$ 如果既是 $P$ 的前缀，$\mathrm{rev}(S)$ 是 $P’$ 的前缀，则 $S$ 的长度为 $2$ 的次幂。
这谁想的到啊。。
设 $w(i)$ 表示 $i$ 中 $1$ 的个数的奇偶性。反证法，假设存在 $\lvert S\rvert \not = 2^k$，首先有 $S_i=x\oplus w(i)=y\oplus w(\lvert S\rvert -1-i)$，其中 $x,y\in\{0,1\}$。所以 $\forall i\in[0,\lvert S\rvert-1],w(i)\oplus w(\lvert S\rvert -1-i)=w(\lvert S\rvert-1)$。
因为 $\lvert S\rvert-1\not = 2^k-1$，所以一定存在一个位置满足 $\mathrm{bit}k(\lvert S\rvert-1)=0,\mathrm{bit}{k+1}(\lvert S\rvert-1)=1$。
所以 $w(\lvert S\rvert -1)=w(2^k)\oplus w(\lvert S\rvert -1-2^k)=1\oplus w(\lvert S\rvert -1)$（考虑 $\lvert S\rvert -1$ 消去了一个 $1$，又出现了一个 $1$）。与原命题不符，假设不成立。
性质 $3$：一个串最多有两种拆分方式。
首先考虑有两种拆分方式，假设 $S$ 可以被拆成 $[A+B][C]$ 和 $[A][B+C]$，因为 $B$ 和 $\mathrm{rev}(B)$ 同时是 $P$ 或 $P’$ 的前缀，所以 $\lvert B\rvert =2^k$。
反证法，假设一个串有三种拆分方式，$[A+B+C][D],[A+B][C+D],[A][B+C+D]$，则 $\lvert B\rvert ,\lvert C\rvert ,\lvert B+C\rvert $ 都应当为 $2$ 的次幂，所以 $\lvert B\rvert =\lvert C\rvert$。
观察 $P$ 的生成方式，可以得到 $C_0=B_0\oplus 1,D_0=C_0\oplus 1,D_0=B_0\oplus 1$，假设不成立。
现在要算的就是所有拆分方式的串数量之和减去有两种拆分方式的串。
设 $pre_{i,0/1},nex_{i,0/1}$ 表示从 $i$ 开始和 $P$ 与 $P’$ 进行匹配最远向前，向后匹配到哪里。这个可以倍增预处理。这样枚举位置 $i$，算拆分方式的串数量之和可以看成一个二维矩形加。
对于有两种拆分方式的串，先枚举 $2^k$ 的区间长度以及区间的位置 $[l,r]$。考虑长度为 $2^k$ 的串 $S$，现在要求一个 $T$，满足 $S$ 是 $T$ 的前缀，并且 $T$ 和删去前缀 $S$ 的 $T$ 都在 $P$ 或 $P’$ 中出现。$S$ 在 $P$ 中的出现应当是 $S,S’,S’\dots$ 这样 $T$ 删掉 $S$ 前缀之后最多还有 $\lvert S\rvert$ 的合法长度，所以只需要求 $\max(pre_r,l-2^k)$ 和 $\min(nex_l,r+2^k)$ 作为矩形加的左右端点即可。
这样问题转化为了有 $\mathcal O(n\log n)$ 次矩形加，多次查询：
\[\sum_{l\leq l'\leq r'\leq r}c_{l',r'}p_{l,l'-1}p_{r'+1,r}\]$p$ 的贡献就是问号带来的方案数，可以差分处理，所以可以转化成矩形 $a_{i,j}\overset +\leftarrow b_{i,j}$，矩形求和 $b_{i,j}$，可以用线段树维护矩阵解决，复杂度 $\mathcal O(n\log^2 n+q\log n)$。
T3
限制是对于一列需要先填完所有 $A_{i,j}=0$ 的位置，才能填 $A_{i,j}=1$ 的位置。对于一行则相反。
如果一步中填了 $B_{i,j}$，如果 $A_{i,j}=1$，也需要填同一列中 $A_{i,j}=0$ 的位置。如果 $A_{i,j}=0$ 则需要填同一行中 $A_{i,j}=1$ 的位置。这样连边之后就是求图中 SCC 的数量。
Day 2
T1
sub5
考虑一条 $1$ 到 $n$ 的经过若干个环的路径，长度为 $l$。假设环长分别为 $a_1,a_2\dots a_k$，则当时间充分大的时候，由裴蜀定理得这个路径对点 $n$ 的贡献就是在 $l+x\gcd\{a_1,a_2\dots a_k\}$ 的时候亮起。
设 $f_{i,j,k}$ 表示是否存在路径，当前走到了 $i$，经过的环长的 $\gcd$ 是 $j$，路径长度 $\bmod j$ 是 $k$。可以通过两次记忆化搜索求出：先求出 $f’_{i,j,k}$ 表示路径长度 $\bmod j=k$ 是否合法，搜的时候走到一个环长不为 $0$ 的点就停下。然后从每个长度不为 $0$ 的环开始继续更新。
这样得到了点 $n$ 的 $f_{i,j}$ 之后问题就转化成了一个数论问题：给定若干个模数，要求 $x$ 模这些数意义下的取值在一个集合里，求 $x$ 的结构。
把每一个 $i$ 对应的 $f_{i,j}$ 数组复制无限份取 or 之后就是答案序列，即 $1$ 的位置是 $x$ 的合法取值。取 or 可以转化为取反之后取 and。以下的 $f$ 和答案序列都是取反意义后的。
考虑 $f_{i,j}$ 的一位 $j$，其取值是 $1$。如果存在一个 $t$ 满足答案序列的第 $ti+j$ 位是 $1$ 则这个位是有贡献的。因为所有环长都互质，所以每一个是 $1$ 的位都是有贡献的。
考虑对每个串进行压缩操作，即找到他的最小循环元 $d\vert i$，把他和 $f_d$ 取交后就可以把 $f_i$ 扔掉了。
此时有结论，答案就是压缩完成后所有没被删掉的串的串长的最小公倍数。
证明：显然答案一定是求出来的最小公倍数的因子。使用反证法，假设最小公倍数是 $K$，答案是 $K’\vert K$，因为 $K$ 是所有 $b_i$ 的最小公倍数，所以一定存在一个 $b_i\vert K’$ 不成立。而对于这个 $b_i$，因为已经把他压缩到了最小并且其每一位都是有贡献的。因此 $\forall j,f_{b_i,j}=f_{b_i,(j+K’)\bmod b_i}$。这会把 $f_{b_i}$ 分成 $\frac{b_i}{\gcd(K’,b_i)}$ 个环。而环数不为 $1$ 的话就可以对 $f_{b_i}$ 再进行一次压缩操作，与假设不符。
sub6
此时环要么互质，要么互为倍数关系。考虑如果把所有串为 $1$ 但是无效的位删去之后，就可以套用上面的分析求出答案。互质的环之间不会造成串的某个位置无效，所以只需要考虑因子对这个数的贡献。把 $b\vert a$ 的串 $f_b$ 复制 $\frac a b$ 次之后和 $a$ 取一个 and，就可以删去所有无效的位。经过上述操作之后再用 sub5 的方式求出答案即可。
正解
对于一个 SCC，关心的是其环长的 $\gcd$，这是经典问题：求出一个 dfs 树，求出树上深度，则环长的 $\gcd$ 就是对于每条非树边 $(u,v,w)$，$d_u-d_v+w$ 的 $\gcd$。这样还是可以求出来点 $n$ 的 $f_{i,j}$。
再考虑不互质的时候如何删去无效位。最暴力的方式是枚举 $\mathrm{lcm}(1,2,3\dots 100)$ 内的所有数字 $r$，对每一位是否有效进行检查。
核心的思想就是把所有环长变得互质。进行根号分治，因为一个数只会有一个 $>10$ 的质因数。设 $T=2^5\times 3^3\times 5\times 7$，枚举 $x\bmod T$ 的结果，此时 $x=r+Ty$，而 $p\in S,r+Ty\equiv p\pmod M$ 也可以转化为一个关于 $y$ 的，$\bmod \frac{M}{\gcd(M,T)}$ 意义下的同余方程。注意到 $\frac{M}{\gcd(M,T)}$ 要么是质数，要么是 $1$，因此就是需要把模数相同的方程的集合放在同一类取 and，如果全都非空则合法。
合法了之后就可以贡献到所有 $r+Ty\bmod M$ 的位上，标记他们为有效，再套用 sub5 的做法即可。
更快一点的做法：注意到互为倍数的模数的同余方程组也是可以求解的，所以可以取 $T=2^3\times 3^2\times 5\times 7=2520$，互为倍数的限制就是把 $a\vert b$ 的 $a$ 的串复制若干遍和 $b$ 取交，然后就还是和上面一样了。可以做到 $\mathcal O((n+m)V^2+TV^2)$。
T2
比较唐啊。
首先序列上已经是经典根号问题了。直接想根号算法。
经过尝试，对第二棵树树分块，把询问拆成四个根链询问，修改看成四个根链修改。询问的时候先把这个点到上面第一个关键点的散点暴力查答案。查答案可以看成是查子树和，可以用一个支持 $\mathcal O(\sqrt n)$ 单点加，$\mathcal O(1)$ 区间查询的分块来支持这一部分。
对于查询的整块，考虑离线下来，对于每个关键点，把在第二棵树的他的祖先上的点权值标记成 $1$，统计第一棵树的每个点的祖先权值和。这样也可以 $\mathcal O(1)$ 处理修改对查询的贡献。总复杂度 $\mathcal O(n\sqrt n)$。
另一个厉害一点的思路是求出欧拉序之间的贡献。
T3
咕了。
sub2
可以看成是求 $\displaystyle \sum_i\sum_j\binom i j a_ib_j$，可以简单 ntt 解决。
sub3
感觉挺高明的。答案可以表示成：
\[\begin{aligned} &\sum_i E_i\sum_j F_jtA_j[x^{i-j}]\prod_{k=0}^{i-1}(1+B_ix)\\ =&\sum_i E_i\sum_j F_jtA_j[x^{-j}]\prod_{k=0}^{i-1}(x^{-1}+B_i)\\ \end{aligned}\]考虑初始设一个多项式 $\displaystyle F(x)=\sum_{i=0}^m F_itA_ix^i$，则在 $i$ 处的答案就是 $\displaystyle E_i[x^0]F(x)\prod_{j<i}(x^{-1}+B_j)$。
在 $n$ 上进行一个分治，建线段树的结构。先预处理处 $G_i(x)$ 表示节点 $i$ 下的 $(x^{-1}+B_j)$ 的乘积。然后再从上到下求出 $H_i(x)$ 表示节点 $i$ 的答案。初始令 $H=F$，然后向左递归的时候 $H$ 不变，向右递归的时候乘上左子树的 $G$ 做一个差卷积，注意保持多项式次数和区间长度一致。由主定理得复杂度是 $\mathcal O(n\log^2 n)$。
后面的还是算了吧。
Day 3
T1
首先确定长度最小的序列作为起点并确定起点的序列选择哪一个数字。暴力做转移复杂度全爆炸了。因为转移系数非常的不好算，所以猜测它有决策单调性，可以分治维护。写一个发现确实是对的，这样就可以做到 $\mathcal O(m^2\log^2 m)$。
暴力选择第一个数字效率过于低下。但是可以猜测（想不到）第一个数字和后面数字的选取之间也是有单调性的。即如果当第一个数字选择 $i$ 的时候后面数字的最优选点是 $a_2,a_3\dots a_n$，则如果选择了 $j>i$，则后面数字的选择有 $a’_k\geq a_k$。所以可以分治套分治做到 $\mathcal O(m\log^3 m)$。把 set 换成压位 trie 就可以暴力消去一个 $\log$（？）。
T2
咕了。
T3
咕了。
Day 4
T1
感觉是非常好的 DS 题。
sub1~3
把所有数都加进一个 trie 里面做 DP。如果某个子树是满的就向另一个子树递归，否则是两者取 $\max$。上个莫队就能做到 $\mathcal O(m\sqrt n\log n)$。
sub6~7
直接这样做 DP 最大的问题就是两边都不满不知道该向哪边递归。一个很厉害的转化是考虑每个点的贡献，是祖先的另一个儿子满子树的 $siz$ 和。
考虑排列。扫描线扫描右端点，每次把一个数加进 trie 树。一个点的贡献关于 $l$ 只有 $\log n$ 段。一个子树被填满了之后，另一个子树的贡献变化形如“若 $l\leq x$，则贡献增加 $2^k$”。暴力更新另一个子树所有的点，一个点只会被更新 $\log n$ 次。每个点有 $\log n$ 段发生变化。每次线段树上二分找出对应区间做区间推平，还要做历史和，复杂度是巨大常数 $\mathcal O(n\log^3 n)$，非常爆炸。
注意到一个子树是一起被更新的，而子树内只有 $\mathcal O(siz)$ 段贡献区间，可以通过一个简单 DP 求出来所有的贡献区间。而这个区间只有 $\log n$ 个子树外的贡献，可以和这个进行归并，这样子树内的复杂度降至 $\mathcal O(n\log^2 n+m\log n)$，但是子树外的若干个区间可能会寄，需要记录每个区间对应的最大权值最后一起更新复杂度才是对的。
正解
现在一个子树可能会被填满多次。考虑一个满子树之前子树内的出现值的最小值 $prmn$ 和现在最小值 $mn$，实际上有变化的就是，对另一个子树的贡献“如果左端点小于等于 $prmn$ 则增加 $2^x$”变成了“如果左端点小于等于 $mn$ 则增加 $2^x$”，有变化的其实就是 $(prmn,mn]$ 的这段区间。
现在需要维护子树内加数，删掉最早出现的数，维护 xormex。可以每个子树开一个 trie 树，实现 sub1 的暴力 DP。更新数还是 $\mathcal O(n\log n)$，复杂度是 $\mathcal O(n\log^2 n+q\log n)$。（话说 BIT 可以做区间加，区间历史和哎）
T2
咕了。
T3
咕了。
Day 5
T1
$f_{i,j}$ 表示 $i$ 子树内选了 $j$ 个点的最大权值，转移是背包合并。
这个东西显然可以只保留凸的部分，先把子树合并起来，然后大概形如这样：
把不凸的地方不断弹出和 $f_x$ 合并就行了。
T2
一个连通块合法当且仅当其周围的点要么大于最大值，要么小于最小值。充分必要性都显然。这样暴力做就是 $\mathcal O(n^2)$。
上面这个判定显然没啥前途。考虑拆一下贡献。看起来最大值和最小值关乎一些麻烦的事情，所以把 $siz$ 拆开，变成数三元组 $(l,r,x)$ 的个数。此时 $x$ 与 $l,r$ 的路径上的点需要全部都在 $[l,r]$ 内。
考虑点分治计算这个东西！非常牛啊，三元组也能上点分的！在第一次把 $l,r,x$ 劈开的位置计数。计算每个点到根链上的最大最小值，问题转化为有若干个 $l,r,x$，要求满足 $R_l\leq r,l\leq L_r,l\leq L_x\leq R_x\leq r$。
看起来很魔怔，可以画一个 $l,r$ 坐标轴。此时对于两个点对 $(l,R_l),(L_r,r)$，对他们有贡献的点是 $(\geq l,\leq r)$。
按照 $r$ 排序，从下到上扫。扫到一个 $l$ 就新加一个点，扫到一个 $x$ 就给前缀的一段 $l$ 加一，扫到一个 $r$ 就容易一段后缀的 $l$ 的权值和。可以用一个线段树实现，复杂度 $\mathcal O(n\log n)$。这样总复杂度就是 $\mathcal O(n\log^2 n)$。
T3
咕了。
Day 6
T1
感谢 yxh 老师的讲解，直接爆标了，太强了/bx/bx。文中的虚树指的都指的是虚树的点和虚树边覆盖的所有点。
取全集，则需要保证 $\text{mex}$ 为 $V+1$，所以每个颜色都至少出现一遍，$V>n$ 时无解。
首先 $0$ 必须出现并且只有一个，$1$ 也必须出现并且只有一个。然后对于 $2$，观察到如果他想出现多次，则需要树中没有 $\text{mex}$ 为 $2$ 的连通块。因为这个连通块首先不包含 $2$，然后如果有多个 $2$ 这个连通块吞掉其中一个之后其 $\text{mex}>2$，一定不合法。
所以充要条件是，从小到大加颜色，如果颜色 $i$ 出现多次则必须全都出现在 $[0,i-1]$ 构成的虚树里。
考虑设 $f_{i,j,k}$ 表示当前考虑到了颜色 $i$，虚树有 $j$ 个点，钦定后面的 $k$ 种颜色全部出现在虚树里面。转移是如果把这个点作为虚树内部出现的点，则令 $k-1$。如果是要作为扩张虚树的点就扩一条长度为 $x$ 的链，系数是 $k^x$。
但是有问题是需要每种颜色至少出现一次，但是上述 DP 对于全都出现在虚树内部就可能出现零次。考虑容斥，在第 $i$ 个点的时候可以什么也不干，$j,k$ 都不变的乘一个 $-1$ 贡献到自己，意思是这个点强制钦定他出现了零次。复杂度可以前缀和优化到 $\mathcal O(n^3)$。