【精选】前缀和の超级进化——SOS-DP & FMT/FWT

· · 个人记录

前缀和の超级进化——SOS-DP & FMT

作者 SMT0x400，版权本人所有，允许转载。

0.说句闲话：研究本文的最好方式是

浅谈前缀和的非常好写法 - DengDuck の Blog - 洛谷博客 (luogu.com.cn)

SOSdp - 果冻的博客 - 洛谷博客 (luogu.com.cn)

FWT 学习笔记 - _Famiglistimo - 博客园 (cnblogs.com)

或多或少地参考了以上三位大佬的博客。感谢 @Jelly_prx 和 @Dengduck ！

0.1 本文定位

属于一篇有一定门槛的科普文。需要学会高维前缀和的写法。

对于 提高组 选手而言，只要会一点点集合符号和容斥原理即可学会 SOS-DP。

对于 省选/NOI 选手而言，这篇文章可以扩展到 FWT/FMT，是一个常用的位运算卷积的技能点。

0.2 规定

数组下标为了方便写式子，统一使用方括号而不是下标。

1.引入：高维前缀和

1.1 普通前缀和 / 差分

普及组知识：我们一般利用前缀和来解决一些 O(n) 预处理 O(1) 查询的题目，比如查询区间和为多少，不带修改。

另外，使用差分打标记+前缀和最后计算，来解决 O(1) 修改，O(n) 查询的题目。

我们考虑把它丢到二维平面上，若是我要计算 (i,j) 左上角所有数的和，那么公式是

