——傅里叶变换在信息学竞赛中主要作用是利用卷积思想,化乘为加,快速计算多项式乘法。

我太蒟了,看了$F(x)$篇博文,还是没看懂。

$update():$发现模板题时限缩小,开始修锅(去冗余)。

当年写这篇文章的时候比较菜(现在仍然很菜),所以讲的比较含混不清,现在更新和精简了一些内容,希望能对大家有所帮助~

源码删去了17KB,更新了9KB内容。

文章中的代码已经进一步优化,可以通过模板题。

由于文章前后内容有所变化,已将讨论区清空。

警告 : 本文对数学水平有一定要求,如果发现看不懂,可以先存着。

另外,如果你掌握和式的话,学习速度将会大幅度提高。

此外,由于前面的内容太掉逼格,建议水平高的选手直接跳到“单位根”。

1.线段树(或者基本分治)：

然后在你刷完这些题之后,发现题和下面的内容并没什么关系。

这里不会满屏都是三角函数!!,没有$e^i$和什么欧拉定理!!

不需要你会高数,只要用过平面直角坐标系,就可以看。

这篇文章源码40KB,写的时候挑战洛谷Blog(浏览器)性能极限

中文名：快速傅里叶离散变换

大家在学多项式乘法的时候,是不是觉得拆括号特别麻烦。

现在我们就要用计算机把两个多项式乘起来(所谓多项式问题)。

P.S:下面提及的多项式均只有一元,你可以认为只有$x$这一元。

为了表述方便,下面定义一些记号(请仔细阅读)：

• $F(x)$表示一个多项式,简单的叫做“多项式$F$”。

• 这里有一个n次多项式$F(x)$

  其中$a,b,c...$是参数,因为他们在系数的位置上,所以也叫系数.

  用不同的字母来表示系数很烦,我们就用数组。

• 现在如果让你把两个$n$次多项式$F(x)$和$P(x)$乘起来,你会怎么写程序？

  也就是说$A[i]B[k-i]$乘起来之后,他们后面的未知数就变成了$x^k$,所以要往$C[k]$贡献。

  那么你可能观察到了,多项式乘法就是加法卷积。

  (后面我们还会学习到其他的卷积)

  多项式乘法拥有交换律结合律分配率什么的,就不多说了……

要用计算机把两个多项式乘起来就是所谓多项式问题。

数学家为了偷懒发明了麻烦的记号。

• 验算上面的式子,你同意作者的化简过程吗？

首先说一下多项式的点值表达。

如果把多项式看作函数,画出图像：

如果一开始不告诉你解析式,只跟你说这个一次函数经过点(0,1)和(1,3),你能搞出解析式吗？

待定系数法(两点确定一条直线)即可。

我们这里不讲待定系数法,我们只讲待定系数法的推论

在平面直角坐标系中,$n+1$ 个点就能唯一确定一个 $n$ 次多项式。

如果对这方面的知识感兴趣,可以查看

所以我们可以用n+1个点值(有序数对)来描述一个多项式。

函数图像与得到的点如下。

让你求两个多项式之积$W(x)=F(x)*P(x)$的点值表达,你会怎么干？

点值表达有一个好处,给你两个多项式点值表达,让你求两个多项式之积的点值表达,直接将对应项乘起来就好了。

(点值的乘法对应着整个多项式的乘法,也就是浓缩了整个多项式)

好像那里不对,W的次数明摆着是2n。

在平面直角坐标系中,给你(n+1)个点就能确定一个n次多项式。

所以需要2n+1个点才行,还差n个,肿么办？

反正点都是你自己找的,再多来几个不就好了……

只需要做2n+1次乘法即可。

看起来很好用,其实只是几个点而已,和系数表达差着十万八千里。

于是我们就想,能不能把系数表达转换为点值表达呢？

把系数表达转换为点值表达->点值表达相乘->把点值表达转换为系数表达。

这就是 FFT 的算法流程。

“把系数表达转换为点值表达”的算法叫做DFT

“把点值表达转换为系数表达”的算法叫做IDFT(DFT的逆运算)

• 从一个多项式的系数表达确定其点值表达的过程称为求值(毕竟求点值表达的过程就是取了 n 个 x 然后扔进了多项式求了 n 个值出来);

• 而求值运算的逆运算(也就是从一个多项式的点值表达确定其系数表达)被称为插值.

