SOSdp

从子集和问题到and卷积

枚举子集：$O(3^{n})$

	int u=15;
	for (int s = u; s; s = (s - 1) & u) {
	b=s ;
	cout<<b<<endl;
}
/*
1111
1110
1101
1100
1011
1010
1001
1000
0111
0110
0101
0100
0011
0010
0001
*/

子集和问题参考好的博客https://ottffyzy.github.io/algos/dp/sosdp/

其实这类算法更多的是解决子集和 （sum of subset） 问题，因此也叫 SOS DP。

也就是对于i从1-n我们希望求出$sum[i] = \sum_{j \subseteq i} a[j]$

一个平凡的做法是直接枚举子集：$O(3^{n})$

for (int i = 0; i < n; i++) {
  sum[i] = a[0]; // 空集被包含于所有集合
  for (int j = i; j > 0; j = (j - 1) & i)
    sum[i] += a[j];
}

引入高维前缀和可以优化到$O(2^{n}n)$

对于高位前缀和如果容斥计算，不仅麻烦而且复杂度不优

for (int j = 1; j <= m; j++)
  for (int k = 1; k <= l; k++) // 求 j k 相等的每条线上的前缀和
    for (int i = 1; i <= n; i++) {
      line_sum[i][j][k] = line_sum[i - 1][j][k] + a[i][j][k];
    }
for (int k = 1; k <= l; k++) // 求 k 相等的每一个面上的前缀和
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      face_sum[i][j][k] = face_sum[i][j - 1][k] + line_sum[i][j][k];
    }
for (int i = 1; i <= n; i++)
  for (int j = 1; j <= m; j++)
    for (int k = 1; k <= l; k++) {
      sum[i][j][k] = sum[i][j][k - 1] + face_sum[i][j][k];
    }

注意到这里其实对于每个三重循环，我们可以任意排列 i,j,k 循环的位置。仔细观察，我们其实是在按照维度依次做前缀和（每次处理了前 p个维度的前缀和）。

这里我们发现复杂度从原本的容斥$O(2^D \Pi_{i = 1}^{D} N_i)$ 下降到了 $O(D \Pi_{i = 1}^{D} N_i)$。当维数 D很大时，这个优化将会非常显著。

高维和和子集和的关系

这里我们注意到，实际上子集和可以按照位数 D 分为 D 个维度（每个维度只有 0,10,1 两个取值），而实际上每个子集和对应了一个 D 维超立方的前缀和。

这里我们可以完全的将求前缀和的方式搬到这里求子集和。

只是细节需要注意，任意一维 被−1 的位置可以假想对应了一个 0 的值，于是我们发现我们实质上在处理第 p 维时，只需要注意那些该维为 1 的位置。这里我们用 $dp[i][d]$ 表示超立方体已经处理了下标 0∼d维度时的前缀和。

for (int i = 0; i < (1 << D); i++) {
  if (i & 1) {
    dp[i][0] = a[i] + a[i ^ (1 << d)];
  } else {
    dp[i][0] = a[i];
  }
}
for (int d = 1; d < D; d++) {
  for (int i = 0; i < (1 << D); i++) {
    if (i & (1 << d)) {
      dp[i][d] = dp[i][d - 1] + dp[i ^ (1 << d)][d];
    } else {
      dp[i][d] = dp[i][d - 1];
    }
  }
}

我们发现可以采用滚动数组省去一维

for (int i = 0; i < (1 << D); i++) {
  dp[i] = a[i];
}
for (int d = 0; d < D; d++) {
  for (int i = 0; i < (1 << D); i++) {
    if (i & (1 << d)) {
      dp[i] += dp[i ^ (1 << d)];
    }
  }
}

当我们知道了子集和，我们可以倒推出本身的权值。

for(int i=n-1;~i;i--) {
    for(int j=0;j<1<<n;j++) if(j&(1<<i)) {
        sum[j]-=sum[j^(1<<i)];
    }
}

超集和$sum[i] = \sum_{j \supseteq i} a[j]$

for (int i = 0; i < (1 << D); i++) {
  dp[i] = a[i];
}
for (int d = 0; d < D; d++) {
  for (int i = 0; i < (1 << D); i++) {
    if (!(i & (1 << d))) {
      dp[i] += dp[i ^ (1 << d)];
    }
  }
}

当我们知道了超集和，我们可以倒推出本身的权值。

for(int i=n-1;~i;i--) {
    for(int j=(1<<n)-1;~j;j--) if(j&(1<<i)) {
        sum[j^(1<<i)]-=sum[j];//疑似博客写错，这里应该是减号
    }
}

实战：毛营B题Binomial - Problem - QOJ.ac

题意：给定一个数组 $a_n$ ，求有几对数字 满足$(a_i,a_j)$满足$C^{a_i}_{a_j}$为奇数

