法嘛塔,或者说sos dp

有趣

Posted by ShanLunjiaJian's Blog on May 11, 2021

法嘛塔和sos dp说的都是子集前/后缀和,用来求解一类这样的问题 :

给出\(g\),求

\[f(S)=\bigoplus_{T\subseteq S}g(T)\]

,其中\(\oplus\)是任意交换律、结合律运算。

为什么要交换律?因为子集的枚举顺序很多,法嘛塔也不知道你要的是哪一种,并且一般情况下我们用到的运算都有交换律。

我的板子习惯和法法塔类似,写起来大概是

1
2
3
4
5
6
7
for(int l=2;l<=n;l<<=1)
{
	int mid=l>>1;
	for(int p=0;p<n;p+=l)
		for(int i=0;i<mid;i++)
			mod(A[p+mid+i]+=A[p+i]);//+ can be replaced by some operator you want
}

上面是子集前缀和,要求子集后缀和(超集和)只要把+=两边的东西反过来即可。

这个东西的过程可以理解为,\(2^k\)构成一个\(k\)维的立方体,我们依次处理每一维之间的贡献。


CF165E Compatible Numbers

考虑\(a,b\)相容,等价于\(b\in\operatorname{not}a\)。

我们记\(c_i\)为任意满足\(a_j=i\)的\(a_j\),如果没有这样的\(a_j\)则\(c_i=-1\)。

对\(c\)做子集前缀和,当然这里的\(a\oplus b\)定义为 : 如果\(a,b\)有一个不是\(-1\),结果是随便一个不是\(-1\)的,否则结果是\(-1\)。

我们得到的新的\(c_i\)的含义是\(c_i\)为任意满足\(a_j\in i\)的\(a_j\),于是对于每个数\(a_i\)输出\(c_{\operatorname{not}a_i}\)即可。


CF383E Vowels

注意到4s,所以\(O(\vert\Sigma\vert2^{\vert\Sigma\vert})\)完全能过。

把每个串状压成二进制,第\(i\)位是\(1\)当且仅当包含第\(i\)个字母。

每次询问要求有多少个单词包含元音字母集合的至少一个,你发现至少一个比较难受,不如反过来求一个也没有,然后用总数减去它。

一个也没有怎么求?跟上一题类似,就是求被 元音字母集合的补集 包含的单词个数。

设\(c_i\)表示有多少个单词状态是\(i\),做子集前缀和(\(\oplus=+\))之后就变成了有多少字母被\(i\)包含。每次询问直接输出答案即可。


CF449D Jzzhu and Numbers

我读错题/cy以为是构造方案/cy

显然是个背包,就是把所有\(z^U+z^{a_i}\)卷起来,当然\(U\)是全集。

直接卷复杂度是\(O(nv\log v)\),这很不好。

对每一个生成函数先进行一次FMT,然后直接拿点值扔进去卷,复杂度还是\(O(nv\log v)\)/jy,瓶颈在于求每一个FMT。

不过这个生成函数很简单,我们说不定可以直接求出它的FMT的结果。

你发现这个结果可以这么算 : 一开始全初始化成\(0\),然后\(U\)的所有子集\(+1\),然后\(a_i\)的所有子集\(+1\),这显然可以\(O(v)\)求。所以我们就可以\(O(nv)\)了。

可是这还是太慢了!

继续考虑上面的性质。更进一步,我们知道每次加入一个新的数\(a_i\),就是把原来的点值先抄过来,然后对于\(a_i\)的所有子集给它们翻倍,打上一个子集翻倍的tag即可。

打完之后做一遍FMT超集和来推标记,就得到了所有生成函数卷起来的点值,所以再一遍逆FMT就可以得到答案。复杂度是\(O(n+v\log v)\)。


CF772D Varying Kibibits

这个题意还挺离谱。

那个\(G(x)\)外面的\(x\)一看就知道是为了减小输出量加上的东西,所以我们可以先去掉它,最后再处理。

看到是十进制!最小值!你就知道是k进制法嘛塔!

k进制法嘛塔怎么做?

