嗒贱缩点板子

有个sb说我没动态,实在是zz

卷积与FFT的理解方法几条

卷积听起来超级高大上,其实,用函数的角度思考不是很好理解。

最好理解的方法,就是“多项式乘法”。其实,你看到的整理后的函数解析式,就是个多项式啦。

现在你还记得整数乘法怎么手算吗?列竖式。本质上多项式乘法算法和他是一样的。只不过,十进制不能出现大于9的位数,所以需要进位。而多项式的系数随便大小正负都可以啦。所以算起来反而更简单。

1.所谓的卷积就是多项式乘运算。把两个函数看成两个多项式,列竖式乘起来。

多项式长度不一样?whocares?你告诉我123*12结果是怎么算的?位数也不一样啊?

2.多项式整理后是按照x的幂排列起来的,本质上和整数的低位和高位也是一样的。我们可以用一个ai唯一的表示某个多项式的某个系数(因为排好序了嘛)

那么乘积也是一个多项式,我们就可以根据系数唯一地写出多项式啦。由于多项式就是函数解析式,我们自然也可以唯一写出一个函数。

函数卷函数=函数<——->多项式乘多项式=多项式

3.卷积运算率的数学表达?也许你是理科生,看了前面的文字不明白。不过我是文科生啦。

设符号@(它比较卷)为卷积的二元运算符,参与运算的算子为函数,结果亦为函数,设函数a=f@g

a(k)=sigma i,j|f(i)*g(j) [i+j=k]

怎么理解这个该死的中括号。

我请你手写一个多项式乘法的竖式。在结果函数a中的某一个位置(也就是x的某次幂的系数)是怎样得到的。

算乘法的时候,横向乘积,纵向加和,就是这个意思。回忆一下整数乘法,某一位的答案,正是许多 位数之和等于这一位的数字 的 乘积 的 加和,当然十进制我们要进位。

类比一下多项式乘法,也就是卷积,某次幂的答案也就是所有幂次之和等于该次数的系数乘积之和。

这样就永远忘不了卷积定义了。

4.FFT. FFT是什么,千万千万不要现在看网上的各类

《十分钟教你理解离散傅里叶变换》《看不懂算我输》。。。的文章。

他们更多是给大学生讲,而不是给你我。其中的FFT更多涉及数学和物理上的定义和应用等,虽然很有利于提高知识水平,但是对于理解并不是很有帮助。

离散是什么?傅里叶是谁?请不要在意。你要在意的只是,这个算法能降低时间复杂的。

多项式乘法,显然是n^2的复杂度。FFT可以降低其到nlogn。FFT在OI的特点有点像网络流,就是板子一般不怎么改,主要是如何应用。网络流难点当然是建图,而卷积的题显然是推式子。所以1.背板子很有用。2.背板子必须准确。3.背板子要找快的。

此文后会附赠一个我找的较为快速的FFT板子,在各站上均有比较优秀的表现。压常不考虑在内。

5.简单来讲,算法是把两个多项式由“系数表示法”转到“点值表示法,再将点值相乘,最后将点值转回多项式表示法。

这听起来绕了个大圈,好像多此一举。系数到点值需要带入x,带入n个x就是n^2的效率了,更何况转回多项式还要插值又是一个n^2。

效率是从哪里提高的呢?FFT最神的就是这个了。一句话:FFT的中心思想是通过代入一些具有特殊性质的x求得函数值,并获得点值表示,再通过类似的方法将点值写成系数形式。每次转化是nlogn的。

这些x是复数。你可能又要问复数是什么了。这很让人痛苦了。

形如a+bi的数就是复数。i是个常数也是个虚数,不存在于实数范围内。

定义: i^2=-1. -1怎么开根?你可能说不可能。事实上,这是实数中心论的思路。我们为什么要研究我们写都写不出来的数呢?FFT就给了一个非常好的例子。i并不是不存在,而是在实数范围不存在而已。如果实数有无限个,那么虚数会不会有无限个?我们无意间忽略了无限个数,就像毕达哥拉斯的信徒忽略的无限个无理数一样。

x,我们叫他单位复根。

你还记得我曾经脑抽用复数证明的和角公式吗?不记得就算了。

单位圆上的点的坐标是(cosx,sinx)。在复平面上写作cosx+sinx*i

(待续)

(先附赠板子)

bzoj3527

 

 

BZOJ3196二逼平衡树_卡常万岁

好久没更,其实好几次想更,但是blog总是登不上去。今天又可以了。那就来一发数据结构。

树套树第一道题。线段树套平衡树对这道题好像是最low的做法,加上我splay的常数异常大。

简单概括算法,其实就是说:通过线段树提取出区间,通过splay对区间进行操作。线段树和splay维护的顺序往往不同。线段树作为静态结构用来维护原序列的顺序,而splay则维护权值大小顺序。

线段树的区间元素不会重合,换句话说,提取出的区间只是连续区间,不可能重复。那么现在提取出的区间是多个线段树节点,我们在每个节点上建立平衡树维护大小,就可以根据平衡树得到或者维护一些信息。节点的答案汇总起来就是整个区间的答案。

这道题据说最快解法是树状数组套权值线段树。其实还是可以想象的。

但是我一直t啊t啊t啊t啊t。。诶怎么A了。

加强常数任重道远。

 

回归函

大概半个月前,发生了一件很奇怪的事情。
合租blog的同学,因为一些意外原因,由于插件漏洞被打了,连锁反应,服务器炸了。
于是乎我们的账号就光荣的被停机了。
多亏曲神积极协商,直到今天blog才终于被回复。

另外曲神的脸实在太白啦。

注意事项:取模

这里特别要贴一个Tip。在这里栽了多少次还是不长记性。
太扯淡了。
这次又来一次,这道矩阵优化递推,本来不恶心。Tle是因为某些情况没特判,倒也罢了。
但是接下来WAWAWAAAAAAAAAAAAAAAAAA
我根本不知道怎么WA的。查来查去,查不出来。是不是基础矩阵写错了?
调标程,对比矩阵,没毛病。
难道是ksm写错了?不可能啊!
终于找到的罪魁祸首竟然是取模。
别忘了取模负数会搞不出来啊。你得+模数再取模!
(x%mod+mod)%mod!!!!!!!!!!!!!!
好了A了。
我实在是醉了。
藉此提醒自己不要再以后的题目和考场上犯如此智障的错误。