OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

『多项式』Karatsuba乘法/FFT&NTT/多项式运算

【前言】

传统的高精度乘法大家早在NOIP之前肯定都会写了,然而这个方法需要严格O(n^2)的时间复杂度,在大多数时候表现不好。至少在刚开始的时候我认为这是无法优化的,但实际上,这个问题有多种更优的解决方法。

这篇笔记首先介绍基于分治的Karatsuba乘法,开启优化高精度乘法和多项式乘法的思路。接下来重点介绍FFT和NTT的原理和实现,最后再使用这些方法或技巧来加速一些多项式的运算。

(maya为什么感觉这么严肃>_<)

Karatsuba乘法

考虑一个优化算法的常见方式,即通过分治把一个问题划分成几个规模相同的子问题,并在一个能接受的时间内进行合并。我们考虑两个Base...

『数论基础』线性筛/积性函数/反演

【线性筛】

顾名思义,线性筛即是在线性复杂度(或接近线性复杂度)内筛出某些特定的函数值(往往是积性函数)。常用的线性筛有埃拉托色尼筛法和欧拉筛法两种,前者时间复杂度略高,后者需要额外的辅助空间。

埃拉托色尼(Eratosthenes)筛法:


可以证明埃拉托色尼筛法的时间复杂度为O(nloglogn),空间复杂度为O(n)。显然每个数都会被它的每一个质因数筛去,但普通的埃拉托色尼筛法无法判断每个数最小的质因数,以及每个质因数的次数(可以增加辅助数组来实现,但这样的话各方面来说都不如下面的欧拉筛法了)。

埃拉托色尼筛法适用于需要根据每个数所有质因数的函数值来计算这个数的函数值的情况(虽然这...

『群论』置换群/Burnside引理/Pólya定理

【置换群】

先分别准备置换和群的定义和部分性质。

给出一个集合G和集合G中元素的二元运算"*",倘若满足以下性质:


则称集合G在运算"*"下是一个群。以上四个性质依次称为封闭性、结合律、单位元和逆元,注意群不一定满足交换律,例如置换群就不满足。

将元素的变换用矩阵的形式表示的一一对应关系叫做置换,例如:


置换之间的运算称为置换的连接或置换的合成:


这样的运算一般不满足交换律:


那么顾名思义,置换群的元素就是置换,运算就是置换的连接。

【Burnside引理】

这个引理大概是解决这样一类问题:设有一个关于某一方案集的置换群,假如两种方案可...

© OI技术宅 | Powered by LOFTER