在平面直角坐标系中,给你(n+1)个点就能确定一个n次多项式(函数)。

点值表示相乘(点乘)远快于暴力卷积。

(如果你不知道$i$的故事,请百度)

P.S：学会了复数计算之后推荐给自己出点计算题来做

DFT有一个妙处,就是代入什么由你自己决定,只要点值个数足够。

我们这些蒟蒻第一感觉都会选择人畜无害的正整数,或者有理数什么的。

但是这些东西虽然在普通人看来计算简单,但并没有什么能够加以利用的优秀性质。

事实证明,找一些毒瘤东西代入进去是个好想法。

上古之时,有一位dalao横空出世,他就是傅里叶！

好像是个搞复数的专家,有一天他突发奇想：

然后分治,就$O(nlogn)$了(好像只有最后一个分句看得懂)

比如说数轴原来是一条直线：

某个实数一定可以用数轴上一个点来代表。

数轴原来是一条横着的直线,现在又多了一条竖着的,变成了一个坐标系。

原来的那条直线(横)称为实轴

新的那条直线(竖)称为虚轴

每个复数一定可以用这个坐标系上一个点来代表。

其实形为$a+bi$的复数也可以理解为一个点(a,b)

精妙之处在于,复数之间能做运算。

不懂的话就多琢磨下我写完这些之后就懂了

我们来介绍下复数运算：

• 复数相加：实部和虚部分别相加。

• 复数相减：取个相反数再相加。

• 复数相乘：像一次多项式一样相乘。

• 复数的共轭：实部相同,虚部相反(根据实轴对称)。

• 复数相除：分子分母同乘分母的共轭

  将分母实数化,在分子分母同时乘上分母的共轭,即可把分母变成实数。

而且这些运算在几何(也就是上面的坐标系)里面也有神奇的性质。

好吧,看见那些从$A,B,C$点连向原点的细线了么。

以你做几何题的直觉？？

没错！如果设原点为点$O$,数5表示的那个点为P(忘记画点P)。

我们把一个复数表示的点到原点的距离叫做这个复数的模长,也就是这里的$OB;OC;OA$,复数$x=(a+bi)$的模长称作$|x|$。

也即 : 复数相乘时,模长相乘,幅角相加！

原点到该点的射线与实轴正方向射线组成的角 （逆时针旋转） 的角度乘坐这个复数的幅角,复数$a+bi$的幅角称作$arg(a+bi)$。

接下来是证明(最好跟着把图画出来)：

为保证一般性,下面涉及到的都是字母。

• 第二个规律需要相似+爆算的,不想了解请跳过。

  那么,如果能证明途中两个三角形相似,就能证明幅角相加定理了。

  我们已经证明了$OA=OC*OB$(模长相乘),相似比例就是$OB$。

  证毕。这玩意特别重要。

接下来我们介绍单位根。

看起来很高大上,这是傅里叶快速变换的重要内容。

• n次单位根(n为正整数)是n次幂为1的复数。

到这里你也许会有一点不懂,我们来一起推导一下。

学过三角函数的话应该对单位圆很熟悉。

不熟悉的话也没事,单位圆就是：

圆心在原点且半径为1的圆(如图)

我们在复平面上放一个单位圆,在这个单位圆上的点表示的复数都有一个性质：

模长为1(圆上每一点到圆心的距离都相等)

可还记得？n次单位根是n次幂为1的复数,1的模长就是1。

所以只有模长等于1的复数才有可能成为n次单位根。

也就是说,只有单位圆上的点表示的复数才有可能成为n次单位根(必要性)

我们成功缩小了探究范围,只在这一个圆上研究。

(下面提及的复数,均是在单位圆上的复数!!!)

接下来,我们要找单位根。

这些单位根的模长都是$1$,只有幅角存在差别,下面我们就不考虑模长。

容易知道这玩意的$n$次方幅角是$a$倍圆周,那么就和1重合。

根据代数基本定理 : n次方程在复数域内有且只有n个根。

所以这些不重不漏,就是所有的单位根了。

还不懂也没关系,我们来实践一下。

有一个模长为1的复数为3次单位根,它的幅角为(圆周$*a$)

它的3次方的幅角为$3a*$圆周

那么,如果它是3次单位根,幅角的3倍$(3a*$圆周$)$一定是圆周的自然数倍。

a=0时,它的幅角为0(其实这个复数就是1)

