集合并卷积与FMT

首先感谢几篇良心博客的博主,教程写得真的很好。
真正理解快速沃尔什变换/快速莫比乌斯变换(FWT|FMT) (已完结)
FMT 与 子集(逆)卷积

集合卷积

我们时常要解决一些与集合有关的卷积问题,像快速傅里叶变换那样,对下标有一些要求和限制。
FWT和FMT可以成为我们解决这类问题的有力武器。

FMT

我个人认为,FMT比FWT从原理角度上更好理解。接下来介绍一下快速莫比乌斯变换。

原理

首先我们要证明FMT可以像FFT那样乘来乘去并保证正确性。

证明

对于长度为的序列,我们定义集合并卷积,
                                                                                                                        

定义它的莫比乌斯变换为


对集合并卷积的式子两边做FMT,




至此我们就证明了其具有线性变换的性质。

正变换

直接暴力进行计算,其复杂度是O()的,这个复杂度很容易证明(虽然写烂了的话就变成O())。
一种优美的方法是分层进行递归处理,我们处理某一位i,假设一个集合S是不包含i的,那么的位置可以由S来产生贡献。
处理边界和n轮之后的变换式,就可以得到我们要的东西了。

逆变换

与正变换类似,不同点在于这次要减去SS的贡献。


这个式子用容斥证明非常容易。

Code

void FMT(int *f, int opt)  {   for (int j = 0; j < n; ++ j)   for(int i = 0; i < (1 << n); ++ i)    if (i >> j & 1)  f[i] += opt * f[i ^ (1 << j)];  } 

复杂度O(n2n)O(n2n)

其他相关

有限制的FMT

现在要求


和之前不同的地方在于多了一个二者交集为空的条件,所以我们不能无脑套用FMT了。
我们可以多加一维考虑当前集合大小为ii,集合为SS的变换值。
你问为啥多加这一维?集合SS已知还要再加一位确定大小?
其实这个ii并非真实大小,而是我们认为的大小。最后有作用的只有那些f[count(S)][S]。

for (int i = 0; i <= n; ++ i)  {  for (int j = 0; i + j <= n; ++ j)  for (int S = 0; S < (1 << n); ++ S)  h[i + j][S] += f[i][S] * g[j][S]; } 

复杂度O()。

子集逆卷积

对于要求反卷积,形如


已知h,g,求f。有


现在我们要求,即一个多项式一以下的逆。然后进行FMT就万事大吉了。

inline void Inv(int *f)  {  tmp[0] = Pow(f[0], mod - 2);  for (int i = 0; i <= n; ++ i)   {  inv[i] = tmp[i];  for (int j = 0; i + j <= n; ++ j)  tmp[i + j] -= inv[i] * f[j];  } } 

全部评论

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务