Sol:结论题：$C^{n}_{m}$为奇数的条件是 n & m = m

也就是对于C(n,k),若n&k == k 则C(n,k)为奇数，否则为偶数

严谨证明：考虑卢卡斯定理的推论，尝试证明mod2意义下为1

$\text{C}_n^m\equiv \text{C}_{[n/p]}^{[m/p]}\times\text{C}_{n\bmod p}^{m\bmod p} \pmod p$

将$C^{n}_{m}$中的 n 和 m表示成 p 进制数：

$n=\sum\limits_{i=0}^k a_i\cdot p^i \left(a_k \ne 0 \right) $

$m=\sum\limits_{i=0}^k b_i\cdot p^i$

$\text{C}_n^m \equiv \prod\limits_{i=0}^k\text{C}_{a_i}^{b_i} \pmod p$

取p=2的时候，也就是对n和m的二进制拆分，我们希望为奇数，也就是必须全为1，也就是a[i]为0的位不参与计算，就是只计算二进制有效位。此时无论b[i]在这位为0或1结果，本次计算都是1，多个1相乘还是1，也就证明了计算结果是奇数

综上所述，原问题等价于在数组中找到有多少对包含关系

由于题目既不要求自环又不要求偏序，所以我们需要先把所有数存下来，再去dp。

const int len=__lg(N);
void solve(){
	cin>>n;
	vector<int>dp(N);
	ll ans=0;

	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[a[i]]++;
		// for(int j=0;j<=len;j++){
			// if((x>>j)&1)dp[x]+=dp[x^(1<<j)];
		// }
		// ans+=dp[x];
	
	}
	for(int i=0;i<=len;i++){
		for(int j=1;j<=1000000;j++){
		if((j>>i)&1)dp[j]+=dp[j^(1<<i)];
		}
	}
	for(int i=1;i<=n;i++)ans+=dp[a[i]];
	cout<<ans<<endl;
}

SOSDP学习笔记 | c4Lnn 的个人博客

Codeforces Round 112 (Div. 2)E

题意：给定一个数组，对于每个$a_{i}$找到$a_{j}$满足$a_{i}\&a_{j}=0$.如果有多个j满足要求，输出最小满足要求的j（cf上题目没要求，但可以加强）

Sol：考虑对于二进制位的取值情况，原问题等价于找~a[i]的子集，我们只需要正常做一遍sosdp。然后考虑统计答案。又由于设置最小，我们考虑对于dp的时候使用min运算维护值域对应的最小下标，答案是要输出元素

// a[i]  0      1
// ans[i] 0,1   0
const int len=__lg(M)+1;
const int N =(1<<len)+5;
int a[N];
int dp[N];
//假设需要找下标最小符合条件的答案的值,这样出题人就不用写spj了
//本题设计取反，所以实际涉及范围会超过题目a[i]的范围
void solve(){
	//找a[i]取反后的子集
	//cerr<<len<<endl;
	//cerr<<((1<<len)-1)<<endl;
	memset(dp,0x3f,sizeof dp);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];		
		dp[a[i]]=i;
	}
	for(int i=0;i<=len;i++){
		for(int j=0;j<(1<<len);j++){
			if((j>>i)&1){
				dp[j]=min(dp[j],dp[j^(1<<i)]);
			}
		}
	}
	//对于每个a[i]我们需要考虑他的取反有没有子集存在，这并不影响前面答案
	for(int i=1;i<=n;i++){
		int x=(1<<len)-1-a[i];;
		if(dp[x]==inf)cout<<-1<<" ";
		else cout<<a[dp[x]]<<" ";
	}
}

Codeforces Round 225 (Div. 1)E

题意：字符集为小写字母前24个。共有$2^{24}$的子集，给定若干长度为3的单词。对于每个子集，我们认为当前子集里的元素是元音，每个单词至少含1个元音才合法，回答在当前子集条件下有多少正确的单词？

Sol:将单词映射成二进制位，我们只关心当前单词有哪几个元素，不用关心重复元素。假设集合为s，当前单词为$a_{i}$,我们需要统计有多少个i满足$a_{i}\&s!=0$，这样正着考虑复杂度太高，我们考虑反面，$a_{i}\&s=0$的i的数量num，答案用n-num得到。而与起来等于0在上题已经被解决，我们只需要正常sosdp，在统计答案的时候找~a[i]的子集的数量。

bug1没想清楚到底两个循环的边界

bug2：一开始没处理高维前缀和，导致统计答案的时候导致多加了一层循环

