[atARC139F]Many Xor Optimization Problems
对$\{A_{i}\}$建立线性基(从高到低),并注意到以下性质
若线性基中第$x\in [0,m)$位上存在元素,则其在$[2^{x},2^{x+1})$中独立均匀分布
根据此性质,仅存储每一位上是否存在元素,转移分类讨论:
1.若该元素未加入线性基,对应的方案数为$2^{线性基中元素个数}$
2.若该元素加入线性基且作为第$x$位,对应的方案数为$2^{x+线性基中>x位上的元素个数}$
在此基础上,枚举最终线性基的状态,并统计对应的方案数和(答案)期望
假设有$k$个元素依次在第$a_{1} 方案数:将幂次中的$x$提出,其余部分求和可以看作以下问题 将$\{a_{i}\}$和$n-k$个$-1$(未加入线性基的元素)重新排列(确定加入顺序)后的逆序对数 将所有$n$个元素从小到大依次插入排列,总方案数即$\prod_{i=1}^{k}2^{a_{i}}\sum_{j=0}^{n-k+i-1}2^{j}$ 期望:$>a_{k}$位必然为$0$,第$a_{i}$位必然为$1$,其余位在$01$中独立均匀随机 将$[0,a_{k}]$位均看作均匀随机并补上必然为$1$的部分,总期望即$\frac{\sum_{i=0}^{a_{k}}2^{i}+\sum_{i=1}^{k}2^{a_{i}}}{2}$ 综上,总答案即 关于上述式子,实际上分为四部分—— 1.记$w_{k}=\prod_{i=1}^{k}(2^{n-k+i}-1)$,注意到该式等价于$\prod_{i=0}^{k-1}(2^{n-i}-1)$,直接计算即可 2.记$g_{k}=\sum_{0\le a_{1} 注意到$G(x)=\prod_{i=0}^{m-1}(2^{i}x+1)$,进而$(x+1)G(2x)=(2^{m}x+1)G(x)$ 比较两者$k$次项系数,可得$g_{k}=\frac{2^{m}-2^{k-1}}{2^{k}-1}g_{k-1}$,可以递推计算 3.记$h_{k}=\sum_{0\le a_{1} 注意到$H(x)=\sum_{i=0}^{m-1}2^{2i}x\prod_{j=0}^{i-1}(2^{j}x+1)$,进而$2(x+1)H(2x)+x=H(x)+2^{2m}x\cdot G(x)$ 比较两者$k$次项系数,可得$h_{k}=\frac{2^{2m}g_{k-1}-2^{k}h_{k-1}-[k=1]}{2^{k+1}-1}$,可以递推计算 4.记$f_{k}=\sum_{0\le a_{1} 展开可得$f_{k}=(2^{m}-1)g_{k}-(k+1)g_{k+1}$,进而总答案也即$\sum_{k=1}^{n}\frac{w_{k}(2h_{k}-g_{k}+f_{k})}{2}$,直接计算即可 另外,为了做到线性,可以利用$\frac{1}{2^{k}-1}=\frac{\prod_{i=1}^{k-1}(2^{i}-1)\cdot \prod_{i=k+1}^{\max}(2^{i}-1)}{\prod_{i=1}^{\max}(2^{i}-1)}$处理逆元 时间复杂度为$o(n+m)$,可以通过
$$
\sum_{0\le a_{1} 1 #include