所以n次单位根n等分单位圆。(重要)。

我们从1开始(1一定是单位根),沿着单位圆逆时针把单位根标上号。

随意称呼,切了书写方便,一般不取模。

关于单位根的基本定义相信你已经Get到了。单位根的世界,就是一个单位圆。

下面还有一些性质(类比切蛋糕记忆)

• 显而易见,不懂的把上面的图看一看。

• 感性理解 : 我们把一个圆等分成n份(想想你切蛋糕的时候)

• 任何一个n次单位根都可以写成$ω_n^1$的整幂

$ω^k_n$相当于我们把一个圆(蛋糕)等分成n份然后取k份

类似的,$ω^{2k}_{2n}$相当于我们把一个圆(蛋糕)等分成2n份然后取2k份

显然是等价的,只不过多切了几刀而已。

• 也就是旋转半个圆周,也就是关于原点对称,也就是取相反数(建议画个图)

好啦,关于单位根想必你已经掌握啦(终于！！)。

坐稳了,前方高能！！！

复数把数轴扩展到了复平面上,复数可以对应复平面上一个点。

复数也有四则运算。复数相乘时,模长相乘,幅角相加。

n次单位根(n为正整数)是n次幂为1的复数。

把单位根画到单位圆上之后,就能整出一些性质。

• 画出五次单位根并计算它们的具体值

我们来讲讲FFT的分治方式

傅里叶一巴掌把这个多项式拍成碎片,然后按奇偶拼成两块

考虑n-1次(也就是说有n项)多项式F(x)

的每一项按照下标(次数)的奇偶分成两部分：

这里保证n是2的整幂,不会出现分得不均匀的情况。

他们的系数依赖于$F(x)$(具体看式子)

(又把多项式忘了的,赶紧回去看)

等式右边不就是只有一个正负号的区别吗？

这两条式子有什么用呢？

我们就成功的获得了$F(x)$的点值标示。

(懵逼不怕,具体见代码)

问题在于我们不知道啊？

上面的工作,其实是一个分治的过程。

$FL(x)$和$FR(x)$这两个多项式,是规模为原多项式一般的子问题,他们的性质完全相同！

这个可以一直分治下去,直到多项式只剩下一个项为止(此时什么操作也不用做)。

实践出真知,我们现在就用代码来表现丰富多彩的数学吧！

FFT分治的过程,就是根据：

这两个式子,实现子问题的合并。

• 默写上述两个式子的证明过程

上文有一句话：“保证n是2的整幂,不会出现分得不均匀的情况。”

实际应用中,n不一定是2的正整数次幂。

我们可以补项,在最高次强行添加一些系数为0的项(类似于高精度补0)。不影响我们的计算结果,却占了位置。(具体见代码)

讲完了这些我们可以开始写$DFT$了

根据上文复数的四则运算重载。

之前我们一直在说“把单位根代入...”

现在我们来学习如何求单位根。

我们怎么求$ω^1_n$呢？

点A就是$ω^1_n$,我们需要求出它的横坐标$OB$和纵坐标$AB$

其他什么也不知道。我们需要求$OB$和$AB$。

观察上图,需要求$OB$和$AB$,它们俩分别是$∠O$的邻边和对边.

C++的三角函数采用弧度制。一个整圆不再是$360$°,而是$2π$

具体见代码,多说无益。

现在问题来了,DFT输出的都是些杂乱的点值表达,所以解决不了问题。

上文说过,IDFT是DFT的逆(CP),她可以把点值还原成多项式,最终完成乘法。

现在到了讲IDFT的时候了!!!

IDFT和DFT就是两句话的区别,这个结论实在太好记了。

当然,证明还是要有的,而且很有价值,从这里可以延伸出 。

我们知道$DFT$就是求点值,我们不需要再去证明点值的相关性质,我们只要弄出一个$DFT$的逆运算就好了。

还是多项式$F(x)$,设我们变换之后,得到的点值数列为$G$。

通过这个式子我们可以把点值还原。

等比数列求和可以得到:

所以这部分贡献为0,我们就成功地证明了上述结论。

如果你想知道的多一些,我可以告诉你这个东西本质是单位根反演。

或者可以理解成范德蒙德矩阵求逆。

就是相当于把$G$数列当做系数,再代入一遍求值。

我悄悄告诉你$ω^{-1}_n$长这个样子

