Ucup Stage 5 Osijek 部分题解
A And Xor Tree
我们把贡献拆开，设 $B_i$ 表示与 / 或 / 异或第 $i$ 位的值，那么：
也就是说对于每两位，只需要求出多少条路径的与 / 或 / 异或在这两位均为 $1$ 即可。
实际上三者都可以利用 $dp$ 解决。设 $f_{u,i,j}$ 表示 $u$ 向下，第一位为 $i$ ，另一位为 $j$ 的路径个数。然后合并即可。
但是如果对于每对 $i,j$ ，均做一次 dfs 会直接 TLE 。参考了 sjx 的优秀代码，对所有点按 dfs 序重编号后按这个编号 $dp$ 即可。
C Cyclic Shifts
精妙的构造题。
首先把小于一半的都放前面，大于一半的放后面。如果把前一半中本应在后面的和后一半中本应在前面的拿出来并一共有 $2x$ 个位置，显然只需要 $x$ 次轮换就可以达成这个目标。花费 $0.5$ 。
接下来考虑对于后一半的数，按从 $n$ 到 $\frac n 2$ 依次放到最前面，也就是把该数和前面的所有的数都选上进行轮换，如果设 $m = \frac n 2$ ，很显然代价不超过 $\frac{1}{m+1}+\frac 1 {m+2} + \cdots + \frac 1 {2m} \sim \ln 2m - \ln m = \ln 2$ 。
然后现在前一半是有序的 $m+1,\ldots,2m$ ，我们对后一半的 $m,m-1,\ldots,1$ 同样进行这样的操作来轮换，代价一样不超过 $\ln 2$ ，就实现了排序。
因此总共花费 $2\ln 2 + 0.5 < 2$ 。
D Distinct Subsequences
考虑把整个数列写成若干个 $0$ 和 $1$ 的切换过程，即写成 $x_1,x_2,\ldots,x_m$ ，每个 $x$ 表示极长 $0/1$ 段的长度。
然后考虑计算所有尽量靠前的本质不同的长为 $k$ 的子序列。
这个过程可以看成在每段 $0/1$ 中选择开头的若干个值，然后拼起来。或者选择某个段全部选完，并且跳过下一段继续选这个数。
这个选数的过程可以看作是多项式乘法的过程。在每次多项式乘法后还需要累计求和一下（因为可以选择在任意段停下）。所以可以写出一个矩乘的形式。对于一个长为 $w$ 的段：
其中 $W = x+x^2+\cdots+x^w$ 。
直接分治乘一下矩阵即可。复杂度 $O(3^3n\log^2 n)$ 。