首页 > 其他分享 >高维前缀和 (SOSDP)

高维前缀和 (SOSDP)

时间:2024-09-02 19:03:19浏览次数:13  
标签:前缀 二进制 int SOSDP 求和 子集 高维

算法介绍——高维前缀和

引入

我们都知道二维前缀和有这么一个容斥的写法:

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] \]

非常的繁琐,于是就诞生了如下二维前缀和的写法:

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];
    }
}

其实就是先统计列的前缀和,再统计行的前缀和。
那三维前缀和只需要三遍 forforfor 就搞定了,明显简单很多。

这就启发我们对于更高维度的前缀和,同样只需要做 \(n\)遍\(n\)层 for 循环

正文

对于上面的 \(n\)遍\(n\)层for循环 的高维前缀和的代码,其复杂度显然不是我们能接受的,但是当每一维很小时就可以进行状态压缩
最常见的就是每一维的大小为 \(2\) ,此时对于\(L\) 维数组就可以用一个长度为 \(L\) 的二进制数表示其中一个位置。

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)];
         }
    }
}

时间复杂度\(O(L\times2^L)\)

子集求和

对于一个二进制数 \(j\) ,如果另一个二进制数 \(i\) 满足,\(i \operatorname{and} j=i\) , 就说 \(j\) 包含 \(i\) , 即 \(i\) 是 \(j\) 的子集。
那上面的代码相当于对每一个 \(j\) 加上它的所有子集,我们称它为 子集求和

超集求和

对于一个二进制数 \(j\) ,如果另一个二进制数 \(i\) 满足,\(i \operatorname{or} j=i\) , 此时 \(i\) 包含 \(j\) , 即 \(j\) 是 \(i\) 的子集,此时我们称 \(i\) 是 \(j\) 的超集
与子集求和类似的,我们有如下 超集求和 代码:

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)];
        }
    }
}

应用

高维前缀和是计数的常用技巧,因此也被称为SOSDP

其他

高维前缀和有时会配合Lucas定理使用,参见Lucas定理入门


例题

Compatible Numbers

\(a \operatorname{and} b = 0\) 等价于 \(a\) 是 \(b\) 的补集的子集,因为题目要求输出任意一个答案,所以只要把上述子集求和的代码中得加操作改成赋值操作即可。

#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];   //计算补集 
		if(f[b]) printf("%d ",f[b]);
		else printf("%d ",-1);
	}
	return 0;
}

[ARC137D] Prefix XORs

设 \(A_{i,j}\) 表示第 \(j\) 次操作后 \(A_i\) 的值,根据常识或手推可以知道:

\[A_{n,k}=\oplus^n_{i=1} C^{k}_{n-i+k} \cdot A_{i,0} \]

因为偶数个 \(A_i\) 异或起来的的结果为\(0\),所以 \(A_{i,0}\) 对 \(A_{n,k}\) 有贡献当且仅当 \(C^{k}_{n-i+k}\) 为奇数,即 $ C^{k}_{n-i+k} \equiv 1 \pmod 2 $,根据 Lucas 定理可知,此时 \(k\) 是 \(n-i+k\) 的子集,即 $k \operatorname{and} (n-i) = 0 $,用高维前缀和预处理即可

#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开始 
		printf("%d ",f[((1<<20)-1)^k]);   //求补集的答案 
	}
	return 0;
}


标签:前缀,二进制,int,SOSDP,求和,子集,高维
From: https://www.cnblogs.com/FloatingLife/p/18393314