至此我们已经写出了第一个版本的FFT(蛤？还有几个？)

代码很好写,和DFT不同的地方很少：

可以看到因为常数过大而TLE了,看来我们需要一个常数更小的写法。

先别着急卡常,前文我们说过,IDFT和DFT只有一个符号的区别。

那么我们何不减少一下代码量呢:

卡常的方法分为以下几类：

0.硬件优化：浮点加速器,CPU等等。

2.封装优化：把代码的封装拆开,封装得过死会使效率降低(stl)。

3.编写优化：细节优化,手写栈之类。

4.时空互易: 空间换时间以达到时空均衡(常数层面上)。

硬件优化没什么指望,编译优化能力有限又太玄学。

咱们这份代码如果硬要把封装拆开就会显得十分丑陋。

只剩下编写优化,时空互易两条路子了。

首先观察这个程序片段:

复数的乘法代价是很高的,而buf*fr[k]我们计算了两次!

换成下面的操作,常数就小多了:

代码中我们使用了大量数组拷贝,这会影响性能。我们能否通过某些手段规避数组拷贝呢?

这个分治究竟在干什么?

分治过程 : 先按照某种顺序把东西分开排列,然后再合并上去。

原来的递归版(数组下标,先偶后奇,从0开始)：
 

 我们要想办法求出第4层的数组状况,然后才能往上合并。
 


 

 （这个东西叫做蝴蝶变换来着）
 


 

 具体怎么求呢?多多观察可得,最后的序列是原序列的二进制反转。
 


 

 


 

 “6”确实排在原来“3”的位置。
 


 

 如何得到二进制翻转后的数列呢？
 


 

 $O(nlogn)$倒是可以,但是这就违背了我们卡常的本愿啦……
 


 

 可以用递推$O(n)$搞定。
 


 

 这玩意是怎么得到的呢？
 


 

 我们可以把一个二进制数的反转拆成两部分来看：
 


x 连接上 其他部分的反转
 

 可以类比数位DP理解。
 


 

 

 
 

 
 

 那么我们完全可以用如下代码来代替:
 
 

 这就规避了所有的数组拷贝。
 
 

 
 

 
 
 

 可以看到还是TLE一个点QAQ
 
 

 三角函数求值很慢,我们却使用了$O(nlogn)$次三角函数求值,可以考虑预处理来减小常数。
 
 

 不过一种更有效的方式是:迭代实现(嘴巴讲不清楚的,看代码秒懂)。
 
 

 还有一点,/2可以用位运算优化,我们把/2统一换成>>1。
 
 

 
 

 怎么觉得比递归版好写？
 
 

 这个版本是最经典的,建议背诵全文。
 
 

 
 

 
 
 

 可以看到已经成功地通过了这道题。
 
 

附 : "三次变两次"优化

 

 
 

 
 

 
 

 
 

 
 

 也就是说求出$P(x)^2$之后,把它的虚部除以2即可.
 
 

 
 

 为了卡常数还写了个快读……
 
 

 相信经过上面的学习,这份代码大家都能够理解,我就不再赘述了.
 
 

 
 

 快了一点吧！虽然本蒟蒻的常数还是很大QwQ
 
 

• Warning : 如果需要卷积的两个多项式值域相差太大,就会卡精度,慎用。

 

 
 

 
 

 假如使用三次变两次优化,由于平方项的存在,涉及的精度跨度上限是${10^{24}}$,严重掉精度。
 
 

 下方例题第二题直接铁头硬上会WA。
 
 

 至于修正方法,可以把两个多项式数乘到相同的值域范围,这样子就不会产生平方项的大误差了。
 
 

 
 

 

 我们的点值代表了整个多项式,加法和乘法都是对应的。
 
 

 这可以用于某些(初等)卡常,比如我们如果要计算$A*B+B*C+A*C$
 
 

 如果完全封装,每次乘法就要计算$3$次FFT,一共就是$9$次FFT。
 
 

 
 

 
 

 
 

 
 

 平方之后也不需要分别IDFT,这样做是$3$次FFT,只折合原来的一次暴力。
 
 

 
 

 卡常有什么好总结的？去吊打集训队问吧。
 
 

 
 

 

 那么讲到这里,想必FFT的大部分内容你已经掌握了,到了说再见的时候了……
 
 

 
 

 欲知后事如何,请看下集:! (看完你会了解更多的多项式工业)
 

