算法介紹——高維前綴和

引入

我們都知道二維前綴和有這么一個(gè)容斥的寫(xiě)法:

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    }
}

那換成三維前綴和，就有如下容斥代碼:
\( s[i][j][k]=a[i][j][k]+s[i-1][j][k]+s[i][j-1][k]+s[i][j][k-1]-s[i-1][j-1][k]-s[i-1][j][k-1]-s[i][j-1][k-1]+s[i-1][j-1][k-1] \)
非常的繁瑣，于是就誕生了如下二維前綴和的寫(xiě)法:

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        s[i][j]=s[i][j-1]+a[i][j];
    }
} 
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
     	s[i][j]+=s[i-1][j];
    }
}

其實(shí)就是先統(tǒng)計(jì)列的前綴和，再統(tǒng)計(jì)行的前綴和。
那三維前綴和只需要三遍 forforfor 就搞定了，明顯簡(jiǎn)單很多。

這就啟發(fā)我們對(duì)于更高維度的前綴和，同樣只需要做 \(n\)遍\(n\)層 for 循環(huán)。

正文

對(duì)于上面的 \(n\)遍\(n\)層for循環(huán) 的高維前綴和的代碼，其復(fù)雜度顯然不是我們能接受的，但是當(dāng)每一維很小時(shí)就可以進(jìn)行狀態(tài)壓縮。
最常見(jiàn)的就是每一維的大小為 \(2\) ,此時(shí)對(duì)于\(L\) 維數(shù)組就可以用一個(gè)長(zhǎng)度為 \(L\) 的二進(jìn)制數(shù)表示其中一個(gè)位置。

for(int i=0;i<L;i++){
    for(int j=0;j<(1<<L);j++){
        if(j>>i&1){
          f[j]+=f[j^(1<<i)];
         }
    }
}

時(shí)間復(fù)雜度\(O(L\times2^L)\)

子集求和

對(duì)于一個(gè)二進(jìn)制數(shù) \(j\) ,如果另一個(gè)二進(jìn)制數(shù) \(i\) 滿(mǎn)足，\(i \operatorname{and} j=i\) , 就說(shuō) \(j\) 包含 \(i\) , 即 \(i\) 是 \(j\) 的子集。
那上面的代碼相當(dāng)于對(duì)每一個(gè) \(j\) 加上它的所有子集，我們稱(chēng)它為 子集求和。

超集求和

對(duì)于一個(gè)二進(jìn)制數(shù) \(j\) ,如果另一個(gè)二進(jìn)制數(shù) \(i\) 滿(mǎn)足，\(i \operatorname{or} j=i\) , 此時(shí) \(i\) 包含 \(j\) , 即 \(j\) 是 \(i\) 的子集，此時(shí)我們稱(chēng) \(i\) 是 \(j\) 的超集 。
與子集求和類(lèi)似的，我們有如下 超集求和 代碼：

for(int i=0;i<L;i++){
    for(int j=0;j<(1<<L);j++){
        if(!(j>>i&1)){
            f[j]+=f[j^(1<<i)];
        }
    }
}

應(yīng)用

高維前綴和是計(jì)數(shù)的常用技巧，因此也被稱(chēng)為SOSDP。

其他

高維前綴和有時(shí)會(huì)配合Lucas定理使用，參見(jiàn)Lucas定理入門(mén)

例題

Compatible Numbers

\(a \operatorname{and} b = 0\) 等價(jià)于 \(a\) 是 \(b\) 的補(bǔ)集的子集，因?yàn)轭}目要求輸出任意一個(gè)答案，所以只要把上述子集求和的代碼中得加操作改成賦值操作即可。

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n;
int a[N];
int f[1<<22];
signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		f[a[i]]=a[i];
	}
	for(int i=0;i<=21;i++) {
		for(int j=0;j<(1<<22);j++) {
			if((j&(1<<i))&&f[j^(1<<i)]) f[j]=f[j^(1<<i)];
		}
	}
	for(int i=1;i<=n;i++){
		int b=((1<<22)-1)^a[i];   //計(jì)算補(bǔ)集 
		if(f[b]) printf("%d ",f[b]);
		else printf("%d ",-1);
	}
	return 0;
}

[ARC137D] Prefix XORs

設(shè) \(A_{i,j}\) 表示第 \(j\) 次操作后 \(A_i\) 的值，根據(jù)常識(shí)或手推可以知道:

因?yàn)榕紨?shù)個(gè) \(A_i\) 異或起來(lái)的的結(jié)果為\(0\)，所以 \(A_{i,0}\) 對(duì) \(A_{n,k}\) 有貢獻(xiàn)當(dāng)且僅當(dāng) \(C^{k}_{n-i+k}\) 為奇數(shù)，即 $ C^{k}_{n-i+k} \equiv 1 \pmod 2 $，根據(jù) Lucas 定理可知，此時(shí) \(k\) 是 \(n-i+k\) 的子集，即 $k \operatorname{and} (n-i) = 0 $，用高維前綴和預(yù)處理即可

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m;
int a[N]; 
int f[1<<20];
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int j=0;j<n;j++) f[j]=a[n-j];
	for(int i=0;i<=19;i++){
		for(int j=0;j<(1<<20);j++){
			if(j>>i&1){
				f[j]^=f[j^(1<<i)];
			}
		}
	}
	for(int k=0;k<m;k++){     //k從0開(kāi)始 
		printf("%d ",f[((1<<20)-1)^k]);   //求補(bǔ)集的答案 
	}
	return 0;
}