写一些最近做的计数题。目前只写了一部分。

[USACO20DEC] Spaceship P

以下认为 $n,k$ 同阶。

设 $dp_{i,j},i\le j$ 表示从已经摁下 $i$ 按钮这个状态开始，到刚摁下 $j$ 这个按钮，中间没摁过 $>j$ 的所有方案的转移矩阵之和。

直接转移是 trivial 的，但是复杂度为 $\mathcal{O}\left(n^5\right)$，不够优秀。

注意到所有 dp 值的矩阵都是关于邻接矩阵 $M$ 的多项式。所以可以求出 $M$ 的特征多项式 $P\left(x\right)$，每次矩阵乘法就把两个对应的多项式 $\mathcal{O}\left(n^2\right)$ 相乘，然后对 $P$ 取模。预处理出 $M$ 的 $0\sim n$ 次方即可 $\mathcal{O}\left(n\right)$ 求出单个多项式对应的答案。

这时复杂度为 $\mathcal{O}\left(n^4+qn^3\right)$。因为询问的时候首先枚举最大位置，再对两个多项式做乘法并取模，再计算答案。还是不够优秀。考虑优化掉 $q$ 上面一个 $n$。

由于每次做乘法的两个多项式次数都是 $n-1$。于是考虑把所有的 dp 值都转为 $2n-1$ 维点值，然后预处理出每个点值对每个位置的贡献，即可 $\mathcal{O}\left(qn^2\right)$ 回答询问了。

L-X and Xor link

令 $L\left(x\right)$ 表示 $x$ 最低位的 $1$，若 $x=0$ 则 $L\left(x\right)=m$。

考虑最终结果中第 $i$ 位为 $0$ 和 $1$ 的概率。

若存在一个下标 $i$ 满足 $L\left(A_i\right)+L\left(A_{i+1}\right)<i$，那么这一位为 $0$ 和 $1$ 的概率相等，否则，答案取决于 $\#\left\{L\left(A_i\right)+L\left(A_{i+1}\right)=i\right\}\bmod 2$，

若 $L\left(A_{n-1}\right)\le i$，不妨设 $L\left(A_{n-1}\right)=k$，那么 $L\left(A_{n-1}\right)+L\left(A_{n}\right)=i$ 的概率都为 $2^{-\left(i-k+1\right)}$。为对称的，因此可以不用考虑

于是只需考虑 $L\left(A_{n-1}\right)>i$ 的情况，此时 $L\left(A_{n-1}\right)+L\left(A_{n}\right)>i,L\left(A_{n-2}\right)+L\left(A_{n-1}\right)>i$，最后两个不对答案产生贡献。

依次类推，只有从后往前偶数位置的 lowbit 都 $>i$ 时才不对称，而此时这一位必定为 $0$。

设 $t=\left\lfloor n/2\right\rfloor$，那么答案即为：$$2^{nm}\sum_{i=0}^m\left(1-2^{-\left(i+1\right)t}\right)\times \dfrac{1}{2}\times 2^i$$