定义：除了1和本身两个数都不能被整除的自然数叫做质数，否则为合数。
0和1既不是质数也不是合数，最小的合数是4，
最小的质数是2，是唯一的偶质数，质数有无穷多个
由质数定理可以给出第n个质数p(n)的渐进估计：p(n)≈nlnn

二、唯一分解定理（算术基本定理）

任意大于1的自然数都能被质数的质数幂的乘积表示
运用：试除法（质因数分解或求一个数的约数）、质数判定
由此衍生出埃式筛法和线性筛法（欧拉筛法）
线性筛法时间复杂度为O(n)

先将2的倍数删去，再将3的倍数删去，即按顺序将质数的倍数删去

让每个合数只被最小的素因子筛除,这样每个数最多只被筛一次。
这个性质被广泛运用于数论函数的求解
洛谷P3383 【模板】线性筛素数

唯一分解定理（算术分解定理）的推论

如果一种转移关系j->i且j是i的约数，那么有两种方法
一个数约数个数上限为2sqrt n
倍数法：O(nlogn)先枚举j再枚举倍数i。
显然倍数法时间复杂度更优
有的情况可以用埃式筛法，当然倍数法会更加广泛

三、最大公约数与最小公倍数

四、求两个数的最大公约数

定义1：给定正整数m，若用m除两个整数a和b所得余数相同，称a和b对模m同余，记作a≡b(mod m)，并称该式子为同余式；否则称a和b对模m不同余
定义2：整数的集合被分为m个不同的集合，这些集合被称为模m剩余类（同余类）。每个同余类的任意两个整数都是模m同余的。

七、欧拉定理和费马小定理

八、裴蜀定理与欧几里得算法

十、中国剩余定理（CRT）

十一、扩展中国剩余定理（ExCRT）

用扩展欧几里得算法合并两个方程组
数学归纳法：假设求出了前k-1个方程构成的方程组的一个解x，记m=lcm(m1,m2,…,mk-1)， 则x+im(i为任意整数)是前k-1个方程的解。
其中t是未知量，可以用扩展欧几里得判断该方程是否有解。如果有解，求出t值，则前k个方程构成的方程组的一个解为x’=x+tm。
特别的，第一个方程的解x=a1

0.如果不是秒切的话，解决问题的一般思路：

1.退而求其次：如果数据小、没有某个限制怎么办？（可以通过暴力分得到提示）

2.找到矛盾问题的根源，就是算法升级的关键，如果有了这个限制，怎么处理？

本篇博文记录一些机智操作，简洁方法，奇技淫巧。

支持：整形读入。包括负数

但是空间极其紧张，除非没时间改，否则不要用这个。

用num[0]计数，有多个数组的时候，不会弄混cnt名称

当数组中可能遇见负数的时候，可以考虑采用修正值fix，将取值的区域平移。

直接再加上n，平移到[0,n]就可以直接处理了。

二分一个中位数的值ans，大于ans的赋为1，小于-1（等于再说）

找区间内有无连续子段和大于0，判断ans+还是ans-

9.Hungary匈牙利算法每次memset的小优化（默认左部点出发dfs）

①一般情况下，我们是每次找到一个右部点，vis[y]=1，之后每次memset一下vis

②但是，有的时候，右部点很多，memset一下，nleft*nright 就挂了。

而如果左部点很少，可以尝试标记左部点的vis，

因为，我们之所以标记vis，是因为，不能在dfs(pre[y])时，从pre[y]里不断返回pre[y]自己（考虑代码模拟一下）。

如果标记左部点，那么，回到自己时，会因为已经vis，直接返回0

换句话说，①方案是不让你找到y，而②方案，是回到自己再打断。本质一样。

③我们也可以用一个栈sta[]，收集右部点vis的点，用弹栈并归零处理vis。

为什么复杂度在②条件下没问题？？

其实，最坏和②复杂度是一样的，一般情况下更优。

返回就返回了，打断搜索。如果dfs下去，那么必然要到了一个新的左部点。

所以，每vis一个，最多多访问一个左部点。所以，sta[]中元素的数量和左部点数量是一致的。

所以，最坏情况下，和②是一样的。

（  update:其实根本可以不用每次尝试清空什么vis！！！

我们可以采用时间戳的东西，vis[i]变成int数组，表示最后一次访问这个右部点的左部点的编号！

dfs序最小点和dfs序最大点取lca即可。

