首页 > 其他分享 >SOSdp

SOSdp

时间：2024-05-18 16:10:30浏览次数：27  
标签：前缀 int sum SOSdp 子集 我们 dp

从子集和问题到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，然后二进制位从大到小考虑， 对于第

标签：前缀,int,sum,SOSdp,子集,我们,dp
From： https://www.cnblogs.com/mathiter/p/18199404

相关文章

  • SOSDP
    SOSDP(SumOverSubsetsDynamicProgramming)，中文名子集DP。下面给个common的用法：给定一个集合\(S=\{a_0,a_1,\dots,a_{n-1}\}\)，求：\[\sum_{T\subseteqS}\sum_{a_i\inT}a_i\]即\(S\)的子集和。暴力做是\(\mathcalO(3^n)\)的，而用SOSDP可以把时间复......
  • SOSDP
    SOSDP(SumOverSubsetsDynamicProgramming)，中文名子集DP。下面给一个最Common的用法：给定一个集合\(S=\{a_0,a_1,\dots,a_{n-1}\}\)，求：\[\sum_{T\subseteqS}\sum_{a_i\inT}a_i\]即\(S\)的子集和。暴力做是\(\mathcalO(3^n)\)的，而用SOSDP可以把时......
  • 高维前缀和 (SOSDP)
    介绍一维前缀和:$s[i]=s[i-1]+a[i]$二维前缀和:$s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]$当然也可以这么写:for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)a[i][j]+=a[i-1][j];for(inti=1;i<=n;i++)for......
  • 「升维打击」- 高维前缀和与 SOSDP
    高维前缀和众所周知，一维前缀和即\(s_i=\sum\limits_{p=1}^ia_p\)，二维前缀和则是通过容斥原理来求：由图，显然可以得到\(s_{i,j}=a_{i,j}+s_{i-1,j}+s_{i,j-1}+s_{i-1,j-1}\)。那么，同理推到三维，可以得到\(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-......
  • SoSdp 学习笔记
    SoSdp用来解决这种问题：对于非负整数\(i\)，\(K\)，定义布尔型二元运算\(i\subseteqK\)，可以以下四种等价角度理解：\(i\operatorname{bitand}K=i\)。\(\operatorname{bitand}\)是按位与的意思。同一个二进制位上，\(i\)的这一位小于等于\(K\)的这一位。同一个二进制位上，\(......
  • 高维前缀和(SOSDP)
    高维前缀和(SOSdp)AXorBProblemagain二维前缀和for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)s[i][j]=s[i-1][j]+s[i][j-1]-......
  • 对 sosdp 的一些理解
    sosdp可以做的题目：对子集/超集的dp，这里对子集相关的部分做一下分析参考资料设\(f[mask][i]\)表示从低到高考虑到\(mask\)的第\(i\)位（从0开始算），而且这\(i+1\)......
  • Trick 8：子集卷只因的 SOSDP 做法
    问题引入：对于两个数组\(a\)，\(b\)，长度为\(2^n\)，从\(0\)开始标号。求\(c_i=\sum\limits_{p\&q=i}a_pb_q\)。关于这个问题的求解，我们可以使用SOSDP完成一系列......
  • 高维前缀和与 SOSDP
    高维前缀和高维前缀和，就是对每一个高维空间的点\((a_1,a_2,\cdots,a_k)\)，求\(\displaystyle\sum_{b_1=0}^{a_1}\sum_{b_2=0}^{a_2}\cdots\sum_{b_k=0}^{a_k}val_{(......
  • [数学记录][sosdp]CF449D Jzzhu and Numbers
    前几天做arc时连做两道高维前缀和，今天去看dp题单时发现这东西居然叫sosdp，来刷一下板子。粘一篇找到的blog，感觉引入那里非常自然！linktoCF|linktoLuogu给......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99