1.坐标(代数)形式：

当b为0是z为实数，当a为0时为纯虚数

注:复数包括实数和虚数，虚数下有纯虚数

虚数z对应了复平面上的一点(a,b)

几何意义:相当于把该复数 拉长/缩短 到另一个复数模长 倍/分之一 ,然后 顺时针/逆时针 旋转另一个复数的幅角大小的角度

于是有了如下非常有用的公式:

这个算乘除法就更好算了:

上面的那个公式就可写成这样：

学FFT最重要的就这个了吧

不难发现其实\(n\)次单位复数根就是把复平面上的单位圆 \(n\) 等分后的那些\(n\)等分点

一些次数单位的单位根举例:

可以发现1是任意次的单位复数根，-1是任意偶数次单位复数根

把复数的指数形式带进去就可以了
说人话就是不同次数的单位根可以互相转化

假设\(n\)是大于0的偶数:

说人话就是n次单位复数根的前后两半平方后是对应相等的

对于大于1的整数n和小于等于n的整数k有:

常规的一个最高次数为n-1的多项式的表示形式是系数表示法,如:

按照朴素的多项式乘法(卷积),就是每一项两两相乘，复杂度为\(O(n^2)\)

如果我们把多项式看成一个函数，我们取图像上的n个点来表示这个函数也即该多项式，这样的表示法叫做点值表示法

对于两个n-1次多项式,由于我们最后卷积出来的多项式是2n-2次的,如果我们知道了卷积后的多项式函数图像上的至少2n-1个点，那么我们就可以确定这个多项式了

现在原来的两个多项式上选取好x值相同的点(个数为原来两多项式次数的和加1)，用\(O(n)\)的时间将选的点的y值相乘，得到的值用某种方法(待定系数法)转化为多项式系数的形式

如果选取的x都是n次单位复数根的k次方，那么以上两个过程就是\(DFT\)和\(IDFT\)了

本人太弱不会证，丢个式子:

由于写的时候系数表达式和点值表达式是共用的数组，所以写起来和\(DFT\)没什么差别

是一种快速求出\(DFT\)和\(DFT^{-1}\)的算法，利用了单位复数根的优良性质

根据折半引理,我们可以发现:

以n=4的情况来考虑:

把每一个多项式的偶数次数项的系数提出来组成的多项式记为\(A^{[0]}(x)\),奇数项记为\(A^{[1]}(x)\)

奇数项就没有这么优美的性质,但是我们可以提出来一个x使得它变成偶数项
所以我们现在考虑把一个多项式奇偶分组:

那么我们知道如果把上面的分成两半,根据折半引理:前后两半对应的只有后面要乘上的单位复数根不一样,所以其实我们已经把问题的规模缩小了一半了,因为我们只需求解如下东西:

所以说其实只是后面的系数的符号不一样

再来观察一下现在要求的东西,可以发现如果把整个子问题也进行奇偶分组的话,每一组其实要求的是长度为原来一半的\(DFT\),如果采用递归进行处理,那么递归分组一次之后

于是我们只要计算这4个子问题原\(DFT\)的两边就都可以直接算出来了
并且对于该子问题,我们也只需求解\(A^{[0]}(w_2^0)和A^{[1]}(w_2^0)\),另一半也是和上面的一样由这一半推出,因为这是一个长度为原来一半的\(DFT\)

我们先看看递归版应该怎么实现:
1.不停将要求的\(DFT\)进行奇偶分组并递归下去
2.如果只有一个元素,显然这时\(x=w_1^0=1\),直接返回当前的系数就可以了
把每层要求的东西写出来:

根据上面的公式就很容易知道每个元素是由下一层的哪一个得来的了,这很像个蝴蝶,于是被成为蝴蝶操作

还没有理解的话可以看看8的情况,建议自己手画一下,标出贡献来源,这样就很容易理解了

从下往上蝴蝶的跨度不断增大,倒数第2层就是相邻的两个元素宽度半径为1,然后往上不断倍增
,每一次只是改变两个位置对应的数,所以其实也可以写成非递归的
但是我们需要最后分组后的最下面一层
其实每个数最后在的位置是他的二进制反序数,所以是一个Rader排序(二进制反转),这个并不是非常重要,记一下就差不多了

