快速傅里叶变换 FFT
前置内容
卷积
两个长度分别为 n+1n+1n+1 和 m+1m+1m+1 的序列 a,ba,ba,b 的卷积定义为一个长度为 n+m+1n+m+1n+m+1 的序列 ccc ，其中 ccc 的每一项满足：
ci=∑j=0iajbi−jc_i=\sum_{j=0}^i a_jb_{i-j}
ci=j=0∑iajbi−j
多项式
两个次数分别为 nnn 和 mmm 的多项式 A(x)=∑i=0naixiA(x)=\displaystyle\sum_{i=0}^n a_ix^iA(x)=i=0∑naixi 和 B(x)=∑i=0mbixiB(x)=\displaystyle\sum_{i=0}^m b_ix^iB(x)=i=0∑mbixi 的乘法结果定义为一个次数为 n+mn+mn+m 的多项式 C(x)=∑i=0n+mcixiC(x)=\displaystyle\sum_{i=0}^{n+m} c_ix^iC(x)=i=0∑n+mcixi ，其中 ccc 的每一项满足：
ci=∑j=0iajbi−jc_i=\sum_{j=0}^i a_ ...
更优的区间互质对个数算法
目前我可以做到 O(n1.5logn)O(n^{1.5}\log n)O(n1.5logn) 时间， O(n)O(n)O(n) 空间。
题目描述：
给你一个长度为 nnn 的排列 aaa ， mmm 次询问，每次询问区间 [l,r][l,r][l,r] 内互质对个数。
互质对定义： 一个有序二元组 (i,j)(i,j)(i,j) 为互质对，当且仅当 i<ji<ji<j 且 gcd(ai,aj)=1\gcd(a_i,a_j)=1gcd(ai,aj)=1 。
区间内二元组定义： 一个有序二元组 (i,j)(i,j)(i,j) 在区间 [l,r][l,r][l,r] 内，当且仅当 l≤i<j≤rl \le i<j \le rl≤i<j≤r 。
n,m≤5×104n,m \le 5\times 10^4n,m≤5×104 ，
时间限制 1s1s1s ，空间限制 512MB512MB512MB 。
首先使用莫队暴力移动需要每次得到一个区间内有多少个数字于已知数字互质。这个可以预处理质数和因数然后 2ω(n)ω(n)2^\ ...
肚子的爷爷操纵天气使小 ζ\zetaζ 挂大分
本文内容在作者本人经历下参考 这里 文学化改编，如小 ζ\zetaζ 、肚子的 等名字在现实生活中如有雷同，实属巧合，无影射现实的任何成分。
五月，即使已过谷雨，冰冷的寒气尚未完全褪去，但也一天天热下去，仿佛在对气温求导一般一层层如链式法则地剥去寒气的外壳。
小 ζ\zetaζ 是一个 生中初 ，上学期在 中期试考 中表现平平，获得了高达一个 名四十第语英 和一个 名六十第分总 。浑浑噩噩度过一年之后，他再次踏上征途。
他为了不被 肚子的 甩开太远，觉得顺便参加一下 Day1 下午的英语考试，摸一摸底（被打击），当作 Day2 上午数学的安慰赛。小 ζ\zetaζ 对此心里完全没底，觉得自己能及格的概率低于投掷一枚质地均匀的硬币结果立在地上的概率——虽然他知道后者几乎为零。
天气不佳。肚子的 大手使前一天晚上起就下起了淅淅沥沥的小雨。小 ζ\zetaζ 预感着，选手们的分数就将要如同如雨水一般不断流逝，肚子的 大手将如这风一般夺去选手们仅剩的尊严，挂掉更多的分。而他，大概会是挂得最多的那个。
小 ζ\zetaζ 早早来到考场，却发现早上 ...
肚子的爷爷操纵天气使小 ω 挂大分
本文内容在作者本人经历下参考 这里 文学化改编，如小 ω 、肚子的 等名字在现实生活中如有雷同，实属巧合，无影射现实的任何成分。
五月，即使已过谷雨，冰冷的寒气尚未完全褪去，但也一天天热下去，仿佛在对气温求导一般一层层如链式法则地剥去寒气的外壳。
小 ω 是一个 生中初，上学期在 中期试考 中一鸣惊人，获得了高达一个 名二第语英 和一个 名三第分总。精心备战一年之后，他在此踏上征途。
他为了打爆 肚子的，觉得顺便参加一下 Day1 下午的英语考试，虐一虐全场，当作 Day2 上午数学的信心赛。小 ω 对此信心十足，觉得自己没有 AK\text{AK}AK 的概率高于投掷一枚质地均匀的硬币结果立在地上的概率。
天气不佳。肚子的 大手使前一天晚上起就下起了淅淅沥沥的小雨。小 ω 预感着，选手们的分数就将要如同如雨水一般不断流逝，肚子的 大手将如这风一般夺去选手们仅剩的尊严，挂掉更多的分。
小 ω 早早来到考场，却发现早上操场上聚集着一群 生学小，叽叽喳喳的。他把自己的物品在架子上摆得整齐之后，毕恭毕敬地站着。旁边几个 _生学小_一边大吵大闹，抛出的一枚 ...
大战 YNOI ——我真的会数据结构吗（一）
YNOI 的题目非常毒瘤……数据结构天花板。
——我。
T1 ：[Ynoi Easy Round 2016] 掉进兔子洞
题目链接： [Ynoi Easy Round 2016] 掉进兔子洞 。
题目内容：
给定一个序列，每次给三个区间 [l1,r1],[l2,r2],[l3,r3][l_1,r_1],[l_2,r_2],[l_3,r_3][l1,r1],[l2,r2],[l3,r3] ，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。
序列长度 n≤105n \le 10^5n≤105 ，询问次数 m≤105m \le 10^5m≤105 。
时间限制 3s3s3s ，空间限制 500MB500MB500MB 。
第一眼看这个题目就可以感觉到我们之前学的知识，像线段树，是很难发挥作用的。
而这个题目主要是区间问题，那么第一想法自然是使用莫队暴力跑三个区间，复杂度 O(n116)O(n^\frac{11}{6})O(n611) ，显然会炸。
那么此时就只能想办法把三个区间拆开了。
首 ...
回文自动机 PAM
PAM 基本内容
确定性有限状态自动机
B站视频：确定性有限状态自动机
OI-Wiki: 确定性有限状态自动机
一个确定性有限状态自动机 DFA 是一个五元组 (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F)(Q,Σ,δ,q0,F) ，分别指：
有限状态集合 QQQ ：如果把一个 DFA 看成一张有向图，那么 DFA 中的状态就相当于图上的顶点。
有限字符集合 Σ\SigmaΣ ：自动机里面只有这些字符。
转移函数 δ\deltaδ ： 定义在 Q×Σ→QQ \times \Sigma \rightarrow QQ×Σ→Q 的一个函数，接受一个状态 q∈Qq \in Qq∈Q 和一个转移字符 $c \in \Sigma $ ，结果是另一个状态 q1∈Qq_1 \in Qq1∈Q 。如果把一个 DFA 看成一张有向图，那么 DFA 中的转移函数就相当于图上的边。
起始状态 q0∈Qq_0 \in Qq0∈Q ：自动机的初始状态。
可接受状态集合 F⊆QF \subseteq QF⊆Q ：自动机的可接受状态，也叫终止状态。
以下代码 ...
分享内容：Video_1775655647320_51.mp4等4项 分享链接：点击
题解： NOIP2017 D2 T3 列队
题目链接： 列队
题目描述：
有一个 nnn 行 mmm 列的方阵，初始时第 iii 行第 jjj 列的学生编号为 (i−1)∗m+j(i-1)*m+j(i−1)∗m+j 。
现在要支持 QQQ 次操作：将第 xxx 行第 yyy 列的学生移除，然后让第 xxx 行第 yyy 行右侧的学生向左移动，接着让第 mmm 列第 xxx 行以后的学生向上移动，最后将移除的学生放入第 nnn 行第 mmm 列，并输出他的编号。
n,m,Q≤3×105n,m,Q \le 3 \times 10^5n,m,Q≤3×105 ，
对于一部分数据，保证 x=1x=1x=1 。
以下认为 n,mn,mn,m 同阶
x=1x=1x=1 怎么做
这也就意味着只有第 111 行和第 mmm 列的数据有用，可以使用平衡树进行维护，每次将第 yyy 个学生取出后放入末尾即可。
不保证 x=1x=1x=1 怎么做
此时如果空间足够，可以仿照 x=1x=1x=1 的做法，对每一行前 m−1m-1m−1 个位置开一个平衡树，第 iii 行的平衡树编号为 iii 。再 ...
二项式定理的研究
杨辉三角
我国南宋数学家杨辉使用了如下三角形解释二项式展开的规律：
在这个三角形中，第 iii 行有 iii 个数。第 111 行的数字为 111 ，第 i(i≠1)i(i \ne 1)i(i=1) 行的第 j(1<j<i)j(1<j<i)j(1<j<i) 个数字为其上方两个数字之和，即，第 i−1i-1i−1 行第 jjj 个数字和第 i−1i-1i−1 行第 j−1j-1j−1 个数字之和。第 iii 行第一个数字和最后一个数字为 111 。
杨辉认为，这个三角形中第 iii 行第 jjj 个数字为 (a+b)i−1(a+b)^{i-1}(a+b)i−1 中 aj−1bi−ja^{j-1}b^{i-j}aj−1bi−j 的系数。
二项式展开
二项式是形如 (a+b)n(a+b)^n(a+b)n 的式子。这类式子可以使用多项式乘法将其展开成几个只与 a,ba,ba,b 有关的式子。
比如， a+b=a+ba+b=a+ba+b=a+b ， (a+b)2=(a+b)(a+b)=a2+2ab+b2(a+b)^2=(a+b)(a ...
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.
Quick Start
Create a new post
1$ hexo new "My New Post"
More info: Writing
Run server
1$ hexo server
More info: Server
Generate static files
1$ hexo generate
More info: Generating
Deploy to remote sites
1$ hexo deploy
More info: Deployment