//任何单词只要包含至少一个元音，就是正确的。
int dp[N];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
			int x=0;
		for(int j=0;j<3;j++){
			int u=s[j]-'a';
			x|=1<<u;
		}
		//cerr<<x<<endl;
		dp[x]++;
	}
	for(int i=0;i<len;i++){
		for(int j=0;j<(1<<len);j++){
			if((j>>i)&1)dp[j]+=dp[j^(1<<i)];
		}
	}
	int ans=0;
	
		for(int j=0;j<N-3;j++){
			int x=(1<<len)-1-j;
			//cerr<<dp[x]<<endl;
			ans^=((n-dp[x])*(n-dp[x]));
		}
	
	cout<<ans<<endl;
}

Codechef-COVERING Covering Sets CodeChef

题意：$r_i=\sum_{i\&(a|b|c)=i}{f_ag_bh_c}$，求$\sum_0^{2^n-1}{r_i}(1\le n \le 20)$。

Sol：可参考大佬博客CodeChef COVERING - Covering Sets 题解 - ycx060617 - 博客园 (cnblogs.com)

我的理解：首先考虑无法直接$r_{i}$一个一个计算，我们考虑从可能贡献的值的出现次数入手，对于一个数，它贡献的次数，就是它作为别人超集的个数，就是它的子集个数，也就是它的二进制位为1的个数。那么接下来考虑哪些数可能作为值域，显然我们不可能暴力枚举。对于这种位运算的希望求某一点的单值，一般都是先求高维前缀和，再倒着差分减回去得到单点值，但这样做的时候复杂度时间复杂度就大大降低了。

int n, m;
int a[N];
int f[N],g[N],h[N];
int sum[N];
int cal(int x){
	return 1LL<<__builtin_popcountll(x);
}
void solve(){
	cin>>n;
	for(int i=0;i<(1<<n);i++)cin>>f[i];
	for(int i=0;i<(1<<n);i++)cin>>g[i];
	for(int i=0;i<(1<<n);i++)cin>>h[i];
	for(int i=0;i<n;i++){
		for(int j=0;j<(1<<n);j++){
			if((j>>i)&1){
				
				f[j]=(f[j]+f[j^(1<<i)])%mod;
				g[j]=(g[j]+g[j^(1<<i)])%mod;
				h[j]=(h[j]+h[j^(1<<i)])%mod;
				
				
				}
		}
	}
	for(int i=0;i<(1<<n);i++)sum[i]=f[i]*g[i]%mod*h[i]%mod;
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<(1<<n);j++){
			if((j>>i)&1)sum[j]=(sum[j]+mod-sum[j^(1<<i)])%mod;
		}
	}
	int ans=0;
	for(int i=0;i<(1<<n);i++){
		ans+=sum[i]*cal(i);ans%=mod;
	}
	cout<<ans<<endl;
}

Codeforces F. Bits And Pieces（位运算） - Cold_Chair - 博客园 (cnblogs.com)

题意：给定 $n$ 个数的数组 $d$，找到 $i\lt j\lt k $ 的 $i,j,k$，使得 $d_i|(d_j \& d_k)$ 最大

Sol：对于这样的多循环变量，要么就是直接枚举一维，其他方法解决其他维。还有就是直接换角度，算贡献和次数。

位运算的比较基本的题。

考虑枚举i，然后二进制位从大到小考虑， 对于第𝑤位，如果$a_{i}[w]$=1，那么对𝑗、𝑘并没有什么限制。

如果$a_{i}[w]$=0，那么我们希望$(a_{j}\&a_{k})[w]=1$，结合前面的限制，就是给定x，问有没有$x∈𝑎[𝑗]\&𝑎[𝑘](𝑖<𝑗<𝑘)$,这个x需要满足前面高位为1限制还要满足当前位为1的限制。再考虑需要满足j，k严格大于i，我们需要满足对于一个集合的超集的最大位置和次大位置（在数组中的下标靠后）

int n, m;
int a[N];
const int N = 1<<21;
const int len=21;
int f[N+5];
int g[N+5];
//权值数组映射到位置，维护一个值对应最大位置，次大位置
void add(int val,int pos){
	if(f[pos]<val){
		g[pos]=f[pos];
		f[pos]=val;
	}
	else if(g[pos]<val)g[pos]=val;
}
void solve(){
	//cerr<<__lg(N)<<endl;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		add(i,a[i]);
	}
	for(int i=0;i<len;i++){
		for(int j=0;j<(N);j++){
			if(((j>>i)&1)==0){
			add(f[j^(1<<i)],j);
			add(g[j^(1<<i)],j);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n-2;i++){
		int x=0;
		for(int j=len-1;j>=0;j--){
			if((a[i]>>j)&1)continue;
			x+=1<<j;
		//满足前面条件和当前条件的数的超集对应次大位置需要大于i
			if(g[x]<=i)x-=1<<j;
			
		}
		ans=max(ans,a[i]|x);
	}
	cout<<ans<<endl;
}