1.由于FFT有大量实数运算,不仅常数大,精度也会有很大问题,转化为整数时要四舍五入。
2.注意蝴蝶操作的式子不要记错, Y 要乘上单位复数根!

在模意义下有如下结论:

其中\(g\)是\(p\)的原根,然后就直接把这个代换进FFT模板就可以了,加上模意义下的基本操作

常用NTT模数以及其原根:

1.如果确定计算结果不会超过你的 NTT 模数,那么可以用 NTT 来代替 FFT 进行运算

两部分,那么可以把每一个多项式拆分为两个系数都不超过\(M\)的多项式,分别\(DFT和IDFT\),最后还原出系数并对原模数取模即可,这样的话最后的系数最大可能达到 \(nP\) 的级别,要确保\(long\ long\)能存下

3.多项式的一些基本操作

之后回代并在两边乘上\(F(x)\),变形可得:

所以不断递归就行了,如果模数不是 NTT 模数,那么需要 MTT
边界就是当 n=1 的时候直接求逆元

首先你可能会想,除法不就是乘上多项式的逆吗,所以直接求逆即可。
但是你会发现好像这个东西没办法下手，因为有次数限制和余数,并且这个不是多项式求逆的式子的形式。
所以我们必须要找到一种方法使得能够把式子转化为能和多项式求逆搭上边的。

这下终于能用同余式来表示原式子了,并且未知多项式还能够少掉一个:

这下只要求出多项式\(G_R(x)\)的逆然后乘法就得到了\(Q_R(x)\),翻转回去就可以进一步通过多项式乘法得到\(R(x)\)

求对数函数直接两边求导就可以了:

只需要会求导,求不定积分,多项式求逆就行了

首先你需要学会牛顿迭代,这是个不断求导并迭代来求函数零点的方法。

倍增求出这个东西,需要 多项式求\(ln\) 的所有内容(注意求ln的数组要清空)

\(P.S.\): 一个常错点,当运算在 \(mod\; x^n\) 下进行时,一定不能合并点值相乘的步骤,必须一次次来,并把多余的项赋成 0

根据多项式取模的原理，因为除式是一个一次时，那么结果只有常数项。

接下来就是多点求值的方法了。

这样我们先用 分治+多项式乘法 来求出每一个线段树上节点的 \(P(x)\)， 然后递归分治进取求解点值，到了最底下的点值就是其 \(F(x)\) 的常数项了。

为了卡常可以当当前区间长度较小的话改用暴力直接计算点值。

拉格朗日插值与多项式多点求值。

前面的那部分就可以直接多点求值先全部算出来了。

然后就是处理后面的部分了，这个东西也可以类似分治的求。
设 \(F_{l,r}(x)\) 表示 \([l,r]\) 内的点插值出来的多项式，那么这个东西可以由左右两边合并得到，具体来说是:

(并不知道这玩意有什么鸟用)

三角函数诱导公式...

(这个就更加不知道有什么鸟用了)

求导和积分随便化一下就弄出来了，你需要一个反三角函数求导公式。
直接扔出最后的式子了:

我们知道假设有两个多项式 \(A,B\),他们的多项式卷积可以写成以下形式(中间打个乘号的话表示的是按位相乘,没有则为卷积)

但假设现在有一个问题是给你两堆集合,求出在两堆中各选出一个集合使得他们的并集是某个集合的方案数

这个问题其实就是要求出以下形式的卷积:

现在就要找到一种方法能够快速求出以上卷积。

仿照\(FFT\)的方法,我们希望找到一种变换\(FWT\),能够使得:

以上操作类似于\(FFT\)点值相乘,复杂度为O(n),这样的化我们通过找到一种\(FWT\)的逆变换\(IFWT\)就可以还原出结果多项式了

一下开始讲三种位运算的卷积,注意之后的下标可以将其理解为一个集合

