无聊的话写在前面

zlj：今天出联考成绩，四校排名我妈已经告诉我了！

随即说了句愚人节快乐......

今天T2居然是道原题？

dyp：不能说非常相似，只能说完全相同！

下午打篮球赛，初中打高中

高中连输两场？？？

总结

T1

给你一个长度为$n$的序列$\{a_n\}$和$x$，问$\{1,2,\cdots,n\}$有多少个非空子集$S$满足$\forall i,j\in S,a_i\text{ xor }a_j\le x$.

题解

令$i$是满足$2^t\ge x$的最小的$t$，将原序列分为若干组，满足每组数除去最低的$i$位后完全相同.

显然，不同组的两个数异或一定大于$x$，同组的两个数异或不小于$x$当且仅当它们第$i$位不同.

于是对每组分开算贡献，每组只能选$0,1$或$2$个数，前两种情况非常trivial，第三种情况可以将所有数依次插入Trie里，每插入一个数之前计算这个数的贡献即可.

答案即为每组选择的方案数的乘积减一（除去空集）.

T2

定义一个序列$a$对答案的贡献为$\max(L(a)-x,0)$，请你计算所有长度为$n$，且每个数取值$1$到$m$的序列的贡献值和.

题解

转化一下贡献$$\max(L(a)-x,0)=\sum_{k=x+1}^n[L(a)\ge k]$$ 于是考虑对每个$k\in[x+1,n]$求出最长连续段大于等于$k$的序列个数.

取个补集，转而考虑求最长连续段小于$k$的序列个数.

用组合意义算是不可能的，这辈子都不可能的.

假设我们将一个序列划分成了$i$个极长连续段，那么划分的方案数为$(m-1)^{n-1}m=\dfrac{m}{m-1}(m-1)^n$

令$f_i$为将长度为$i$的序列划分，且最长连续段的长度小于$k$的方案数.

显然有转移方程$$f_i=(m-1)\sum_{j=1}^{\min(k-1,i)}f_{i-j}$$ 答案即为$\dfrac{m}{m-1}f_n$.

由上述转移方程易知$f$是满足初值为$$f_0=1,f_1=m-1,\cdots,f_{k-2}=(m-1)m^{k-3}$$ 的$k-1$阶常系数线性齐次递推.

于是我们可以将它的生成函数写成$f(x)=\dfrac{p(x)}{q(x)}$，其中$$p(x)=f_0+\left[f_1-(m-1)f_0\right]+\left[f_2-(m-1)f_1-(m-1)f_0\right]+\cdots+\left[f_{k-2}-(m-1)f_{k-3}-\cdots-(m-1)f_0\right]=1$$$$\begin{aligned}q(x)=1-(m-1)x-\cdots-(1-m)x^{k}=\frac{1-[mx+(1-m)x^{k}]}{1-x}\end{aligned}$$ 代入得到$$f(x)=\frac{1-x}{1-[mx+(1-m)x^{k}]}$$ 而我们念念于兹的是$[x^n]f(x)$，即$$\begin{aligned}[x^n]f(x)&=[x^n]\frac{1}{1-[mx+(1-m)x^{k}]}-[x^{n-1}]\frac{1}{1-[mx+(1-m)x^{k}]}\end{aligned}$$ 而$$\begin{aligned}[x^n]\frac{1}{1-[mx+(1-m)x^{k}]}&=[x^n]\sum_{i=0}^{\infty}[mx+(1-m)x^{k}]^i\\&=[x^n]\sum_{i=0}^{\infty}\sum_{j=0}^i{\binom i j}m^{i-j}(1-m)^jx^{i+j(k-1)}\\&=\sum_{i=0}^{\infty}{\binom {n-i(k-1)} i}m^{n-ik}(1-m)^i\end{aligned}$$ 于是我们可以在$O(n/k)$的时间内求出$[x^n]f(x)$的值，总时间复杂度为$$\sum_{k=x+1}^n\frac{n}{k}=O(n\log n)$$