相关文章

  • CF 1996 E. Decode(*1600) 思维+前缀和
    CF1996E.Decode(*1600)思维+前缀和题目链接题意:给你一个长度为\(n\)的二进制字符串,求出所有的子区间的所有满足\(0\)的个数等于\(1\)的个数的子区间个数之和。思路:首先,求一段区间是否满足\(0\)的数量是否等于\(1\)的个数,是非常经典的做法,我们只需要维护一个数......
  • luoguP5369 [PKUSC2018] 最大前缀和
    题目n<=20题解想了半天3位状态的折半,然后发现空间开不下(时间也不太行)所以放弃思考,直接枚举答案答案是a中的一个集合,设为S;记集合S的和为sum[S]考虑当S确定时,有多少种方案能使答案恰好为sum[S]。为了处理多种sum相同的情况,记S为从前往后考虑,第一次出现最大ans的集合;记剩余部......
  • Nuxt3 全局变量接口前缀全局配置,全局方法,全局状态管理
    接口前缀全局配置,全局变量1.像api前缀这类的全局变量一般配置在nuxt.config.ts文件中。如下:nuxt.config.ts可以在public下定义全局变量,且public下的变量可以在客户端和服务端使用在其他任意vue或者js、ts文件中,可通过以下方式获取变量const{public:{apiBase}}=u......
  • (算法)最⻓公共前缀————<链表—模拟>
    1.题⽬链接:14.最⻓公共前缀2.题⽬描述:3.解法:算法思路:解法⼀(两两⽐较):我们可以先找出前两个的最⻓公共前缀,然后拿这个最⻓公共前缀依次与后⾯的字符串⽐较,这样就可以找出所有字符串的最⻓公共前缀。C++算法代码: classSolution{public: stringlongestCommonPr......
  • 【数据结构-前缀异或和】力扣1177. 构建回文串检测
    给你一个字符串s,请你对s的子串进行检测。每次检测,待检子串都可以表示为queries[i]=[left,right,k]。我们可以重新排列子串s[left],…,s[right],并从中选择最多k项替换成任何小写英文字母。如果在上述检测过程中,子串可以变成回文形式的字符串,那么检测结果为......
  • ZBlog的数据库表是可以设置前缀-修改ZBlog数据库前缀
    ZBlog的数据库表是可以设置前缀,程序安装的时候默认是zbp_,所以很多同学也就默认用了zbp_,但是因为某些原因需要修改ZBlog数据的前缀。例如烽烟前几天搭建了几个演示站,多个演示站都使用的是一个数据库,但是由于之前的演示站数据表也是默认的zbp_,这样的话就与现在存在的网站数据表......
  • 「字符串」前缀函数|KMP匹配:规范化next数组 / LeetCode 28(C++)
    概述为什么大家总觉得KMP难?难的根本就不是这个算法本身。在互联网上你可以见到八十种KMP算法的next数组定义和模式串回滚策略,把一切都懂得特别混乱。很多时候初学者的难点根本不在于这个算法本身,而是它令人痛苦的百花齐放的定义。有的next数组从0下标开始,有的从1开始;有的表......
  • 汇编语言的神秘面纱:指令前缀的深度解析
    标题:汇编语言的神秘面纱:指令前缀的深度解析在计算机编程的底层世界中,汇编语言以其接近硬件的特性,扮演着至关重要的角色。指令前缀是汇编语言中一个关键的概念,它为指令提供了额外的信息,使得程序能够执行更加复杂和灵活的操作。本文将深入探讨指令前缀的作用、类型以及如何在......
  • 【C++二分查找 前缀和 】1292. 元素和小于等于阈值的正方形的最大边长
    本文涉及的基础知识点C++二分查找C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频LeetCode1292.元素和小于等于阈值的正方形的最大边长给你一个大小为mxn的矩阵mat和一个整数阈值threshold。请你返回元素总和小于或等于阈值的正方形区......
  • zblog该数据库里已存在相关的表和数据,请更改表前缀或是更换清空数据库再安装
    问题原因:其实这个提示已经说的很清楚了。意思就是之前你应该安装过zblog程序,所以你的数据库里面已经存在了zblog数据表。再次安装的时候因为表名是一样的所以会冲突,就会出现这个提示。解决办法:第一种:填写数据库信息的时候修改下表前缀,如下图:该数据库里已存在相关的表和数据,请......