显然可以用分配率提出来\(A_p\)

万事大吉,这样就找到一种优秀的\(FWT\)形式了

剩下的就是看怎么快速求出这个\(FWT\)和\(IFWT\)了

如果你去看很多其他人的博客,他们会通过分治思想,多项式拼接什么的把非巨佬以外的人绕的云里雾里,然后再甩给你一个代码。
但是你没发现或运算下的\(FWT\)就是个子集的前缀和吗,所以直接用高维前缀和求就行了。

\(FWT\)的精髓在于构造优秀的变换形式,求解变换就是高维前缀和。

至于为什么可以写成和\(FFT\)代码高度相似,是因为那个是直接枚举已经确定下来的\(1\)左右两边的0/1情况,理论上能少一半的常数,但是会多一重循环(说不定常数更大了),也就是长成这样:

后面那个减法就是 \(IFWT\)了,就是把高位前缀和的操作反着来一边就行了,把子集的和减去就得到原本自己的值

与和或运算非常相似,所以找\(FWT\)的思想一样,直接把子集前缀和换成超集前缀和就行了:

后面的推导是一样的,求解\(FWT\)也一样高位前缀和解决,代码如下:

仅仅只是把操作的对应数组下标前后交换了一下,其他一模一样

异或的话要自己瞎找就有点难了只能直接放结论了:

不过这个代码写起来就真的可以和\(FFT\)一模一样了,代码:

\(FWT\)的主要难点(其实就由这两部分构成),一是构造出合适的\(FWT\)变换形式,而是能够快速求出\(FWT\)及\(IFWT\)

答案差不多了，却被%u7b和%u7d卡住了，猜想是{ }的url编码，{的url编码是%7B，}的url编码是%7D

所以去掉u符号（这里u符号应该是什么十六进制之类的，我也不知道）

下载附件，打开，发现两个等号和19azA~Z的典型base64编码型，直接base64转换：

转了一堆&#出来，根据以前的做题经验，猜unicode或hex：

一开始用了十六进制来转，转了个四不像出来，后来发现转错了，unicode在线解码网址：

这三个数的看着像ASCII，因为题目暗示混合编码，直接转换看看：ASCCII表对照法：

python2 /和yafu分解n肯定是分解不出来的，毕竟是2048bit嘛。所以我们需要一些算法，比如前面模不互素的欧几里得算法这样，这里我们要用的是费马分解算法。

费马分解算法的特征就是n是4个数的乘积，分解n之后我们会得到p、p1、q、q1四组隔开的排列组合，但是我们的脚本可以把组合限定成 p * q1， p1 * q 和 p * q ，p1 * q 这样。然后通过欧几里得算法求公因子的封装函数 gcd(pq1,pq) = p、gcd(p1q,p1q) = q 求出两组各一个数，然后就可以求出

然后后面的参考以前积累的RSA解密流程做即可：

RSA公开密钥密码体制是一种使用不同的加密密钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制 。

在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK [2] 。

RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥 [4] 。

RSA脚本工具使用说明：

# 第三届上海市大学生网络安全大赛--rrrsa d泄漏攻击

（模不互素是给你两个单独分解不了的大数级n，方便让你求公因子。然后，只用一个n来加密，对，只用一个n。）

RSA通用的简单脚本：（已知p、q、e、c值）

椭圆曲线密码学（英语：Elliptic curve cryptography，缩写为 ECC），一种建立公开密钥加密的算法，基于椭圆曲线数学。

ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA加密算法——提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射，基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。其缺点是同长度密钥下加密和解密操作的实现比其他机制花费的时间长 [1] ，但由于可以使用更短的密钥达到同级的安全程度，所以同级安全程度下速度相对更快。一般认为160比特的椭圆曲线密钥提供的安全强度与1024比特RSA密钥相当。

设私钥、公钥分别为k、K，即K = kG，其中G为G点。

　　选择随机数r，将消息M生成密文C，该密文是一个点对，即：

　　其中k、K分别为私钥、公钥。

ECC脚本积累(解出最后的公钥和私钥即可)：