集合幂级数学习笔记

winterfrost 2023-03-28 原文

Post time: 2022-02-17 14:11:52

本篇文章借鉴于武汉二中吕凯风的2015集训队论文《集合幂级数的性质与应用及其快速算法》。

一、声明

我们令全集为有限集 $U=\{1,2,...,n\}$，其中 $n=|U|$，设所有未标明的 $S$ 都是 $U$ 的子集。

若 $X$ 是一个集合，令 $2^{X}$ 表示 $X$ 的幂集（所有子集构成的集合）。

二、定义

设 $F$ 是一个域，则称函数 $f:2^{U}\to F$ 是 $F$ 上的一个集合幂级数。对于每个 $S\in 2^U$，记 $f_S$ 为 $S$ 处的函数值，称 $f_S$ 为集合幂级数 $S$ 项的系数。

集合幂级数之间的加减法运算是很好定义的，就是对应项的系数加减，可以在 $O(2^n)$ 的时间内完成。

容易发现一个集合幂级数一定可以写成若干个 $cx^S$ 相加的形式（其中这个 $c$ 和 $x^S$ 之间是某种乘法，但不需要严格定义，只需满足与加法的结合律），所以可以用符号 $f=\sum_{S\in 2^U}f_Sx^S$ 来表示一个集合幂级数。

乘法的定义复杂一些，首先我们考虑定义的乘法应当对加法有分配律，即

\[\sum_{S\in 2^U}h_Sx^S=(\sum_{L\in 2^U}f_Lx^L)\cdot(\sum_{R\in 2^U}g_Rx^R)=\sum_{L\in 2^U}\sum_{R\in 2^U}(f_Lx^L* g_Rx^R) \]

考虑一下这个 $* $ 号运算应当具有的性质：

$L* R=R* L$ （交换律）
$(L* M)* R=L*(M* R)$ （结合律）
$S*\varnothing=S$ （单位元为 $\varnothing$）

那么我们可以定义 $f_Lx^L* g_Rx^R=(f_Lg_R)x^{L* R}$。

下面介绍 $* $ 不同的三种常见的集合幂级数乘法。

三、集合并卷积

取 $L* R=L\cup R$，得到集合并卷积。

定义 $f\cdot g=h$，其中

\[h_S=\sum_{L\in 2^U}\sum_{R\in 2^U}[L\cup R=S]f_Lg_R \]

计算集合并卷积要使用快速莫比乌斯变换（FMT）。

定义一个集合幂级数 $f$ 的莫比乌斯变换为

\[\hat{f}_ S=\sum_{T\subseteq S} f_T \]

反过来，由容斥原理，定义逆莫比乌斯变换（莫比乌斯反演）为

\[f_S=\sum_{T\subseteq S}(-1)^{|S|-|T|}\hat f_T \]

对上面集合并卷积的式子两边进行莫比乌斯变换，可得

\[\hat h_S=\sum_{L\in 2^U}\sum_{R\in 2^U}[L\cup R\subseteq S]f_Lg_R \]

由于 $[L\cup R\subseteq S]=[L\subseteq S][R\subseteq S]$，所以

\[\hat h_S=(\sum_{L\subseteq S}f_L)(\sum_{R\subseteq S}g_R)=\hat f_S\hat g_S \]

所以计算集合并卷积的步骤，就是先求出 $f,g$ 的莫比乌斯变换，对应系数相乘之后，再做一次莫比乌斯反演。

现在考虑如何做莫比乌斯变换。

对莫比乌斯变换的一个理解说的是，有一些形如 $x\leq y$ 的偏序集，把所有 $x$ 位置的值累加到 $y$ 位置上就形成了莫比乌斯变换。

计算上述莫比乌斯变换的方法就是，依次考虑集合中每个元素，没有它的贡献到有它的上面，复杂度 $O(n2^n)$。代码大概长这样：

点击查看代码

for(int i=0;i<l;++i){
	for(int S=0;S<(1<<l);++S){
		if(S&(1<<i)) continue;
		add(f[S|(1<<i)],f[S]);
	}
}

莫比乌斯反演就是把里边的加号改成减号。

四、对称差卷积（异或卷积）

令 $L* R=L\oplus R$ 可得对称差卷积：

\[h_S=\sum_{L\in 2^U}\sum_{R\in 2^U}[L\oplus R=S]f_Lg_R \]

快速计算需要用到快速沃尔什变换（FWT）。

首先注意到对于一个集合 $S$ 有

\[\frac{1}{2^n}\sum_{T\in 2^U}(-1)^{|S\cap T|}=[S=\varnothing] \]

当 $S$ 不为空集时，对于 $v\in S$ 把每个 $T$ 和 $T\oplus \{v\}$ 放在一起就得到和为 $0$ 了。

利用这个性质化简上式：

