T1. 安顿

分析部分

考虑 $f(A,X)$ 怎么算。

由于是区间异或和的限制，考虑做一遍异或前缀和，那么 $A_{l\sim r}$ 的区间异或和就是 $S_r\oplus S_{l-1}$，限制就是不能等于 $X$。那么一组划分就相当于在 $0\sim n$ 种选择一个尽可能长的子序列，要求必须包含 $0$ 和 $n$，并且相邻两个数异或和不等于 $X$，$f(A,X)$ 即为子序列长度 $-1$。

首先考虑 $X=0$，也就是相邻两个数不能相等。注意到连续一段相同的数字里只能选一个，所以最多只能选“段数”个位置，而这是可以达到的，每个段内任选一个即可。特别地，如果只有一段（也就是全 $0$），那么此时 $0$ 和 $n$ 不能同时选，所以无解。综上，$X=0$ 时答案就是 $cnt-1$（$cnt$ 为颜色段数）。

接下来考虑 $X\ne 0$。由于数组的取值范围在 $0\sim 2^K-1$，那么任意一个数 $a$ 异或上 $X$ 一定还在这个范围内，而异或具有自反性，所以这相当于把 $0\sim 2^K-1$ 划分成了 $2^{K-1}$ 组匹配，要求最终的子序列中匹配的数字不能相邻。有了 $X=0$ 做法的启发，考虑把匹配的两个数看成同一种颜色，并划分颜色段。对于单个颜色段来说，显然只能选两个数中的一种，于是答案就是出现次数较多的那种。只要在每个颜色段都取出现次数较多的那个数，就一定合法，而且不可能取更多了。特别地，在第一段和最后一段，必须取 $0/n$ 所在的颜色。若只有一段，分类讨论特判一下即可。

计数部分

首先，所有数组 $A$ 和他们的前缀和数组 $S$ 一一对应，所以对所有 $A$ 求期望等价于对所有 $S$ 求期望。

$X=0$ 是简单的，只需要拆一下期望的线性性，对于每个缝隙 $i-1,i$，求他们的颜色不相等的概率，再加起来即可，所以答案即为 $n\cdot \frac{k-1}{k}$。

考虑 $X\ne 0$。同样拆期望的线性性，枚举每个区间 $1\le l\le r

一个长为 $len$ 的区间成为极长连续段的概率为 $(\frac{k-2}{k})^2(\frac{2}{k})^{len-1}$，期望贡献为 $\sum\limits_{i=0}^{len}\binom{len}{i}\max(i,len-i)$。贡献的式子在 $i\le \lfloor len/2\rfloor$ 时取 $len-i$，另一半对称，于是只考虑一半怎么算。首先 $len$ 的部分是容易的，直接提到外面算一下即可。对于另一部分，进行一下组合变换，有 $\sum\limits_{i=0}^{len/2}i\binom{len}{i}=len\sum\limits_{i=0}^{len/2-1}\binom{len-1}{i}$，于是需要计算组合数在一行的前缀和，这是经典的可以用递推解决的问题，这里不再赘述。

前缀、后缀、整个序列只有一段的贡献都是较平凡的，这里同样不再赘述。

T2. 狼抓兔子

对于 $\sum c_i\le 5\times 10^5$ 的部分，有一个经典的反悔贪心做法，读者可自行了解。

正解考虑 dp。从前往后考虑，维护 $f(x)$ 表示考虑到完当前位置，若 $x$ 为正则表示有 $x$ 只兔子需要留到后面匹配，$x$ 为负则表示有 $x$ 只狼需要留到后面匹配（不可能同时有兔子和狼往后留，显然立刻直接匹配他们更优），并且已经把所有留到后面的狼/兔子推到了当前位置，所需要的最小代价。

• 在移动到下一个位置的时候，会首先给 $f(x)$ 加上 $b_i\cdot |x|$ 的贡献，在函数上看就是一个 V 字形。
• 如果下一个位置有 $p$ 只狼，那么所有的狼都一定会先和目前的兔子匹配，匹配完剩下的再留到后面。这就相当于把整个函数往左平移了 $p$ 个位置。
• 如果下一个位置有 $p$ 只兔子，那么不一定所有的兔子都要参与匹配，可以选 $\le p$ 只参与，那么 $f'(y)=\min\limits_{x\in[y,y-p]}f(x)$。

综合三种操作，可以归纳地发现函数始终是下凸的，于是问题变成了，维护一个下凸函数，支持：

• 加 V 字形
• 向左平移
• 做向右平移的闵可夫斯基和

这些都是可以用平衡树维护折线完成的。

T3. 字符串

看到不能出现一些串，考虑 AC 自动机，那么相当于在自动机上随机游走，走到任一关键点的期望时间。对每个点列出方程，直接高斯消元即可得到一个 $(nm)^3$ 的做法，可以获得 $30$ 分。

为了优化，考虑设若干个主元，使得其他变量都可以用这些主元表示出来，这样方程就只有主元之间的限制了。注意到 $n$ 很小，考虑对自动机的 trie 树进行任意链剖分，并把每个链的链顶设为主元，从上往下递推主元的表示。

假设前 $k$ 层已经求出了主元表示，考虑第 $k$ 层的某一个元素 $i$，他的方程为 $f_{i}=1+\sum\limits_{ch}p_{ch}f_{nxt[i][ch]}$。由于 $i$ 的所有儿子中只能有一个重儿子，其他的儿子都一定是主元，而自动机上的其他边都指向更靠上的已经算完的点，且自己的表示也已经算完了，所以可以根据这个方程得到重儿子的表示。于是每次根据前 $k$ 层的表示与第 $k$ 层的方程，可以得到第 $k+1$ 层的表示，这样递推即可，复杂度为 $26nm\cdot n$。高斯消元的复杂度为 $n^3$，不在瓶颈上。