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

對${A_{i}}$建立線性基（從高到低），并注意到以下性質(zhì)

若線性基中第$xin [0,m)$位上存在元素，則其在$[2^{x},2^{x+1})$中獨(dú)立均勻分布

根據(jù)此性質(zhì)，僅存儲每一位上是否存在元素，轉(zhuǎn)移分類討論：

1.若該元素未加入線性基，對應(yīng)的方案數(shù)為$2^{線性基中元素個數(shù)}$

2.若該元素加入線性基且作為第$x$位，對應(yīng)的方案數(shù)為$2^{x+線性基中>x位上的元素個數(shù)}$

在此基礎(chǔ)上，枚舉最終線性基的狀態(tài)，并統(tǒng)計對應(yīng)的方案數(shù)和（答案）期望

假設(shè)有$k$個元素依次在第$a_{1}<a_{2}<...<a_{k}$位上，則兩者分別為——

方案數(shù)：將冪次中的$x$提出，其余部分求和可以看作以下問題

將${a_{i}}$和$n-k$個$-1$（未加入線性基的元素）重新排列（確定加入順序）后的逆序?qū)?shù)

將所有$n$個元素從小到大依次插入排列，總方案數(shù)即$prod_{i=1}^{k}2^{a_{i}}sum_{j=0}^{n-k+i-1}2^{j}$

期望：$>a_{k}$位必然為$0$，第$a_{i}$位必然為$1$，其余位在$01$中獨(dú)立均勻隨機(jī)

將$[0,a_{k}]$位均看作均勻隨機(jī)并補(bǔ)上必然為$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)
$$

關(guān)于上述式子，實際上分為四部分——

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}}$，對應(yīng)的生成函數(shù)$G(x)=sum_{kge 0}g_{k}cdot x^{k}$

注意到$G(x)=prod_{i=0}^{m-1}(2^{i}x+1)$，進(jìn)而$(x+1)G(2x)=(2^{m}x+1)G(x)$

比較兩者$k$次項系數(shù)，可得$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}}$，對應(yīng)的生成函數(shù)$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)$，進(jìn)而$2(x+1)H(2x)+x=H(x)+2^{2m}xcdot G(x)$

比較兩者$k$次項系數(shù)，可得$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}$，進(jìn)而總答案也即$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)}$處理逆元

時間復(fù)雜度為$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

?