\[\begin{aligned} h_S&=\sum_{L\in 2^U}\sum_{R\in 2^U}[L\oplus R\oplus S=\varnothing]f_Lg_R\\ &=\sum_{L\in 2^U}\sum_{R\in 2^U}\frac{1}{2^n}\big(\sum_{T\in 2^U}(-1)^{|T\cap (L\oplus R\oplus S)|}\big)f_Lg_R\\ &=\sum_{L\in 2^U}\sum_{R\in 2^U}\frac{1}{2^n}\big(\sum_{T\in 2^U}(-1)^{|T\cap L|}(-1)^{|T\cap R|}(-1)^{|T\cap S|}\big)f_Lg_R\\ &=\frac{1}{2^n}\sum_{T\in 2^U}(-1)^{|T\cap S|}\big(\sum_{L\in 2^U}(-1)^{|T\cap L|}f_L\big)\big(\sum_{R\in 2^U}(-1)^{|T\cap R|}g_R\big) \end{aligned} \]

由上式定义沃尔什变换为

\[\hat f_S=\sum_{T\in 2^U}f_T(-1)^{|T\cap S|} \]

可得沃尔什逆变换为

\[f_S=\frac{1}{2^n}\sum_{T\in 2^U}\hat f_T(-1)^{|T\cap S|} \]

则上面的对称差卷积可以化为

\[\hat h_S=\hat f_S\hat g_S \]

沃尔什变换的求法跟莫比乌斯变换差不多，仍然一位一位考虑集合中的数，对于当前位 $i$，$f_S:=f_S+f^{S\cup\{i\}},f_{S\cup\{i\}}:=f_S-f_{S\cup\{i\}}$。逆变换给每一项乘以 $\frac{1}{2^n}$ 即可。对特征为 $2$ 的域不能使用沃尔什变换。复杂度 $O(n2^n)$。

五、子集卷积

子集卷积形如

\[h_S=\sum_{L\in 2^U}\sum_{R\in 2^U}[L\cup R=S][L\cap R=\varnothing]f_Lg_R \]

快速算法是枚举 $S$ 和子集 $L$，$R=S/L$，这样做复杂度 $O(3^n)$。

可以转化为集合并卷积做

UPDATE：原来写的快速沃尔什变换(FWT)

FWT用来加速计算位运算卷积。

广义上的FWT思路为：

设序列 $a$ 的变换序列为 $fwt[a]$，若要计算 $c=a\oplus b$（直接算是 $O(n^2)$），可构造一个变换 $a\rightarrow fwt[a]$，使其满足正变换和逆变换时间复杂度均小于 $O(n^2)$，并且 $fwt[a]\cdot fwt[b]=fwt[c]$，这里 "$\cdot$" 一般指点乘（复杂度小于 $O(n^2)$）。

经过上边的铺垫，可以进行这样一个过程：$a\rightarrow fwt[a],b\rightarrow fwt[b],fwt[a]\cdot fwt[b]=fwt[c],fwt[c]\rightarrow c$，这个过程时间复杂度是小于 $O(n^2)$ 的，达到了加速效果。

在 OI 中，对于 OR,AND,XOR 三种卷积都可以用 FWT 优化到 $O(n\log n)$ 复杂度。

以或卷积为例：

要计算

\[c_i=\sum_{j|k=i}a_jb_k \]

直接算是 $O(n^2)$ 的，考虑使用 FWT：

首先注意到 $j|i=i,k|i=i\rightarrow (j|k)|i=i$

设 $fwt[a]_ i=\sum_{j|i=i}a_j$，需要考虑正变换、逆变换和点乘：

首先考虑点乘：对于 $\forall i\geq 1$，有

\[\begin{aligned} fwt[a]_ i\cdot fwt[b]_ i&= (\sum_{j|i=i}a_j)(\sum_{k|i=i}b_k)\\ &= \sum_{j|i=i}\sum_{k|i=i}a_jb_k\\ &= \sum_{(j|k)|i=i}a_jb_k\\ &= \sum_{(j|k)|i=i}c_{j|k}\\ &= fwt[c]_ i \end{aligned} \]

正变换：考虑按位从小到大求，设当前最高位为 $0,1$ 的答案序列（不考虑这一位）分别为 $a_0,a_1$，合并之后（考虑这一位）分别为 $b_0,b_1$，则 $b_0=a_0,b_1=a_1+a_0$，其中 $+$ 是序列每一位相加。

通过正变换，不难发现逆变换的式子为 $b_0=a_0,b_1=a_1-a_0$。

同理，与的式子就是 $b_0=a_0+a_1,b_1=a_1$，逆变换 $b_0=a_0-a_1,b_1=a_1$。

