我打析合树？真的假的？要上吗？

A

把异或值二进制分解，根据期望线性性，\(E((\sum\limits_{i=0}^ka_ix^i)^2)=E(\sum\limits_{i=0}^k\sum\limits_{j=0}^ka_ia_jx^{i+j})=\sum\limits_{i=0}^k\sum\limits_{j=0}^kE(a_ia_j)x^{i+j}\)，

而 \(E(a_ia_j)\) 就是选出的子集的异或值的 \(i,j\) 位都为 1 的概率，直接 DP 即可。

B

只需要对每个 \(k\) 算，每个 1 段长度都不超过 \(k\) 的序列个数。

考虑容斥，设 \(f(i)\) 表示在序列中钦定 \(i\) 个长度超过 \(k\) 的 1 段的方案数，则答案为 \(\sum\limits_{i\ge 0}(-1)^if(i)\)。

考虑算 \(f(i)\)。首先在 \(n-m+1\) 个 1 段中选出 \(i\) 个 1 段的方案数为 \({n-m+1\choose i}\)，

选出 \(i\) 个 1 段后，既然要钦定这 \(i\) 个 1 段长度超过 \(k\)，那就先往它们每一段中插 \(k+1\) 个 1，剩下的 1 随便放，

方案数实际上就是把 \(m-i(k+1)\) 个 1 放进 \(n-m+1\) 个 1 段的方案数，插板法可得方案数为 \({n-i(k+1)\choose n-m}\)，

于是 \(f(i)={n-m+1\choose i}{n-i(k+1)\choose n-m}\)。发现 \(i\le m/(k+1)\) 时 \(f(i)\) 才有值，所以复杂度调和级数。

C

观察到两个性质：

1. 相邻两个相同的手势可以只留下一个
2. 两个强手势夹一个弱手势，可以只留一个强手势

维护一个手势栈，满足以栈顶为第一个时，对于相邻的两个手势，后一个能赢前一个。

考虑加入一个手势 \(x\)，若栈顶能赢 \(x\) 直接入栈，若栈顶与 \(x\) 相同由性质 1 直接不管，若 \(x\) 能赢栈顶由性质 2 直接弹栈。

（特别地，若栈中只有一个手势，\(x\) 能赢栈顶，则性质 2 不成立，需要先弹栈再把 \(x\) 入栈）

手模一下，可以发现答案就是栈底，也就是最后一次栈中只有一个手势时的这个手势，考虑如何找到这个时刻。

考虑直接不管栈中只有一个手势的情况，\(x\) 能赢上一个数时必定弹栈（这样栈的大小可能是负的），

画个图可以发现，此时栈的大小最小的时刻，就是我们要找的时刻。

设 \(a_i\) 表示加入 \(i\) 处手势后栈的大小的变化量，则询问 \(l,r\) 时，\(i\) 时刻栈的大小为 \(\sum\limits_{j=l}^ia_j\)，

要找栈的大小最小的时刻，就是要找 \(a\) 在 \([l,r]\) 上的前缀和最小值，还需要单点修改，线段树维护即可。

D

明天再写，别急。