[atARC139F]Many Xor Optimization Problems
2022-05-11 10:56:31

对${A_{i}}$建立线性基（从高到低），并注意到以下性质

若线性基中第$xin [0,m)$位上存在元素，则其在$[2^{x},2^{x+1})$中独立均匀分布

根据此性质，仅存储每一位上是否存在元素，转移分类讨论：

1.若该元素未加入线性基，对应的方案数为$2^{线性基中元素个数}$

2.若该元素加入线性基且作为第$x$位，对应的方案数为$2^{x+线性基中>x位上的元素个数}$

在此基础上，枚举最终线性基的状态，并统计对应的方案数和（答案）期望

假设有$k$个元素依次在第$a_{1}<a_{2}<...<a_{k}$位上，则两者分别为——

方案数：将幂次中的$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}$

综上，总答案即
$$
sum_{0le a_{1}<a_{2}<...<a_{k}<m}prod_{i=1}^{k}2^{a_{i}}(2^{n-k+i}-1)left(frac{(2^{a_{k}+1}-1)+sum_{i=1}^{k}2^{a_{i}}}{2} ight)
$$

关于上述式子，实际上分为四部分——

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_{0le a_{1}<a_{2}<...<a_{k}<m}prod_{i=1}^{k}2^{a_{i}}$，对应的生成函数$G(x)=sum_{kge 0}g_{k}cdot x^{k}$

注意到$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_{0le a_{1}<a_{2}<...<a_{k}<m}2^{a_{k}}prod_{i=1}^{k}2^{a_{i}}$，对应的生成函数$H(x)=sum_{kge 0}h_{k}cdot x^{k}$

注意到$H(x)=sum_{i=0}^{m-1}2^{2i}xprod_{j=0}^{i-1}(2^{j}x+1)$，进而$2(x+1)H(2x)+x=H(x)+2^{2m}xcdot 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_{0le a_{1}<a_{2}<...<a_{k}<m}sum_{i=1}^{k}2^{a_{i}}prod_{i=1}^{k}2^{a_{i}}$，将$sum_{i=1}^{k}2^{a_{i}}$看作$(2^{m}-1)-sum_{j otin a_{i}}2^{j}$

展开可得$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)$，可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 250005
 4 #define mod 998244353
 5 #define ll long long
 6 int n,m,ans,pw[N],pre[N],suf[N],inv[N],w[N],g[N],h[N],f[N];
 7 int qpow(int n,int m){
 8     int s=n,ans=1;
 9     while (m){
10         if (m&1)ans=(ll)ans*s%mod;
11         s=(ll)s*s%mod,m>>=1;
12     }
13     return ans;
14 }
15 int main(){
16     scanf("%d%d",&n,&m);
17     pw[0]=pre[0]=suf[m+2]=w[0]=g[0]=1;
18     for(int i=1;i<=max(n,m+1);i++)pw[i]=(pw[i-1]<<1)%mod;
19     for(int i=1;i<=m+1;i++)pre[i]=(ll)pre[i-1]*(pw[i]-1)%mod;
20     for(int i=m+1;i;i--)suf[i]=(ll)suf[i+1]*(pw[i]-1)%mod;
21     int Inv=qpow(pre[m+1],mod-2);
22     for(int i=1;i<=m+1;i++)inv[i]=(ll)pre[i-1]*suf[i+1]%mod*Inv%mod;
23     for(int i=1;i<=n;i++)w[i]=(ll)w[i-1]*(pw[n-i+1]-1)%mod;
24     for(int i=1;i<=m;i++)g[i]=(ll)(pw[m]-pw[i-1]+mod)*inv[i]%mod*g[i-1]%mod;
25     for(int i=1;i<=m;i++)h[i]=((ll)pw[m]*pw[m]%mod*g[i-1]-((ll)pw[i]*h[i-1]+(i==1))%mod+mod)%mod*inv[i+1]%mod;
26     for(int i=0;i<=m;i++)f[i]=((ll)(pw[m]-1)*g[i]-(ll)(i+1)*g[i+1]%mod+mod)%mod;
27     for(int i=1;i<=n;i++)ans=(ans+w[i]*((ll)(h[i]<<1)-g[i]+f[i]+mod)%mod*(mod+1>>1))%mod;
28     printf("%d
",ans);
29     return 0;
30 } 

View Code