master_rat1 edited 3 年，6 月前
本次 EOJ 月赛由华东师范大学 ACM 团队与华东师大二附中信息学竞赛组联合举办。
感谢华东师范大学肖春芸老师、华东师范大学第二附属中学金靖老师周密的组织策划，使得 EOJ 月赛能够圆满完成。此外，感谢 EOJ 运维团队为月赛提供了重要的技术支持。
也感谢各位出题人对月赛作出的贡献，感谢所有选手的参与！祝大家假期愉快！
令 $X=A_1~|~A_2~|\cdots|~A_N$，$Y=B_1~\&~B_2~\&\cdots\&~B_M$，下面证明 $X\subseteq Y$（即只要 $X$ 的某个二进制位是 $1$，则 $Y$ 的该二进制位也为 $1$）是 $(A,B)$ 合法的充要条件。
先证明必要性，假设存在一个二进制位使得 $X$ 是 $1$ 而 $Y$ 是 $0$，则 $\exists 1\le j\le M$ 使 $B_j$ 的该二进制位为 $0$，所以 $\forall ~1\le i\le N$ 都有 $a_{i,j}$ 的该二进制位为 $0$，因此 $\forall~1\le i\le N,A_i$ 的该二进制位都为 $0$，$X$ 的该二进制位不可能为 $1$，矛盾。
再证明充分性， 可以通过如下方法构造出一个符合条件的表格：
由于 $\forall 1\le i\le N,1\le j\le M$ 有 $A_i\subseteq X\subseteq Y\subseteq B_j$，所以该表格合法。
可以枚举 $X$，设其中有 $c$ 个二进制位为 $1$，则 $A$ 的个数为 $(2^N-1)^c$，容易用数位dp计算 $B$ 的个数。时间复杂度为 $O(K\log N)$。
credit: ix35
暴力枚举 $2^h-1$ 个非叶结点的开关状态，再暴力计算每个点的球数。
时间复杂度为 $O(2^h\times nh)$，期望得分 $10$ 分。
我们将最后构造出的树上每个点开关状况记为 $S$，而初始时所有点的开关都朝左的状况为 $T$。
我们首先证明一个引理：
引理 $1$：对于任何初始状况对应的 $S$，存在唯一的叶结点重标号方案，使得它等价于 $T$。
证明：考虑从根结点出发，每遇到一个开关朝右的点，就将其左右子树的叶子编号对应交换，最后得到了 $T$。
在证明中可以发现，$S$ 中的一个子树总是和 $T$ 中的一个子树一一对应。
于是我们可以设计 DP，令 $dp(i,j)$ 表示将 $S$ 中以 $i$ 为根的子树对应 $T$ 中以 $j$ 为根的子树时，这个子树内所有关键点的球数之和的最大值，这里要求 $i,j$ 深度相同。
转移是简单的：$dp(i,j)=\max(dp(l_i,l_j)+dp(r_i,r_j),dp(l_i,r_j)+dp(r_i,l_j))$。
边界即叶结点，我们对每个 $T$ 中的叶结点先计算出 $w_i$ 表示它最终的球数，那么当 $j$ 是叶子时 $dp(i,j)=w_j$。
时间复杂度为 $O(2^{2h})$，期望得分 $30$ 分。
我们考虑再证明一个引理：
引理 $2$：在连续投出 $2^h$ 个球后，每个叶子恰有一个球。
在证明这个引理的同时，我们将归纳给出在 $T$ 中最初 $2^h$ 个球流向何方。
令 $A_{h,j}$ 是高度为 $h$ 的树 $T$ 中第 $j$ 个球落到的叶子，下面我们递归证明：$A_h$ 是由 $A_{h-1}$ 和 $A_{h-1}+2^{h-1}$（这表示其中每个元素都加上 $2^{h-1}$） 交替连接得到的，形式化地，有：
$$
A_{h,2j-1}=A_{h-1,j},\ \ \ \ A_{h,2j}=A_{h-1,j}+2^{h-1}
$$
这一点只通过模拟根结点的开关变化即可发现，可以发现第奇数次球会到左边子树，而第偶数次球会到右边子树，这已经证明了上面的引理。
由此可以得到简单推论：
引理 $2$ 推论：在连续投出 $2^h$ 个球后，所有点的开关状态与最初相同。
证明：由于每个叶子都恰好有一个球，所以每个点被经过了其子树内叶子结点个数这么多次，这是一个偶数，所以开关状态和最初相同。
这告诉我们：每 $2^h$ 个球为一组，叶结点求出分布呈现周期性。
由引理 $2$，我们可以简单地知道 $m=1$ 时的答案：令唯一的关键点对应 $T$ 中的点 $1$，那么一定是每一周期中第一个有球经过的点，所以答案就是 $\lceil \dfrac{n}{2^q}\rceil$。
时间复杂度为 $O(1)$，期望得分 $10$ 分，结合 $\text{Algorithm 2}$ 可获得 $40$ 分。
尝试优化 $\text{Algorithm 2}$ 中的 DP，我们需要进一步观察 $T$ 和 $A_h$ 序列的性质。
我们称两个 $T$ 中子树是 $i\text{-}$本质不同的，当且仅当在扔下 $i$ 个球后两个子树中所有球数非零的叶结点不同构（即不能通过重标号使得两个子树中球数非零的叶结点完全重合）。
引理 $3$：对于任意 $i\leq 2^h$ 和任意深度 $h_0$，深度为 $h_0$ 的子树中 $i\text{-}$本质不同的至多有两种。
证明：（深度是到根结点的边数）考虑之前所述 $A_h$ 序列的生成过程，不难发现：考虑所有深度为 $h_0$ 的子树，可以将它们视作整体，将整个扔球操作看成 $2^{h-h_0}$ 个周期，每个周期内 $2^{h_0}$ 个球被扔到每个子树中各一个，而且每个子树内同一周期内球进到的叶子的相对位置是相同的，所以在一个周期进行到第 $x$ 个球时，只会有前 $x$ 个子树和后 $2^{h_0}-x$ 个子树这两种本质不同的子树。
于是原本状态 $dp(i,j)$ 中的第二维 $j$ 只有两种不同情况了，我们只需用 $dp(i,0)$ 和 $dp(i,1)$ 来代替。
转移时，我们需要知道两种深度为 $i$ 的本质不同子树的两个儿子各是哪一种深度为 $i+1$ 的子树，我们可以令 $S(i,0),S(i,1)$ 分别表示大小为 $i$ 的两种本质不同子树的球数非零的叶结点数量，容易发现 $|S(i,0)-S(i,1)|\leq 1$，我们只需要根据这个大小就可以判断是由哪两个子树相加得到的了。
时间复杂度为 $O(2^h)$，期望得分 $40$ 分，结合 $\text{Algorithm 3}$ 可获得 $50$ 分。
当 $h$ 较大时，我们发现只要取所有关键点的祖先结点进行 DP 即可，其余点的 DP 值一定是 $0$。
如果不显式建树，那么需要查询一个点子树内是否有关键点，稍微麻烦点，我们可以选择仿照 Trie 的方式建树，直接得到有效的二叉树结构。
credit: ix35
暴力枚举所有可能的串询问，询问次数约为 $3^R$。
首先确定 $a$ 的个数，只要二分即可。
然后确定 $b$，在任意相邻两个 $a$ 之间二分即可。
然后确定 $c$，在任意相邻两个 $a,b$ 之间二分即可。
询问次数约为 $2n\log R$。
发现上面的二分还不如直接枚举 $a,b,c$ 的个数并检验。
例如确定 $b$ 时，只需要在从小到大枚举相邻两个 $a$ 中有几个 $b$。
询问次数约为 $3n$。
虽然询问 $b,c$ 时枚举比较好，但是询问 $a$ 时还是二分更优。
询问次数约为 $2n+\log R$。
首先确定 $a,b,c$ 的数量，分别设为 $x,y,z$。
不妨设 $x\leq y\leq z$，然后套用上一个做法即可。
来分析一下询问次数：
由于 $x\leq y\leq z$，所以 $x+y\leq \dfrac{2}{3}n$，所以总询问次数约为 $\dfrac{5}{3}n+3\log R$。
时间复杂度为 $O(mh)$，期望得分 $100$ 分。
credit: ix35
$S$ 的后缀自动机上的结点和其反串 $S’$ 的后缀树的结点是对应的，下面考虑计算一个串 $S$ 的后缀树的期望结点数量。
利用字符集大小为 $2$ 的特殊性，我们可知后缀树是一棵二叉树，且可以将结点分成三类（这里不算终止符对应的结点）：
将这三类结点的数量分别设为 $a,b,c$，所求即 $a+b+c$ 的期望。
如果只考虑 A,C 两类结点，根据二叉树的性质易知 $a+c=2a-1$，所以 $a+b+c=2a+b-1$，只需要分别求 $a,b$ 的期望即可，下面以求 $a$ 的期望为例。
枚举以 $i$ 开头的后缀 $Suf(i)$，计算它在全串中仅出现一次的概率 $P(i)$，则 $E(a)=\sum\limits_{i=1}^n P(i)$。
考虑容斥，枚举 $[i-1]={1,2,\ldots,i-1}$ 的子集 $A$，钦定 $Suf(i)$ 是所有 $Suf(j)\ (j\in A)$ 的前缀，设此概率为 $Pr(A)$，则：
$$
P(i)=\sum \limits_{A\subseteq [i-1]} (-1)^{|A|}\times Pr(A)
$$
下面考虑用两种方法计算上式：
暴力枚举 $A$，然后可以建出一张表示某些位置上字符相等的图，数一下连通块，再结合给定的字符就可以方便地得到 $Pr(A)$。
复杂度为 $O(n^2\times 2^{i})$。
令 $len=n-i+1$。
枚举 $Suf(i)$，然后对 $A$ 的容斥系数进行 DP，令 $f(x)$ 表示考虑了 $Suf(1),\ldots,Suf(x)$，且 $Suf(x)$ 以 $Suf(i)$ 为前缀时，$x$ 之前的这些后缀在 $A$ 中部分的贡献，考虑转移 $dp(x)\times w(x,y)\to dp(y)$，则：
先对枚举的 $Suf(i)$ 进行一下 KMP 求出所有 Border，然后 $O(n^2)$ DP。
复杂度为 $O(n^2\times 2^{n-i})$。
结合以上两个算法，当 $i\leq \dfrac{n}{2}$ 时采用法一，当 $i>\dfrac{n}{2}$ 时采用法二，总复杂度 $O(n^2\times 2^{\frac{n}{2}})$。
这是计算 $E(a)$ 的，而 $E(b)$ 基本是一样的，只是在 $Suf(i)$ 后加上一个 $0$ 和加上一个 $1$ 后执行上面算法得到的结果（分别记作 $P_0(i)$ 和 $P_1(i)$），则：
$$
Ans=2E(a)+E(b)-1=\sum\limits_{i=1}^n \Big(2P(i)+(P_0(i)-P(i)+P_1(i)-P(i))\Big)-1=\sum\limits_{i=1}^n \Big(P_0(i)+P_1(i)\Big)-1
$$
所以实际上只要算 $P_0,P_1$ 就可以了，砍掉了 $\dfrac{1}{3}$ 的常数。
此外注意一下根结点只有一个儿子的情况（本质上是空后缀作为 B 类结点，此时 $S$ 为全 $0$ 或全 $1$ 串），要么枚举 $i$ 的时候算上空后缀，要么根据 $S$ 是否可能全 $0$ 和全 $1$ 特殊处理一下。
时间复杂度 $O(n^2\times 2^{\frac{n}{2}})$，可以通过本题。