这个式子不长，很短很好写。 --- 但是如果我把它扩展到三维的情况呢？此时就需要一个个容斥展开了。 我直接再写个三重循环做容斥系数不就行了吗。 进一步：要是我的维度是 $k$ 维呢？ 我再写个 $k$ 重循环容斥不就行了吗。时间复杂度是 $O(2^k n)$（其中 $n$ 为点数）。 但是，这里介绍一种好写又好想的做法，只需要 $O(kn)$ 的时间复杂度。 ---- 不要局限于眼前的二维和三维，我们要**泛化维度**思想。 考虑外层一个循环，循环 $k$ 次，每一次枚举一个低维，从这个低维转移过来。 那么代码很简单，有待补充。 我们的“维度”需要保证相互独立，不能交叉，否则会出现问题。 ## 2.SOS-DP 的引入 在此先卖个关子，不直接讲 SOS-DP，但是先来做一道题： ### 狄利克雷前缀和 给定 $a$ 数组，要求求 $b[i]=\sum _{d|i}a[d]$，算法时间复杂度要求线性。 天然地想到：枚举每个**质数**，作为前缀和转移的“维度”。因为是**质数**作为维度，所以它们之间**相互独立**。 所以无需直接枚举因子，枚举质数 $i$，然后每次 $f[S\div i]\to f[S]$。 于是很快就能写出这样的代码。 ```cpp I sd;inline I g(){return sd^=sd<<13,sd^=sd>>17,sd^=sd<<5,sd;} const I N=2e7+10; I n,a[N],ans,pr[N/10],m; bool p[N]; signed main(){ n=in();sd=in(); fo(i,1u,n)a[i]=g(); fo(i,2u,n){ if(!p[i])pr[++m]=i; for(I j=1;j<=m&&1ll*pr[j]*i<=1ll*n&&(p[i*pr[j]]=1,i%pr[j]!=0);++j);} fo(i,1u,m)for(I j=pr[i],k=1;j<=n;j+=pr[i],++k)a[j]+=a[k]; fo(i,1u,n)ans^=a[i]; return printf("%u",ans),0;} ``` 这和我们今天所探讨的子集求和、子集卷积没有半毛钱关系，但是“泛化维度”思想对我们而言，又是一把处理位运算的利剑。 好了，回归正题，讲讲 SOS-DP 能解决啥问题。 子集求和：给定 $g$，需要求这样的一个数组 $f$，$f[S]=\sum_{T\subseteq S}g[T]$。 我们可以 $O(3^n)$ 直接暴力枚举子集算贡献，代码很简单就不放了。 在 $n\le 16$ 的情况下都可以这么做。 但是，它不够快，也不够优美。很多贡献，都是重复的，等待着我们去优化。 这里的“求和”其实**不是严格意义上的求和**，取 $\min,\max$ 甚至更多奇怪的操作，也是可以的。 ## 3.SOS-DP 的流程 回顾一下我们的算法目标：$f[S]=\sum_{T\subseteq S}g[T]$；（子集卷积是 $\sum_{T\subseteq S} g[T]h[\complement_S T]$，不一样的） 那么我们不妨利用 $S$ 的子集去处理。 则 ${f[S]=g[S]+\sum _{i\in S}f[\complement_S \{i\}]}$。 会不会有重复呢？可能会有。所以我们需要钦定外层的枚举顺序，先枚举 $i$，再枚举 $S$。 这样每个 $f[S]$ 其实就是对于 $i$ 维的一个子集之和，每次新来一个 $i$ 都把不相关的两个集合合并了，它是高效且正确的。 代码很好写：（这里的 `mrg` 函数就是“求和”函数，前面说了，不仅仅可以是加法） ```cpp fo(i,0,n-1)fo(j,0,ns) if(j&(1<<i))mrg(f[j],f[j^(1<<i)]); ``` --- 既然子集求和有了，再来讲超集求和。理论上超集卷积原理和子集卷积一样，详见 FWT（但是我并不会）。 算法目标：$f[S]=\sum_{T\supseteq S} g[T]$。 那么 ${f[S]=g[S]+\sum _{i\notin S}f[\complement_S \{i\}]}$。 --- OK，这两个类似，接下来看多点题目。 ## 4.SOS-DP 的例题 ### ARC100E Or Plus Max 题意：对于每个 $k$ 求 $\max(A_i+A_j)[i<j,i\operatorname{or} j\le k]$。已经有下标的形式了，就不需要转下标了。 我们观察一下 $i\operatorname{or} j\le k$ 是啥。直接做十分不好弄。 于是考虑一个这样的事情：令 $i,j\subseteq k$ 那么 $i\cup j\subseteq k$。显然，若 $i\subseteq k$，则 $i\le k$。 所以这题就变成了对于每个 $k$ 求其子集中某两种不同编号子集的最大值。再理清楚一点，就是维护子集中前两大的 $a$ 值。 化成子集求和的形式，$a[S]\to f[T]$，其中 $S\subseteq T$。然后直接套用子集求和的 SOS-DP，这题就结束了。 ```cpp #include<bits/stdc++.h> #define fo(i,a,b) for(auto i(a),_ei(b);i<=_ei;++i) #define gch(w) for(;w(CH);CH=getchar()) using I=int;using V=void;using LL=long long;I FL,CH;LL in(){LL a(0);FL=1;gch(!isdigit)FL=(CH=='-')?-1:1;gch(isdigit)a=a*10+CH-'0';return a*FL; }using namespace std; const I NS=262144; #define pii array<I,2> pii f[NS];I n,ns,mx; V mrg(pii&a,pii b){ array<I,4>c={a[0],a[1],b[0],b[1]}; sort(&c,&c+4);a={c[3],c[2]};} I main(){n=in();ns=(1<<n)-1; fo(i,0,ns)f[i][0]=in(); fo(i,0,n-1)fo(j,0,ns)if(j&(1<<i))mrg(f[j],f[j^(1<<i)]); fo(i,1,ns)printf("%d\n",mx=max(mx,f[i][0]+f[i][1])); return 0; } ``` ### CF1208F [Bits And Pieces](https://www.luogu.com.cn/problem/CF1208F) 题意：给定 $n$ 个数的数组 $d$，找到 $i\lt j\lt k $ 的 $i,j,k$，使得 $d_i|(d_j \& d_k)$ 最大。 我们观察实际上更能满足条件的是进制位，于是考虑令 $a_{d_i}=i$ 然后转移。 --- 再来理清一下问题。现在我可以枚举 $k$，然后判断一个 $x$，其中 $x$ 是等于某两个元素组成的，要求组成 $f[x]$ 的那两个元素编号尽可能大。 所有进制都有一个套路，考虑从高到低位构造 $k|x$ 这个值，就能让这个值最大化。 设 $k[i]$ 为 $k$ 二进制下从低到高第 $i$ 位。 若 $k[i]=1$ 的时候，不用管它，直接跳过；（这里**不需要强制填数**）； 若 $k[i]=0$ 的时候，判断有没有一个 $x$ 能够使得**填数的位**都能做到 $1$。如果能就最好，不能就算了。 具体而言，设当前填的答案 $ans$ 只算到了第 $i$ 位，令低位的先不填，当前的填上，然后算 $ans$ 的超集即可。 如果它的超集的次大坐标大于 $i$，则可以保留；否则不可以保留，直接把这位变成 $0$。 为什么要算超集？很显然：因为超集保证一定满足该填的都填了，不该填的也可能填。 --- 问题就被我们转化成了：计算 $f[x]$，对于 $x$ 超集“求和”，依此更新答案。于是维护最大坐标和次大坐标就行了。有些小细节，需要注意。 ```cpp #include<bits/stdc++.h> #define fo(i,a,b) for(auto i(a),_ei(b);i<=_ei;++i) using I=int;const I N=1<<21;using namespace std; I n,mxa,lgn,a[N],Mans,pn; #define I2 array<I,2> void mrg(I2&a,I2 b){ array<I,4>c={a[0],a[1],b[0],b[1]}; sort(c.begin(),c.end());a={c[3],c[2]};}I2 f[N]; I main(){ios::sync_with_stdio(0);cin.tie(0); cin>>n;pn=n; fo(i,1,n)cin>>a[i],mrg(f[a[i]],{i,0}),mxa=max(mxa,a[i]); for(n=1;n<=mxa;n<<=1,++lgn); fo(i,0,lgn-1)for(I j=n-1;j>=0;--j) if(!(j&(1<<i)))mrg(f[j],f[j^(1<<i)]); fo(i,1,pn-2){I ans(0); for(I k=lgn-1;~k;--k){ if((a[i]>>k)&1)continue; ans|=1<<k; if(f[ans][1]<=i)ans^=1<<k;} Mans=max(Mans,ans|a[i]);} return printf("%d\n",Mans),0; } ``` 这个题目给我们的思考规律就是： 1. 值和下标互相转化。 2. 考虑一个复杂的条件，转为子集（主要是 $\operatorname{or}$）或者超集（主要是 $\operatorname{and}$）。 3. 直接 SOS-DP。 ### [CF383E Vowels](https://www.luogu.com.cn/problem/CF383E) 题意：给出 $n$ 个长度为 $3$ 的由 $\texttt{a}\sim\texttt{x}$ 组成的单词，一个单词是正确的当且仅当**其包含至少一个元音字母**。 这里的**元音字母**是 $\texttt{a}\sim\texttt{x}$ 的一个**子集**。对于**所有**元音字母**集合**，求这 $n$ 个单词中**正确单词的数量平方**的 **异或和**。 --- 按照套路，首先先丢进桶里面统计个数。观察 $n$ 很小，字母数量很大。 --- 考虑对于 $S$ 集合统计答案。 **至少一个？那么就相当于取一个没有的补集！**求对于 $S$ 集合中元音字母一个没有的方案数。（直接用 $n$ 减去它即为答案）。 再次转化，因为我丢的桶不好搞，那么就求对于 $\complement_U S$ 的所有子集方案数。 然后直接做子集求和即可。 ---- ### CF449D Jzzhu and Numbers 题意：有 $n$ 个二进制数字，每个数字 $m$ 位，求选择一些数 and 起来，恰好等于 $0$ 的方案数，取模 $10^9+7$。 先用 SOS-DP 解决问题。 设 $a[i]$ 为数字选 $i$ 有多少种方案，维护 $b[i]$ 为数字选 $i$ 的**超集**有多少种方案。 很明显，若目标集合为 $S$，则**选择 $S$ 的超集的**方案数应该为 $g[S]=2^{b[S]}-1$ 种（一定要选，所以要减 $1$）。 于是再差分回去，即为答案。差分只需要变动符号。 --- 观察到和 FWT 的 and 很像，确实是这样的。这就是 FWT 的另一种实现。 ```cpp #include<bits/stdc++.h> #define fo(i,a,b) for(auto i(a),_ed(b);i<=_ed;++i) #define gch(k) for(;(k);CH=getchar()) using namespace std;using I=int;using LL=long long;using V=void;I FL,CH;LL in(){LL a=0;FL=1;gch(!isdigit(CH))FL=(CH=='-')?-1:1;gch(isdigit(CH))a=a*10+CH-'0';return a*FL;} const I mod=1e9+7,NS=1<<20; struct mo{I x;mo(I a=0){x=a;if(x<0)x+=mod;if(x>=mod)x-=mod;} mo operator +(mo a){return x+a.x;} V operator +=(mo a){x+=a.x;if(x<0)x+=mod;if(x>=mod)x-=mod;} mo operator *(mo a){return 1ll*x*a.x%mod;} }f[NS]; I n,ns; mo ksm(mo x,I k){mo a(1); for(;k;k>>=1,x=x*x)if(k&1)a=a*x; return a;} V fwt(mo*a,I op){ fo(i,0,n-1)for(I j=ns;~j;--j)if(!(j&(1<<i)))f[j]+=mo(op*f[j^(1<<i)].x);} I main(){fo(i,1,(n=in()))++f[in()].x; ns=NS-1;n=20;fwt(f,1); fo(i,0,ns)f[i]=ksm(2,f[i].x)+mo(mod-1); fwt(f,-1);printf("%d\n",f[0].x); return 0;} ``` ### [P6442 [COCI] KOŠARE](https://www.luogu.com.cn/problem/P6442) 题意：有 $n$ 个二进制数字，每个数字 $m$ 位，求选择一些数或起来，恰好等于 $2^{m}-1$ 的方案数，取模 $10^9+7$。 --- 按照套路，一个个转移是没必要而且无所谓的，每个数字的位置也是没有影响的，所以丢进桶里面，给次数加上 $1$。 直接转为补集，然后就成了 CF449D。 --- 这里考虑直接算。设 $a[S]$ 为数字集合为 $S$ 的方案数（原始的那个桶）。 设 $b[S]$ 为数字集合**通过位与操作**做到集合为 $S$ 的**子集**的方案数。 这里的 $b[S]$ 不好直接算，但是我们可以先给 $a[S]$ 做一遍子集求和，仍然在 $a$ 数组上。 按照套路，我们可以对 $b[S]$ 本身直接容斥最后算答案，也可以对 $b[S]$ 差分。差分具体就见 CF449D 了，就是改个符号的事情。 ## 5.FWT/FMT 的引入 FMT 是“**快速莫比乌斯变换**”，思想基于容斥+DP，它的长相你等会就知道了。 FWT 是“**快速沃尔什变换**”，它的运行结果和 FMT 一模一样。 FWT 思想可以支持异或卷积，这里暂时不讲。因为本文主要在于 SOS-DP 的缘故，所以主要讲 FMT。FWT 打法类似，只是长相更像 FFT，这里不讲。 ### 5.1 它能解决什么问题 首先定义一个东西，叫做“集合幂级数”。它可不是什么形如 $x^2+2x+1$ 的“形式幂级数”多项式，但是也是和多项式紧密相关的。 既然是多项式，那么就有“卷积”。它的“卷积”操作无非就是 ${c[i]=\sum_{j \operatorname{op} k=i} a[i]b[j]}$。 这里的 $\operatorname{op}$ 指一类集合运算（计算机里面，通常是位运算）。比如**且**、**或**和**异或**。 我们就是需要通过 FWT/FMT 高效的时间效率，来优化一系列“卷积”的问题。 ### 5.2 和 FFT 有什么关系 普通多项式卷积的式子是 ${c[i]=\sum_{j+k=i}a[j]b[k]}$。 考虑它一般拿来做卷积的流程。 1. 使用 DFT，转化为点值序列；时间 $O(n\log_2 n)$。 2. 在点值序列上做乘法操作；时间 $O(n)$（取决于具体你做了什么操作）。 3. 使用 IDFT，将点值序列，转化回普通形式幂级数形式，就是那个形如 $x^2+2x+1$ 的那个形式。 这里就是我们拿 FFT 优化一系列多项式毒瘤题目的过程。 考虑 FWT/FMT 的过程，若我们把这个序列，通过一种类似于 DFT 的变换，变为“点值”的形式，就可以做到比较快速的乘法。 我们就需要**找到一种**对于原序列的**变换**，使得 $\operatorname{FWT}(A)\times \operatorname{FWT}(B)=\operatorname{FWT}(C)$。 ## 6.FMT \& IFMT 算法 以下过程，设 $2^n$ 为序列长度，序列从 $0$ 开始。其最大下标位数为 $2^{n}-1$。 前面做了那么多 SOS-DP 的题目，FMT 大家应该就更加容易做了吧。 ### 6.1 或卷积 别急，一个个来。 首先设 $a'=\operatorname{FWT}(a)$ 为 $a$ 序列经过 FWT 变换之后的序列是啥。 这里的序列变换，则是变为序列 $a'[i]=\sum_{j\subseteq i}a[i]$（注意符号）。 咦？这么那么眼熟？ 发现就是我们的老朋友——**子集求和**！ 于是我们只需要做子集求和即可。 我们要求还原，怎么办？老规矩，前缀和过来就给它**差分**回去！ 这里**子集差分**的大致流程请看 CF449D，就是改个符号的事情。实在不懂就去做 ABC322E，可回撤的背包方案数问题，包你满意。 于是我们就搞定了 `or` 运算的 FMT 和 IFMT 流程。 我们再来回顾以下求的是什么，求的是 $c[i]=\sum_{j\cup k=i} a[j]b[k]$。 考虑 $j\cup k=i$ 的必要条件，必然有 $j,k\subseteq i$。 那么根据乘法原理，直接让 $c[i]=(\sum_{j\subseteq i}a[j])(\sum_{j\subseteq i}b[j])=a'[i]b'[i]$ 就是对的吗？ 实际上不是。因为 $c[i]$ 实际上还算上了它子集的答案。 那么怎么办呢？就把 $c$ 数组容斥一下，剔除不该有的东西就好了。 咦？这不就是我们子集差分的流程吗，它也叫做 IFWT。 所以，我们就用 SOS-DP 优雅地解决了问题，并且从 SOS-DP 的角度思考，证明了这个 FWT 变换的正确性。 代码也很好写。等会统一放。 ### 6.2 且卷积 按照 SOS-DP 的套路，也容易思考，这里的 FWT 变换是**超集求和**。 同理，这里的 IFMT 变换无非就是**超集差分**。下面来证明它的正确性。 假设我要让 $c[i]$ 满足 $c[i]=\sum_{j\cap k=i}a[j]b[k]$。 老规矩，先考虑必要条件：$j,k\supseteq i$。然后超集求和一波，设 $c'[i]=a'[i]b'[i]$。 发现 $c'$ 算多了！于是用超集差分搞掉就行了！代码也很短！ 于是我们又用 SOS-DP 优雅地搞掉了这一问！ ### 6.3 子集卷积 先明确问题： $${c[i]=\sum_{j\subseteq i}a[j]b[\complement_i j]}$$ 显然可以 $O(3^n)$ 做，但是太慢了，我要更快！ 考虑把子集卷积的形式拆开：若 $j$ 包含于 $k$，且 $i$ 为补集，则 $i\cup j=k$ 且 $ i\cap j=0$。 考虑先来解决第一个问题。第一个问题可以 FMT/FWT 的子集求和解决。 但是第二个问题我们发现只用 FMT 还会算重，那么怎么办呢？ 于是我们就不直接加到最终的集合，考虑这样一件事情，$|i|+|j|=|i+j|$，于是按照集合大小，再开一维，维护即可。 这样就不会算重了。于是问题就结束了。 ```cpp #include<bits/stdc++.h> #define fo(i,a,b) for(auto i(a),_ed(b);i<=_ed;++i) #define gch(k) for(;(k);CH=getchar()) using namespace std;using I=int;using LL=long long;using V=void;I FL,CH;LL in(){LL a=0;FL=1;gch(!isdigit(CH))FL=(CH=='-')?-1:1;gch(isdigit(CH))a=a*10+CH-'0';return a*FL;} const I mod=1e9+9; struct mo{I x;mo(I a=0){x=a;if(x<0)x+=mod;if(x>=mod)x-=mod;} V operator +=(const mo&a){x+=a.x;if(x>=mod)x-=mod;} mo operator *(const mo&a){return 1ll*x*a.x%mod;}}; using VI=vector<mo>; #define pc __builtin_popcount VI convo(I n,VI&A,VI&B){ auto fmt=[&](I n,VI&f,mo id){ fo(i,0,n)fo(j,0,(1<<n)-1)if((j>>i)&1)f[j]+=id*f[j^(1<<i)];}; VI a[n+1],b[n+1],c[n+1];fo(i,0,n)a[i].resize(1<<n),b[i].resize(1<<n),c[i].resize(1<<n); fo(i,0,(1<<n)-1)a[pc(i)][i]=A[i],b[pc(i)][i]=B[i]; fo(i,0,n)fmt(n,a[i],1),fmt(n,b[i],1); fo(i,0,n)fo(j,0,i)fo(k,0,(1<<n)-1)c[i][k]+=a[j][k]*b[i-j][k]; fo(i,0,n)fmt(n,c[i],mo(-1)); VI C(1<<n,0);fo(i,0,(1<<n)-1)C[i]=c[pc(i)][i]; return C;} I main(){I n=in();VI a(1<<n),b(1<<n); fo(i,0,(1<<n)-1)a[i]=in(); fo(i,0,(1<<n)-1)b[i]=in(); VI c=convo(n,a,b); for(mo i:c)printf("%d ",i.x); return 0;} ``` ### 6.4 异或卷积以及其他 这些算法是 FWT 的内容了，由于作者水平所限，此文不涉及。 ## 7.致谢 谢谢大家的观看。