算法介绍——高维前缀和引入我们都知道二维前缀和有这么一个容斥的写法:for(inti=1;i<=n;i++){for(intj=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[

从子集和问题到and卷积枚举子集：\(O(3^{n})\) intu=15; for(ints=u;s;s=(s-1)&u){ b=s; cout<<b<<endl;}/*111111101101110010111010100110000111011001010100001100100001*/子集和问题参考好的博客https://ottffyzy.github.io/algos/dp/s

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(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可以把时

介绍一维前缀和:$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

高维前缀和众所周知，一维前缀和即\(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用来解决这种问题：对于非负整数\(i\)，\(K\)，定义布尔型二元运算\(i\subseteqK\)，可以以下四种等价角度理解：\(i\operatorname{bitand}K=i\)。\(\operatorname{bitand}\)是按位与的意思。同一个二进制位上，\(i\)的这一位小于等于\(K\)的这一位。同一个二进制位上，\(

高维前缀和(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可以做的题目：对子集/超集的dp，这里对子集相关的部分做一下分析参考资料设\(f[mask][i]\)表示从低到高考虑到\(mask\)的第\(i\)位（从0开始算），而且这\(i+1\)

问题引入：对于两个数组\(a\)，\(b\)，长度为\(2^n\)，从\(0\)开始标号。求\(c_i=\sum\limits_{p\&q=i}a_pb_q\)。关于这个问题的求解，我们可以使用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_{(

前几天做arc时连做两道高维前缀和，今天去看dp题单时发现这东西居然叫sosdp，来刷一下板子。粘一篇找到的blog，感觉引入那里非常自然！linktoCF|linktoLuogu给