因为dfs总是先搜完一个子树，又因为两个点遍历时间相差最远。画图理解一下。

11.区间维护最小值，支持删除，插入

2.差的最小值呢？两个set，第二个set维护数值set相邻两个的差值。插入删除用前驱后继处理。

有的时候，出题人要卡你。一个哈希值可能出现的差错是：

本来不同的两个串，通过取模运算，就可能相同了。

所以，我们通过两个串，如果两个有一个哈希值不同，就认为串不同了。

注意，不可能出现相同的串哈希值不同的情况，因为算法一样，得到的哈希值一定相同。

13.曼哈顿距离转切比雪夫距离

这样，就可以把一个加法变成最值问题。

可以处理曼哈顿距离最小生成树。

用两个set一个维护没有加入当前点集中的点，横坐标，纵坐标。

用四个数维护当前点集最小x，最大x，最小y，最大y

每次从set找四个点和最小x，最大x，最小y，最大y找最小距离加进去。

因为，只要从x找一个max，y找一个max，再取max就可以。

14.变进制数存储状态，状压dp

就是，根据每个数的出现次数不同，每个数位置的进制都不同。

这样，可以达到压缩状态数到最小的结果。

即通过判断i，j所有公约数的u的和是否为1，判断i，j是否互质。

i，j互质的时候，公约数只有1，u(1)=1

i，j不互质的时候，公约数就是i，j最大公约数的约数。

那么，如果取两个以上的pi,u就是0，不影响答案。

所以，就是取p1、。。。pk一个或不取的方案数要考虑

根据组合数的性质，不论k是奇数还是偶数，答案都是0

17.曼哈顿距离和切比雪夫距离转化

18.gets()读入整行字符串，然后再 处理。

20.计算三角形面积。

21.二分图带权最大匹配

如果左部点只连接两个边，可以认为是两个右部点之间连接了一条边。

形成了一个无向图（可能不连通），相当于给边定向。

1.保留“a+b*根号”的形式：构造有序数对：(a,b)，即可定义乘法。

23.快速质因数分解：

如果要多次询问在1e7范围内的质因数分解，可以利用线性筛预处理每个数的最小质因子，然后不断除以mindiv，即可在低于logn时间下完成分解。

而且质因子已经自动排好序了。

24.十进制快速幂（专治高精快速幂）

和二进制快速幂原理一样。

每次x要左移一位，相当于一个快速幂$log_2 {10} $次。

但是，当y是一个高精度的时候，如果用十进制储存，每次/2是O(长度)的，会TLE。

然而十进制快速幂直接舍弃最后一位，可以O(1)进行移位。

（由于复杂度在低精度下是一样的，所以除了高精快速幂，并没有什么卵用）

对于O(1)判断si是sj的循环节：

证明方法类似kmp的循环节证明。

如果n是0，m是1的话，那么C(0,1)=0，那么就是0了。

28.所有取值的前k最值问题

考虑每个可能的决策点是否有贡献。

1.起初把每个点的最优解找出来，带着点的id，放进堆里面。

2.从堆里取出最优解。

3.把和这个id有关的次优解找出来，放进堆里。

适用于一些有固定可能存在的决策点。并且能够快速找到和这个点有关的第k优的值。

枚举每个决策点，计算决策点包含的物品的贡献——>枚举物品，计算对能产生影响的决策点的贡献。

后者，用于计数，就是分开考虑每个元素。对于最值决策，计算之后直接对决策点取最值。

工具——编译选项——编辑器——编辑时加入以下命令：-W -Wall

 31.对于一些序列两次取值的问题（两次取值位置不相交）

可以正着dp，f[i],前i个位置选择一个

再反着dp，g[i]i~n位置选择一个。

然后枚举分界点，即可。

一个数的所有非空前缀组成的数都是素数。

然而，雪球数有最大的数并不是无限的：

2.桌面新建文件。打开。

6.输入cd Desktop进入桌面界面（忘了文件名，输入ls Desktop 显示桌面的所有文件）

8.如果回车之后，没有其他信息（没有error），那么编译成功。

9.接下来输入./my.exe （注意之间没有空格）表示进入这个exe

然后类似windows下的cmd，直接输入数据即可。

 （按动↑可以寻找上面进行过的命令）

排序时，求向量旋转角的时候，用atan2(y,x)比较好