还是从小到大按位处理,我们假设当前处理到\(k\)位,那么所有\(k\)位较小的应该贡献给较大的,你发现这是一个前缀和,做就好了。复杂度应该是\(O(n\log n)\)。

诶等等,这个题怎么带个平方啊???

你发现法嘛塔是个合并的过程,并且它还是不交并,这让人不禁想到在线段树上我们怎么维护平方和。呃不管想不想的到,差不多就那意思(

考虑合并\(A,B\)之后多出来的贡献就是选一个\(a\subseteq A,b\subseteq B\),然后\(a+b\)的贡献,不妨记为\((a+b)^2\),可以写成这样 :

\[\begin{aligned} &\sum_{a\subseteq A}\sum_{b\subseteq B}(a+b)^2\\ =&\sum_{a\subseteq A}\sum_{b\subseteq B}(a^2+b^2+2ab)\\ =&\sum_{a\subseteq A}\sum_{b\subseteq B}a^2+\sum_{a\subseteq}\sum_{b\subseteq B}b^2+\sum_{a\subseteq A}\sum_{b\subseteq B}2ab\\ =&\left(\sum_{a\subseteq A}a^2\right)\left(\sum_{b\subseteq B}b^0\right)+\left(\sum_{a\subseteq A}a^0\right)\left(\sum_{b\subseteq B}b^2\right)+2\left(\sum_{a\subseteq A}a\right)\left(\sum_{b\subseteq B}b\right) \end{aligned}\]

前面两个就是我们维护的\(2\)次方和乘\(0\)次方和,后面就是维护的\(1\)次方和的积。做完了。

另外对于k进制位运算卷积(\(\operatorname{and}\)是取\(\min\),\(\operatorname{or}\)是取\(\max\),\(\operatorname{xor}\)是加起来膜\(k\)),除了\(\operatorname{xor}\)以外跟二进制的推导几乎相同,可以很容易地用上面的k进制法嘛塔解决。至于\(\operatorname{xor}\)怎么做……那就是高维法法塔的工作了,这里不提!


算了还是提一下吧。考虑把每一位拆开,从低位到高位计算,那么每一位相当于一个膜\(z^k\)的循环卷积,用Bluestein硬算即可。类似于左偏树线性建树的复杂度,可以知道这个算法的复杂度是\(O(n\log n)\),当然这里视\(k=O(1)\)。

不过卷积比起\(\min/\max\)卷积性质太差了,搬到上一个题看起来并不可做。


UOJ176 新年的繁荣

奇怪边权的完全图求MST,当然想到Boruvka别乳卡。问题变成,对于每个连通块,查询从连通块内选一个点,块外选一个点,可以得到的\(\operatorname{and}\)的最大值。

法嘛塔。对于每个值做子集后缀和,求出最多两个不同的包含它的连通块,一个简单方法是求出最大编号和最小编号的连通块。

这样我们扫过每个点,进行按位贪心,看其它连通块的点和这个点\(\operatorname{and}\)起来的最大值,并更新这个连通块的出边。

这样进行\(\log n\)轮之后一定会停止,所以复杂度就是\(O((n+v)\log n\log v)\)。

实际上使用Kruskal也是可以的,这是一种类似法嘛塔,但是又不完全是的做法。

考虑一开始每个点都是一个独立的连通块,接下来我们需要从大到小枚举一个边权\(w\),然后在连通块之间找边权是\(w\)的边并合并连通块。

当我们枚举到\(w\)的时候,所有\(>w\)的边都连完了,所以所有点权真包含\(w\)的点已经连成了一个连通块,那么我们只需要枚举二进制恰好比\(w\)多一个\(1\)的权值们的超集,然后如果这些连通块不是同一个连通块,我们试图合并它们。

这启发我们做一些奇怪的操作。一开始我们把点权是\(i\)的点存在\(a_i\)这个位置。然后枚举一个\(w\),枚举\(w\operatorname{or}2^i\)以得到需要合并的连通块,然后用并查集合并它们,最后再选一个代表元存在\(a_i\)。

注意一开始我们存的时候只能存一个点,不过这没有什么关系,因为点权相同的点之间连边是肯定不劣的,我们可以把这样的边连满,然后给每个点权选一个代表。


咕咕咕。