异或的式子比较复杂。首先定义 $x\oplus y=popcount(x\&y) \bmod 2$，这里 $popcount(x)$ 表示 $x$ 二进制下 $1$ 的个数。

可以发现，$(j\oplus i)\operatorname{xor}(k\oplus i)=(j\operatorname{xor} k)\oplus i$。

设 $fwt[a]_ i=\sum_{j\oplus i=0}a_j-\sum_{j\oplus i=1}a_j$，考虑点乘：

\[\begin{aligned} fwt[a]_ i\cdot fwt[b]_ i&= (\sum_{j\oplus i=0}a_j-\sum_{j\oplus i=1}a_j)(\sum_{k\oplus i=0}b_k-\sum_{k\oplus i=1}b_k)\\ &= (\sum_{j\oplus i=0}a_j)(\sum_{k\oplus i=0}b_k)-(\sum_{j\oplus i=0}a_j)(\sum_{k\oplus i=1}b_k)-(\sum_{j\oplus i=1}a_j)(\sum_{k\oplus i=0}b_k)+(\sum_{j\oplus i=1}a_j)(\sum_{k\oplus i=1}b_k)\\ &= (\sum_{(j\operatorname{xor} k)\oplus i=0}a_jb_k)-(\sum_{((j\operatorname{xor} k)\oplus i=1}a_jb_k)\\ &= (\sum_{(j\operatorname{xor} k)\oplus i=0}c_{j\operatorname{xor} k})-(\sum_{((j\operatorname{xor} k)\oplus i=1}c_{j\operatorname{xor} k})\\ &= fwt[c]_ i \end{aligned} \]

正变换：$b_0=a_0+a_1,b_1=a_0-a_1$，逆变换：$b_0=\frac{a_0+a_1}{2},b_1=\frac{a_0-a_1}{2}$。

代码上，所有的正逆变换都可以合并，注意取模，注意修改的顺序即可。

模板P4717

点击查看代码

#include<iostream>
#include<cstdio>
typedef long long ll;
const int N=(1<<17)+13,mod=998244353;
inline int qpow(int a,int k){int s=1;for(;k;k>>=1,a=(ll)a*a%mod)if(k&1)s=(ll)s*a%mod;return s;}
int n,a[N],b[N],ina[N],inb[N];
inline void clear(){
	for(int i=0;i<n;++i) a[i]=ina[i],b[i]=inb[i];
}
inline void OR(int *f,int type=1){
	for(int mid=2,k=1;mid<=n;mid<<=1,k<<=1){
		for(int i=0;i<n;i+=mid){
			for(int j=0;j<k;++j){
				f[i+j+k]+=(ll)f[i+j]*type%mod;
				f[i+j+k]%=mod;
			}
		}
	}
}
inline void AND(int *f,int type=1){
	for(int mid=2,k=1;mid<=n;mid<<=1,k<<=1){
		for(int i=0;i<n;i+=mid){
			for(int j=0;j<k;++j){
				f[i+j]+=(ll)f[i+j+k]*type%mod;
				f[i+j]%=mod;
			}
		}
	}
}
inline void XOR(int *f,int type=1){
	for(int mid=2,k=1;mid<=n;mid<<=1,k<<=1){
		for(int i=0;i<n;i+=mid){
			for(int j=0;j<k;++j){
				int x=f[i+j],y=f[i+j+k];
				f[i+j]=(ll)(x+y)*type%mod,f[i+j+k]=(ll)(x-y+mod)*type%mod;
			}
		}
	}
}
inline void mul(){
	for(int i=0;i<n;++i) a[i]=(ll)a[i]*b[i]%mod;
}
inline void print(){
	for(int i=0;i<n;++i) printf("%d ",a[i]);
	putchar('\n');
}
int main(){
	scanf("%d",&n);n=(1<<n);
	for(int i=0;i<n;++i) scanf("%d",&ina[i]);
	for(int i=0;i<n;++i) scanf("%d",&inb[i]);
	clear();OR(a),OR(b),mul(),OR(a,mod-1);print();
	clear();AND(a),AND(b),mul(),AND(a,mod-1);print();
	clear();XOR(a),XOR(b),mul(),XOR(a,qpow(2,mod-2));print();
	return 0;
}

笔记集合 span inline class 算法与数据结构

有关集合幂级数学习笔记的更多相关文章

postman——集合——执行集合——测试脚本——pm对象简单示例02 - 2
//1.验证返回状态码是否是200pm.test("Statuscodeis200",function(){pm.response.to.have.status(200);});//2.验证返回body内是否含有某个值pm.test("Bodymatchesstring",function(){pm.expect(pm.response.text()).to.include("string_you_want_to_search");});//3.验证某个返回值是否是100pm.test("Yourtestname",function(){varjsonData=pm.response.json
LC滤波器设计学习笔记（一）滤波电路入门 - 2
目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》，侵权删。前言最近需要学习放大电路和滤波电路，但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放，所以也是相当从零开始学习了。滤波电路科普主要分类滤波器：主要是从不同频率的成分中提取出特定频率的信号。有源滤波器：由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波，最普通易于采用的无源滤波器结构是将电感与电容串联，可对主要次谐波（3、5、7）构成低阻抗旁路。无源滤波器：无源滤波器，又称
CAN协议的学习与理解 - 2
最近在学习CAN，记录一下，也供大家参考交流。推荐几个我觉得很好的CAN学习，本文也是在看了他们的好文之后做的笔记首先是瑞萨的CAN入门，真的通透；秀！靠这篇我竟然2天理解了CAN协议！实战STM32F4CAN！原文链接：https://blog.csdn.net/XiaoXiaoPengBo/article/details/116206252CAN详解（小白教程）原文链接：https://blog.csdn.net/xwwwj/article/details/105372234一篇易懂的CAN通讯协议指南1一篇易懂的CAN通讯协议指南1-知乎(zhihu.com)视频推荐CAN总线个人知识总
深度学习部署：Windows安装pycocotools报错解决方法 - 2
深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal
ruby - 我正在学习编程并选择了 Ruby。我应该升级到 Ruby 1.9 吗？ - 2
我完全不是程序员，正在学习使用Ruby和Rails框架进行编程。我目前正在使用Ruby1.8.7和Rails3.0.3，但我想知道我是否应该升级到Ruby1.9，因为我真的没有任何升级的“遗留”成本。缺点是什么？我是否会遇到与普通gem的兼容性问题，或者甚至其他我不太了解甚至无法预料的问题？最佳答案你应该升级。不要坚持从1.8.7开始。如果您发现不支持1.9.2的gem，请避免使用它们(因为它们很可能不被维护)。如果您对gem是否兼容1.9.2有任何疑问，您可以在以下位置查看:http://www.railsplugins.or
ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2
我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排
ruby - 我如何学习 ruby 的正则表达式？ - 2
如何学习ruby的正则表达式？(对于假人) 最佳答案 http://www.rubular.com/在Ruby中使用正则表达式时是一个很棒的工具，因为它可以立即将结果可视化。关于ruby-我如何学习ruby的正则表达式？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/1881231/
深度学习12. CNN经典网络 VGG16 - 2
深度学习12.CNN经典网络VGG16一、简介1.VGG来源2.VGG分类3.不同模型的参数数量4.3x3卷积核的好处5.关于学习率调度6.批归一化二、VGG16层分析1.层划分2.参数展开过程图解3.参数传递示例4.VGG16各层参数数量三、代码分析1.VGG16模型定义2.训练3.测试一、简介1.VGG来源VGG（VisualGeometryGroup）是一个视觉几何组在2014年提出的深度卷积神经网络架构。VGG在2014年ImageNet图像分类竞赛亚军，定位竞赛冠军；VGG网络采用连续的小卷积核（3x3）和池化层构建深度神经网络，网络深度可以达到16层或19层，其中VGG16和VGG
机器学习——时间序列ARIMA模型(四)：自相关函数ACF和偏自相关函数PACF用于判断ARIMA模型中p、q参数取值 - 2
文章目录1、自相关函数ACF2、偏自相关函数PACF3、ARIMA(p,d,q)的阶数判断4、代码实现1、引入所需依赖2、数据读取与处理3、一阶差分与绘图4、ACF5、PACF1、自相关函数ACF自相关函数反映了同一序列在不同时序的取值之间的相关性。公式：ACF(k)=ρk=Cov(yt,yt−k)Var(yt)ACF(k)=\rho_{k}=\frac{Cov(y_{t},y_{t-k})}{Var(y_{t})}ACF(k)=ρk=Var(yt)Cov(yt,yt−k)其中分子用于求协方差矩阵，分母用于计算样本方差。求出的ACF值为[-1,1]。但对于一个平稳的AR模型，求出其滞
Unity Shader 学习笔记（5）Shader变体、Shader属性定义技巧、自定义材质面板 - 2
写在之前Shader变体、Shader属性定义技巧、自定义材质面板，这三个知识点任何一个单拿出来都是一套知识体系，不能一概而论，本文章目的在于将学习和实际工作中遇见的问题进行总结，类似于网络笔记之用，方便后续回顾查看，如有以偏概全、不祥不尽之处，还望海涵。1、Shader变体先看一段代码......Properties{ [KeywordEnum(on,off)]USL_USE_COL("IsUseColorMixTex?",int)=0 [Toggle(IS_RED_ON)]_IsRed("IsRed?",int)=0}......//中间省略，后续会有完整代码 #pragmamulti_c

集合幂级数学习笔记

有关集合幂级数学习笔记的更多相关文章

随机推荐