既可以保证精度，而且范围是在(-Pi,Pi]的。可以表示所有的旋转角。而且，如果atan2(t,0)的话(t>0)，会返回Pi/2,

适用于：FFT等需要四舍五入以及处理-0.0的情况。
（注意，负数的时候，强转int是向中取整，floor是向下取整，有所不同。看情况决定）

而且，FFT最后输出的时候，

用欧拉遍历序遍历树，然后RMQ记录深度。LCA就是之间深度最浅的，O(1)查询

38.堆优化dij的一个小剪枝

1.不必每次把所有的出边更新到的都加入到堆里

这样常数会小一些。多次dij，优化就明显了。

2.还可以用num记录已经确定的点的个数，如果num=0直接return

适当减少了常数（但是如果要多次dij的话，别忘了清空堆）

39.关于平均值的二分

上面有中位数的二分，平均值也可以二分

每个数减去平均值，如果区间和大于等于0，那么可以

一个有向图，S到T经过至少k条边的最短路，这个要T自己和自己连个自环，表示保留下来

缩减冗余状态：各种DP中用到

合并类似转移及状态：数组平移，维护分段函数，

修改之间忽视并不会变的：虚树、动态DP

42.异或下线性方程组的自由元个数：

然后高斯消元，如果某一个id找不到，那么一定是自由元了，计数器++

注意，每次找i和消除必须在全局位置，并且用一个vis标记表示是否还能动（因为有时候存在自由元X_i，但是第i行其实还能用）

最后削成的上三角矩阵，除了无解情况，剩下的一定有唯一解

（一般的线性方程组也是这样求，只不过xor下的自由元用的比较多）

43.一个通用技巧是：

f范围宽松好统计，g范围严格难统计但是和答案有直接关系，

这样，只要得到f和g的关系，就可以找到答案！

经常是可以得到f由g的表达式，然后斯特林反演或者二项式反演得到g的求法

数论函数的反演也可以这么做。

一些对于字典序大小，或者二进制下有大小比较限制的按位操作的题

枚举LCP可以有效体现比较大小的“实质”

一般外层枚举LCP，内层用DP处理方案。

46.一种生成函数还原序列的方法

有时候，两个生成函数卷积起来，要展开以后求x^k的系数，但是k很大。

①如果一个生成函数的次方的话，就是组合意义小球放盒子了，O(1)有公式，LUCAS求组合数

②否则考虑能不能把其中一个的生成函数变成有限项，使得项数在O(n)以内

47.给DAG转移重新定向

可以做到O(sqrt(m))的出边个数。支持暴力枚举

基于动态DP的思想，记录往轻儿子的贡献。重儿子现场计算。

便于打标记。便于写。（毕竟是静态树）

1.有标号图计数，F表示所有情况，G表示连通情况。则：G=Ln(F)

②把答案大的变小，仍然满足单调性，所以取最小值方案还是不变的。

4.求积分时候，处理分式分母。

前提是求一个分子分母都是连乘积的分式

可以考虑表示成：x*p^y的pair形式，最后上下把p的次数相减（类似扩展Lucas）

显然这样取模，mod的次数不会减少。

显然DINIC的瓶颈在于增广。

所以一些必然不会到达T的点就不用访问了。

所以从T开始搜分层图。

虽然一些点S不能到达，但是浪费的只是BFS的常数，反之浪费的就是增广时候的常数了。

O(p)预处理，O(1)任意底数，任意质数的快速幂

对于$G^{x}$可以直接预处理

 54.树上点集到点集的最大值

一个常用的套路：一个树上点集的直径，可以直接合并两个集合得到。四个端点C(4,2)计算即可。

猫的某个随机连通块直径题、安师大的某个O(n^4)预处理二分+前缀和查询、51nod1766

55.编号区间点集，信息可以合并？

一个常用套路：编号区间？线段树！线段树区间维护这个区间的信息即可

56.不能立刻决定球的颜色？

每个球的颜色个数固定，不能放一个球就染色

可以先认为是白色，然后某一个时刻钦定k个白色成为某一个颜色。只要知道之前有多少个白色就可以了。

如果遇到矩阵乘法套多项式，最后就求一个多项式的系数的话，可以考虑用IDFT的trick降低常数

具体是：直接把转移矩阵的x换成$w_N^i$，得到$Ans(w_N^i)$最后再插值。

一个乘法的常数，比卷积的常数小太多了。