组合数学与计数 DP （二）
其实 FFT 也算组合数学。
Lucas 定理
给定 n,m,pn,m,pn,m,p ，保证 ppp 为质数，求 Cn+mm mod pC_{n+m}^m \bmod pCn+mmmodp 。
题目： Lucas 定理 。
Lucas 定理：
若 ppp 为质数，则有：
Cnm mod p=C⌊np⌋⌊mp⌋Cn mod pm mod p mod pC_n^m \bmod p=C_{\lfloor \frac{n}{p}\rfloor}^{\lfloor \frac{m}{p}\rfloor}C_{n \bmod p}^{m \bmod p} \bmod p
Cnmmodp=C⌊pn⌋⌊pm⌋Cnmodpmmodpmodp
证明：
引理 2 ：
对于质数 ppp ，有 (1+x)p≡1+xp(modp)(1+x)^p \equiv 1+x^p \pmod p(1+x)p≡1+xp(modp) 。
令 n=ap+b,m=cp+dn=ap+b,m=cp+dn=ap+b,m=cp+d 。
则有：
(1+x)n≡(1+x)ap(1+x)b ...
组合数学与计数 DP
这东西博大精深……
前置内容
排列组合
nnn 个数的排列：将这些数放在一个序列中，与这些数的顺序有关。 例如， 1,2,31,2,31,2,3 和 3,2,13,2,13,2,1 是不同的排列。
nnn 个数的组合：将这些数放在一个可重集中，与这些数的顺序无关。 例如， {1,2,3}\{1,2,3\}{1,2,3} 和 {1,3,2}\{1,3,2\}{1,3,2} 是同一个组合。
AnmA_n^mAnm ，表示从 nnn 个不同的数中选 mmm 个数进行排列的方案数。
CnmC_n^mCnm ，表示从 nnn 个不同的数中选 mmm 个数进行组合的方案数。
引理 1 ：
Anm=n!(n−m)!A_n^m=\frac{n!}{(n-m)!}
Anm=(n−m)!n!
Cnm=n!m!(n−m)!C_n^m=\frac{n!}{m!(n-m)!}
Cnm=m!(n−m)!n!
证明：
AnmA_n^mAnm 可以看作将 nnn 个不同的数选 mmm 个数放在一个长度为 mmm 的序列上。序列的顺序重要。 所以第一个位置上可以放 nnn ...
快速傅里叶变换 FFT （二）
Chirp-Z Transform
FFT 可以求单位根为公比的等比数列在多项式函数上的点值。
Chirp-Z Transform 是一种可以求任意数为公比的任意长度的等比数列在多项式函数上的点值。
设 nnn 次多项式 P(x)=∑i=0n−1aixiP(x)=\displaystyle\sum_{i=0}^{n-1}a_ix^iP(x)=i=0∑n−1aixi 和整数 c,mc,mc,m ，则 Chirp-Z Transform 可以快速求出 P(1),P(c),P(c2)⋯P(cm−1)P(1),P(c),P(c^2)\cdots P(c^{m-1})P(1),P(c),P(c2)⋯P(cm−1) 。
引理 12 ：
ij=Ci+j2−Ci2−Cj2ij=C_{i+j}^2-C_i^2-C_j^2
ij=Ci+j2−Ci2−Cj2
证明显然。
设 ansi=P(ci)ans_i=P(c^i)ansi=P(ci) ，则有：
ansi=∑j=0n−1ajcijans_i=\sum_{j=0}^{n-1} a_jc^{ij}
ansi ...
快速傅里叶变换 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项 分享链接：点击
