{"posts":[{"title":"点分治","content":"点分治 树上分治 分为边分治和点分治，其中只有点分治可以保证 log⁡n\\log nlogn 的复杂度。 分！ 找重心 找其他被分开树的重心 continue 治！ 额...归并 无了 例题1 给定一棵树，树上路径大于 kkk 的路径总数有多少。 树 ","link":"https://evrgardenviolet.github.io/post/dian-fen-zhi/"},{"title":"闲人の题解P7919","content":"Step_1 题目简述 对于一个有 ABCABCABC 组成的序列 SSS 可执行如下操作： 选择一个区间 [l,r]\\left[l, r \\right][l,r] 。 对于选择的区间而言可以将其中所有 AAA 变为 A,B,CA, B, CA,B,C 中的任意一个。 BBB 和 CCC 同理。 我们需要通过以上两个操作是的序列 SSS 相邻两个字符不相等， 求最小步骤和方案。 题目传送门 Step_2 题目分析 不难发现， 此题是一道标准的构造体。 根据题目描述，可以发现序列 SSS 的如下性质。 假设我将一个区间中的所有 AAA 变成 BBB ， 所有 BBB 变成 CCC ， 所有 CCC 变成 AAA ，那么区间内（除两端）原本与相邻字符不同的依然不同， 原本相同的依然相同，也就是说区间（除两端）的本质不变。 我们一次性最多只能使两个原本与相邻字符相同的字符变的与相邻字符不同。 对于第二点而言， 需要同学们好好领悟一下（也许不用）。 Step_3 正解思路 通过 Step_2 的两点性质，我们不难想出如下方法： 我们指定两个指针 l,rl, rl,r ， 一个指向 111 一个指向 nnn 。 当当前指针所指与两侧的字符不相等， 那么指针向中间靠拢，否则我将指针所指区间内（不包括两端）的所有字符 AAA 变成 BBB ， BBB 变成 CCC ， CCC 变成 AAA 。 注意，在移动指针时不要其中一个找到目标字符就马上变换区间，因为我们要使步数最小， 所以每次尽量两个一起变。 (PS. 特别注意指针最后一刻的状态， 极为容易出错） AC Code 后记 月赛唯一一道作对的题 ","link":"https://evrgardenviolet.github.io/post/xian-ren-noti-jie-p7919/"},{"title":"闲人の题解 P7878","content":"Step1：题目简化&粗略分析 与我以往写的题解不同，这一篇题解的第一个部分不再是《题目描述》，而是《题目简化&分析》，因为在我看来此题最大的障碍在于题目的理解。 首先，让我们理解一下什么叫做“用同一账号连续发多个帖子”。这其中有个很重要的一点，这会影响到我们后续的做题，注意此处的“连续”，设想一个问题，如果我发的所有帖子是不连续的（也就是说我在几个账号上循环发帖），那么就不存在同一账号上的“连续的多个帖子”了。 其次，在理解了上一个问题之后再来看一下“该账号的安全指数会减小这两篇帖子安全指数的较小值”这句话做何理解（怎么感觉再讲阅读理解？）。其实很容易弄懂，这句话是指在同一账号中的连续帖子之间相邻连个帖子的最小值就是这个账号的风险，把这些值累加起来，第一篇帖子的安全系数减去累加起来的值就是这个账号的安全指数。 Step2：题目详细分析 在理解了第一部分的内容后就开始对题目进行一个较为深入的解析。 Step2_1：关于安全指数的来源 来源有二：其一，是本账号的第一篇帖子的安全指数。其二在后续发帖过程中所损失的安全指数。 Step2_2：如何使安全指数最大化 首先不难发现，总有一个账号的第一篇帖子是所有帖子的第一篇，应为所有帖子的的发帖顺序是固定的，只是在那个账号发事不固定的。 其次，根据 Step1_1 中提到的：“如果我发的所有帖子是不连续的（也就是说我在几个账号上循环发帖），那么就不存在同一账号上的‘连续的多个帖子’。”可以得出所有会损失安全值得操作会在第二个账号发了一个帖子后结束。 接下来，如果在用第二个账号发帖之后还有多余的账号，就可以用账号来发剩下帖子中价值最大的贴子以获取最大的收益。 最后一点，也是本题的关键：确定第二个账号发的第一个帖子是哪一篇。解决了这个问题，此题就结束了。 Step2_3：如何解决 Step2_2_4 中所提到的问题 设想一个问题，如果前面帖子损失的安全指数已经大于了所有账号第一篇帖子中的最小值，那么我肯定会舍弃这个帖子然后减小前面帖子的损失。 这样的话我们就可以有效的解决 Step2_2_4 中的问题。 代码分析 接下来，只讲我个人的做题方法 先对所有相邻的贴子求一遍最小值，在对最小值求前缀和预处理。 对原来序列排序，找出 k−1k - 1k−1 个最大的帖子（还有一个帖子是所有帖子中的第一个，在 Step2_2_1 中有所讲解，并且记录这些帖子中最靠前的是哪一篇，（记位置为 first_wherefirst\\_wherefirst_where ）。 枚举 222 到 first_wherefirst\\_wherefirst_where 的每一个帖子作为第二个账号的第一篇帖子所获得的最大收益，求出答案 AC code 后记 此篇题解写于 2021CSP 之前，在这里祝所有同学能在接下来的学习中跟进一步，考试中 rp++ ！ ","link":"https://evrgardenviolet.github.io/post/xian-ren-noti-jie-p7878/"},{"title":"闲人の题解 P7814","content":"P7814 题目传送门 题目简述 有两个由0和1组成的字符串 AAA 和 BBB ，其中 AAA 小于 BBB 。 其中 AAA 不是 BBB 的字串但是 AAA 却是 BBB 的子序列。 找出一个满足要求得 BBB 串并输出。 一共 TTT 组询问， AAA 串长度为 nnn ， BBB 串长度为 mmm , 其中 1≤n≤m,1≤∑m≤2×1061 \\le n \\le m , 1 \\le \\sum m \\le 2 \\times 10 ^ 61≤n≤m,1≤∑m≤2×106 题目分析 首先我把这道题分为了两个部分： 当 AAA 长度为一和二时 当 AAA 的长度在三以上的时候。 我们来分别讨论以上两种情况： 长度为 111 或 222 显然， 如果长度为 111 时一定找不到一个满足条件的 BBB 。 再来讨论 222 的情况，设想， 如果这两个数一个是 000 ， 一个是 111 ， 也不存在可行解， 事实上当 AAA 的长度和 BBB 的长度一样时也时无解的。 那么难道只要 AAA 长度为 111 或 222 就都无解吗？其实不是， 如果 AAA 形如 000000 ，那 BBB 只要像 01...1001...1001...10 就可以了。 111111 时同理。 长度在 333 以上 如果在原序列中 111 和 000 都有， 就有一种比较妙的容易想到的方法， 比如现在的序列是这样的： 011101010100111010101001110101010 我们不妨将第一个数 (0)(0)(0) 和后面所有的数分开来看，如果我在第一个数 (0)(0)(0) 的后面一直添加和它不同的数 (1)(1)(1) ， 那么后面的所有数 (1110101010)(1110101010)(1110101010) 和前面的那个新加的数 (1)(1)(1) 一定组成不了原序列。所以成立！ 那么新的问题出现了如果我的序列是这样的： 011111111011111111011111111 会发现用上一个方法不行了，应为如果在第一个数 (0)(0)(0) 后面加不同的数 (1)(1)(1) 时第一个数会和后面的数组成原序列， 俗话说特殊情况特殊处理， 我们不难想到从第二个数开始插入与后面的数 (1)(1)(1) 不同的数 (0)(0)(0) ，就像这样： 010...011111111010...011111111010...011111111 。好啦，现在这个问题也愉快的解决啦！ AC Code 后记 此题主要在于思维， 对于代码的要求极低， 但是思维一定要打开。 ","link":"https://evrgardenviolet.github.io/post/xian-ren-noti-jie-p7814/"},{"title":"lxxy题解","content":"大家好，我是搬题人闲人，这里，来讲一下这道题的正解 题目描述 略 难点 这道题我和三强讨论过后决定评一个 提高加/省选 的难度，因为此题的思维很重要，想明白了，一下就好了，想不明白就死活做不出来。 首先是关于 f(x)f(x)f(x) 的求法，为什么 f(x)=xf(x) = xf(x)=x 可能好多人没有想懂，知道了也只是在打标时无意发现的（我是不会告诉你我就是这样做对的）。所以我在这里讲一下证明： 我们先来看 numgcd(x)numgcd(x)numgcd(x) 这个函数根据题目中的定义我们不难发现这其实是欧拉函数 φ(x)\\varphi(x)φ(x) ，那么根据 φ(x)\\varphi(x)φ(x) 的性质我们可以知道两条性质： 1： 1∼x1 \\sim x1∼x 中与 xxx 的最大公约数为 1 的所有数的和等于 x⋅φ(x)/2x \\cdot \\varphi(x) / 2x⋅φ(x)/2 2： 若 φ(a)\\varphi(a)φ(a) 与 φ(b)\\varphi(b)φ(b) 互质，则 φ(a⋅b)=φ(a)⋅φ(b)\\varphi(a \\cdot b) = \\varphi(a) \\cdot \\varphi(b)φ(a⋅b)=φ(a)⋅φ(b) 显然，这一道题我们要用到的是第一条性质。 证明： $ \\because gcd(a, b) = gcd(a, a - b)$ $ \\therefore $ 与 aaa 不互质的数 bbb 和 a−ba - ba−b 成对出现，平均值为 n/2n / 2n/2 故性质一成立。 证毕。 由此可以知道 sumgcd(x)=x⋅φ(x)/2sumgcd(x) = x \\cdot \\varphi(x) / 2sumgcd(x)=x⋅φ(x)/2 又∵f(x)=2⋅sumgcd(x)numgcd(x)\\because f(x) = \\frac{2 \\cdot sumgcd(x)}{numgcd(x)}∵f(x)=numgcd(x)2⋅sumgcd(x)​ ∴f(x)=2⋅x⋅φ(x)/2φ(x)=x\\therefore f(x) = \\frac{2 \\cdot x \\cdot \\varphi(x) / 2}{\\varphi(x)} = x∴f(x)=φ(x)2⋅x⋅φ(x)/2​=x 在解决了 f(x)f(x)f(x) 的问题之后，我们还要考虑如何快速的求出 ∑i=1nf(i)k\\sum_{i = 1}^{n}f(i)^k∑i=1n​f(i)k 的值。这里我介绍一种泛用性较高的，也是做简单的方法，我们找出所有询问当中最大的一个 nnn ，在计算这一组数据时就沿路记录其他的解的值，最后统一输出就可以了。 最后附上代码： AC Code ","link":"https://evrgardenviolet.github.io/post/lxxy-ti-jie/"},{"title":"闲人の题解 P1834","content":"题目描述 1 ~ 9 的数用四则运算凑成 24。 满足答案字典序最小。 题目保证有解。 题目传送门 讲解 Round1 此题关键在于字典序。先让我们来想一想，什么情况下字典序.可以尽可能小？ (((3∗5)+2)+7)(((3 * 5)+2)+7)(((3∗5)+2)+7) 这是样例给出的答案。 观察一下，为什么他要把三个括号放在前面？ 显然，因为“()”的 ASCII 码是运算符里（仅限于本题）最小的。所以如果我们可以把式子写成 (((Aopr⁡B)opr⁡C)opr⁡D)(((A\\operatorname{opr} B)\\operatorname{opr} C)\\operatorname{opr} D)(((AoprB)oprC)oprD) （注：opr 指运算符）的形式就不需要额外考虑怎么加括号的事了！ Round2 分析一下刚刚我们处理字典序的方法，不难发现其中的 BUG！如果遇上了 $ 5 5 5 5 $ 的情况显然用刚才的表达式是无法求出解的，而只能换成 ((5∗5)−(5/5))((5* 5)-(5/5))((5∗5)−(5/5)) 的形式。所以当我们遇到这样的情况，先看一下第一种情况行不行的通，行不通再用第二种方法。 Round3 我们如何来比对那个式子的字典序最小呢？我们可以用一个 cmp 数组初始为“zzzzzzzzzzzzz”然后每搜到一个答案就把它替换掉。 Round4 深搜的思路也比较简单，先枚举四张牌，在枚举运算符，然后把得到的数值递归到下一层，最后判断是否等于 24 即可。 Round5 其他的细节会在代码注释里出现，这样方便同学们理解。 Code 后记 此题最开始做的时候以为只用第一种情况就能过，然后发现事情不对，硬是把代码写了一百七十多行。暴力的地方可能有点臃肿，希望巨佬们要是有更好的方法可以私信提出。 改了多次题解，一直LaTeX或英文少空格，不晓得是哪里的问题，望能再得到更详细的解释，谢。 ","link":"https://evrgardenviolet.github.io/post/xian-ren-noti-jie-p1834/"},{"title":"闲人の题解 P7522","content":"主要是一个巧妙的思路 题目传送门 题目分析 有一堆数，然后那两个数，让一个去减另一个得到一个新数，然后放在这堆数里 求最后一个数最大。 $ 1\\le n\\le 3\\times 10^{5} , \\left |v_i \\right | \\le 10^{9} $ 思路 首先我们看几个样例： 3 1 2 3 ans $ = $ 4 4 -4 5 -2 -3 ans $ = $ 14 8 2 0 2 1 0 4 2 3 ans $ = $ 14 可以发现第二个样例和第三个中ans的值是所有数的绝对值之和，但是第一个样例并非如次。于是我们自己造几个数据： 6 1 1 1 1 1 1 ans $ = $ 4 6 -1 1 1 1 1 1 ans $ = $ 6 同样是六个数，为什么一个负数的差别使得一个答案是4，另一个是6。 顺着这个思路我们可以对数列中的正负性分析出一下结论： 正数 −-− 负数 可以得到一个最大值。 负数 −-− 正数 可以得到一个最小值。 当且仅当数列中存在异号的数才可以把所有的负数转化成正数从而得到最大值。 如果数列中只有同号的数则 （1）若全是负数，则把最大值转化成正数，使数列中存在异号情况。（2）若全是正数，则把最小值转化成负数数，使数列中存在异号情况。 如果只有一个数，输出去就完了。 那么我们的思路就出来了： 如果异号，则输出所有数绝对值之和。 如果同号，就输出所有数绝对值之和减两次最大（小）值。 如果只有一个数，输出去。 是不是超 简单 。 AC代码 Code： 后记 只是我唯一做出来的题。 ","link":"https://evrgardenviolet.github.io/post/xian-ren-noti-jie-p7522/"},{"title":"闲人の题解 P3866","content":"又是一道网络流的建图题 题目传送门 题目分析 有一群敌人“0”，想要走出地图。 有一些障碍“-1”，在地图上。 你可以通过用炸药把一些地变为障碍，不过每一块地变成障碍所需的炸药不同，具体是这块地的数字，如“2”。 你现在要知道阻止敌人走出地图所用的最少炸药是多少。 对100%的数据，1≤M,N≤301 \\le M,N \\le 301≤M,N≤30 思路 我们要割断敌人的路，断了的路不能走，又要使所用的炸药最少，想到了什么？ 对！ 最小割！ 又因为最大流=最小割。 所以 建图+拆点+最大流 就是正解。 亿点问题 万恶的建图总是我们成功路上的绊脚石，所以我们应该如何建图呢？ 地图上唯一在在动的是敌人，而我们要阻止他到边界。每一个块地有一个值，代表我们那至少要用多少炸药把它变成障碍（要花费多少把流割断）。 那么图的基本框架就出来了： 把所有的点拆成两个，中间连起来的流量为这个点的数值。 构建一个超级源点，把所有的敌人的入点连起来。 把所有的点的出点连上旁边点的入点。 建一个超级汇点，把所有的边界点的出点连起来。 PS.不过敌人和障碍都可以不连边，因为他们不能炸掉。 代码 Code: 后记 一些其他关于网络流的题： 狼和羊的故事 方格取数问题 家园 / 星际转移问题 ","link":"https://evrgardenviolet.github.io/post/xian-ren-noti-jie-p3866/"},{"title":"闲人の题解 P2065","content":"一道网络流的题，重在建图 题目传送门 题目分析 首先，我们简化一下题面： 有两堆数。 一次只能在两堆中分别选一个数且不互质。 求最多能取几次。 1≤n,m≤5001 \\le n,m\\le 5001≤n,m≤500 错误解 其实比较容易理解，所以我们首先想到了用二分做： 如果一个蓝色数字和一个红色数字不互质，我们就把它们连起来。 然后用一个二分跑一遍，求出最大匹配。 但是实际操作上是要T掉的，因为二分匹配有着 O(nm)O(nm)O(nm) 的时间复杂度，加上连线的时间是一定会T掉的。 正解 然后啊，我就想到可以用网络流： 因为蓝色数字和红色数字互质时才可以配对，所以可以看成蓝色的数字和红色的数字是通过它们共同的质因数连接起来的。 由于每一张牌只能用一次，所以每一条流的流量都为1。 我们把源点和每一个蓝色点连起来，把每一个红色点和汇点连起来，蓝色点和红色点由中间的质数点连起来。 最后跑一遍网络流就好了。 其中在算质数点的时候，直接用试除法就可以了，不过感兴趣的同学可以了解一下Pollard's Rho算法。 Pollard's Rho (不是我写的) 建图 接下来，还有一个问题需要解决，就是我们应该如何给点标号呢？ 这里分享一种方法 ： 因为中间的质数点个数我们是事先不知道的，所以标号红点应该放在通过蓝点算质数点的操作之后。 由此可得： 源点为“0”号点， 蓝点编号为1到 blue， 质数点编号为 blue 到 blue + total， 红点编号为 blue + total 到 blue + total + red， 汇点编号为 blue + red + total + 1。 下面是通过样例中第一个数据所建得图： 代码 最后放上AC代码，希望可以帮助大家理解 Code: 后记 这道题我改了好久才过，怎么也没有想到是head数组没有初始化“-1”的原因，希望其他同学不要犯同样错误哦！ ","link":"https://evrgardenviolet.github.io/post/xian-ren-noti-jie-p2065/"},{"title":"闲人の题解 P7441","content":"说实话，当我看到这道题时还有点懵。 但是你静下来就会发现其实是一道数学思维的题。 我们可以把题抽象一下： 有T组数据据。 每一组数据有两个等差数列，公差分别为x，y； 两个数列最大的一个数不大于K； 一些小问题 细心地同学已经发现，我好像并没有考虑-K的情况。 why？ 很简单 ∵0≤Ci,Ei≤K∵0\\le C _i ,E _i\\le K∵0≤Ci​,Ei​≤K ∴Ci+(−K),Ei+(−K)<K∴C _i+(-K),E _i+(-K) < K∴Ci​+(−K),Ei​+(−K)<K so我们可以不用考虑-K的情况 进入正解 Round1 我们看看样例中的两个等差数列： 2 4 6 8 10 3 6 9 因为每一片叶子和每一片雪花只能用一遍 所以我们可以用其中一个数列中最小的数字去加另一个数列的最大数。 为什么这样做? 不难发现 3+10=133 + 10 = 133+10=13 6+8=146 + 8 = 146+8=14 9+6=159 + 6 = 159+6=15 这是一个递增的关系 有兴趣的小朋友可以证明一下为什么。 如果加起来不足K怎么办？ 那我们就用一个数列的第一个去加另一个数列的倒数第二个数。 Round 2 新的问题又出现：应该用哪一个数列的第一个数去加另一个数列的最后一个数呢？ 再看一下样例： 2 4 6 8 10 3 6 9 可以发现我们最好情况下可以配对所有数字最少数列中的所有数，所以我们应该尽量把数字少的数列中的数字用完。 Round 3 那么思路就出来了： 找出数列短的那一个。 用这个数列的第一个去加另一数列的最后一个数，如果大于等于K，则证明这个数列中的数都能匹配，直接输出此数列的数字个数。 如果2没有执行我们就用这个数列的第一个数去加另一个数列的倒数第二个数。 Round 4 之亿点点问题 看看第二个样例是什么 1 0 0 1 有“0”？？？？？？ 没错，如果有“0”，就会比较麻烦。 如果两个公差都是“0”，那必然输出“0”，没说的 如果其中一个公差是“0”，我就还要判断另一个数列的最后一个数等不等于K，若是，就输出“1”。如不是，就只能输出“0”了 Round 5 最后还是附上代码（代码的思路有一点点不一样，它说用数列数字多的那一个数列的最后一个数依次加另一数列的1,2,3...个数） 后记 这篇题解中有些话可能有点绕，需要好好思考一下。 因为是我第一篇发的题解（前面（一年前）发过只有代码的题解没有过） 也许有不足之处，还请随时指出。 感谢阅览！ ","link":"https://evrgardenviolet.github.io/post/xian-ren-noti-jie-p7441/"},{"title":"树链剖分","content":"树链剖分 核心思想 通过给树上的每一个点重新编号，使得我们可以让树上的任意一条路径转化为 O(log⁡n)O(\\log n)O(logn) 段连续的区间。 需要处理的问题： 将树从x到y结点最短路径上所有节点的值都加上z 求树从x到y结点最短路径上所有节点的值之和 将以x为根节点的子树内所有节点值都加上z 求以x为根节点的子树内所有节点值之和 概念 重儿子：对于每一个非叶子节点，它的儿子中 以那个儿子为根的子树节点数最大的儿子 为该节点的重儿子 轻儿子：对于每一个非叶子节点，它的儿子中 非重儿子 的剩下所有儿子即为轻儿子 叶子节点没有重儿子也没有轻儿子 重边：一个父亲连接他的重儿子的边称为重边 轻边：剩下的即为轻边 重链：相邻重边连起来的 连接一条重儿子 的链叫重链 对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链 每一条重链以轻儿子为起点 如何对树进行拆分 先用 dfs1dfs1dfs1 找出轻重儿子等，然后用 dfsdfsdfs 序遍历（ dfsdfsdfs 序 指 优先遍历重儿子）。 Code ","link":"https://evrgardenviolet.github.io/post/shu-lian-pou-fen/"},{"title":"费用流","content":"网络流之费用流 费用流 给定一个 G=(V,E)G = (V, E)G=(V,E) ， 每条边除了有容量限制 c(u,v)c(u, v)c(u,v) ， 还有一个单位流量的费用 w(u,v)w(u, v)w(u,v) 。 当 (u,v)(u, v)(u,v) 的流量为 f(u,v)f(u, v)f(u,v) 时， 需要花费 f(u,v)×w(u,v)f(u, v) \\times w(u, v)f(u,v)×w(u,v) 的费用。 www 也满足斜对称性，即 w(u,v)=−w(v,u)w(u, v) = -w(v, u)w(u,v)=−w(v,u) 。 则该网络中总花费最小的最大流称为 最小费用最大流，即在最大化 ∑(s,v)∈Ef(s,v)\\sum_{(s, v)\\in E} f(s, v)∑(s,v)∈E​f(s,v) 的前提下最小化 ∑(u,v)∈Ef(u,v)×(u,v)\\sum_{(u, v)\\in E} f(u, v) \\times(u, v)∑(u,v)∈E​f(u,v)×(u,v) 。 SSP 祂死了 Primal-Dual 原始对偶算法 前置芝士： Johnson 全源最短路径算法 用 Bellman-Ford 求解最短路的时间复杂度为 O(nm)O(nm)O(nm) ，无论在稀疏图上还是稠密图上都不及 Dijkstra 算法。但网络上存在单位费用为负的边，因此无法直接使用 Dijkstra 算法。 Primal-Dual 原始对偶算法的思路与 Johnson 全源最短路径算法 类似，通过为每个点设置一个势能，将网络上所有边的费用（下面简称为边权）全部变为非负值，从而可以应用 Dijkstra 算法找出网络上单位费用最小的增广路。 首先跑一次最短路，求出源点到每个点的最短距离（也是该点的初始势能）hih_ihi​ 。接下来和 Johnson 算法一样，对于一条从 uuu 到 vvv ，单位费用为 www 的边，将其边权重置为 w+hi+hvw + h_i + h_vw+hi​+hv​ 。 可以发现，这样设置势能后新网络上的最短路径和原网络上的最短路径一定对应。证明在介绍 Johnson 算法时已经给出，这里不再展开。 与常规的最短路问题不同的是，每次增广后图的形态会发生变化，这种情况下各点的势能需要更新。 如何更新呢？先给出结论，设增广后从源点到 iii 号点的最短距离为 di′d'_idi′​ （这里的距离为重置每条边边权后得到的距离），只需给 hih_ihi​ 加上 di′d'_idi′​ 即可。下面我们证明，这样更新边权后，图上所有边的边权均为负。 容易发现，在一轮增广后，由于一些 (i,j)(i, j)(i,j) 边在增广路上，残量网络上会相应多出一些 (j,i)(j, i)(j,i) 边，且一定会满足 di′+(w(i,j)+hi−hj)=d′jd'_i + (w(i, j) + h_i - h_j) = d'jdi′​+(w(i,j)+hi​−hj​)=d′j （否则 (i,j)(i, j)(i,j) 边就不会在增广路上了）。稍作变形后可以得到 w(j,i)+(hj+dj′)−(hi+di′)=0w(j, i) + (h_j + d'_j) - (h_i + d'_i) = 0w(j,i)+(hj​+dj′​)−(hi​+di′​)=0 。因此新增的边的边权非负。 而对于原有的边，在增广前， di′+(w(i,j)+hi+hj)−dj′≥0d'_i + (w(i, j) + h_i + h_j) - d'_j \\ge 0di′​+(w(i,j)+hi​+hj​)−dj′​≥0 ，因此 w(i,j)+(di′+hi)−(dj′+hj)≥0w(i, j) + (d'_i + h_i) - (d'_j + h_j) \\ge 0w(i,j)+(di′​+hi​)−(dj′​+hj​)≥0 ，即用 hi+di′h_i + d'_ihi​+di′​ 作为新势能并不会使 (i,j)(i, j)(i,j) 的边权变为负。 综上，增广后所有边的边权均非负，使用 Dijkstra 算法可以正确求出图上的最短路。 EK费用流 简单来说就是用最短路去寻找一个费用最多（少）的增广路然后回溯统计答案。 ","link":"https://evrgardenviolet.github.io/post/fei-yong-liu/"},{"title":"数论分块","content":"数论分块 用处 数论分块可以快速计算一些含有除法向下取整的和式（即形如 ∑i=1nf(i)g(⌊ni⌋)\\sum_{i = 1}^n f(i)g(\\left\\lfloor\\dfrac ni \\right\\rfloor)∑i=1n​f(i)g(⌊in​⌋) 的和式）。当可以在 O(1)O(1)O(1) 内计算 f(r)−f(l)f(r) - f(l)f(r)−f(l) 或已经预处理出 fff 的前缀和时，数论分块就可以在 O(n)O(\\sqrt n)O(n​) 的时间内计算上述和式的值。它主要利用了富比尼定理(Fubini′stheorem)(Fubini's theorem)(Fubini′stheorem) ，将 ⌊ni⌋\\left\\lfloor\\dfrac ni\\right\\rfloor⌊in​⌋ 相同的数打包同时计算。 富比尼定理 又称“算两次”，以意大利数学家圭多·富比尼（Guido Fubini）命名。 富比尼定理的积分形式：只要二重积分 ∫∫∣f(x,y)∣dxdy\\int\\int|f(x, y)|dxdy∫∫∣f(x,y)∣dxdy 有界，则可以逐次计算二重积分，并且可以交换逐次积分的顺序。 积分号也是特殊的求和号，因此在一般求和中，富比尼定理往往呈现为更换计数顺序，即交换两个求和号。 组合数学中的富比尼定理表现为，用两种不同的方法计算同一个量，从而建立相等关系。 例如这里的双曲线下整点的图片： 图中共分为了 555 块，这 555 块整点的最大纵坐标都相同。如果统计整点的个数，可以从纵向计数改为横向计数，直接计算555 个矩形即可。 引理1 ∀a,b,c∈Z,⌊abc⌋=⌊⌊ab⌋c⌋\\forall a, b, c\\in\\mathbb{Z}, \\left\\lfloor\\frac{a}{bc}\\right\\rfloor = \\left\\lfloor \\frac{\\left\\lfloor\\frac{a}{b}\\right\\rfloor}{c}\\right\\rfloor ∀a,b,c∈Z,⌊bca​⌋=⌊c⌊ba​⌋​⌋ 证明略(我也不会)qwq 引理2 ∀n∈N+,∣{⌊nd⌋∣d∈N+,d≤n}∣≤⌊2n⌋\\forall n\\in\\mathbb{N}_{+}, \\left|\\left\\{\\lfloor\\frac{n}{d}\\rfloor\\mid d\\in\\mathbb{N}_{+}, d\\leq n \\right\\}\\right|\\leq\\lfloor 2\\sqrt{n}\\rfloor ∀n∈N+​,∣∣∣​{⌊dn​⌋∣d∈N+​,d≤n}∣∣∣​≤⌊2n​⌋ ∣V∣\\left|V\\right|∣V∣ 表示集合 VVV 的元素个数 证明略 数论分块结论 对于常数 nnn ， 是的式子 ⌊ni⌋=⌊nj⌋\\lfloor \\frac ni\\rfloor = \\lfloor \\frac nj\\rfloor⌊in​⌋=⌊jn​⌋ 成立的最大的满足 i≤j≤ni \\le j\\le ni≤j≤n 的 jjj 的值为 ⌊n⌊ni⌋⌋\\left\\lfloor \\frac{n}{\\lfloor \\frac ni\\rfloor}\\right\\rfloor⌊⌊in​⌋n​⌋ 。即值 ⌊ni⌋\\lfloor \\frac ni \\rfloor⌊in​⌋ 所在的块的左端点为 ⌊n⌊ni⌋⌋\\left\\lfloor \\frac{n}{\\lfloor \\frac ni\\rfloor}\\right\\rfloor⌊⌊in​⌋n​⌋ 。 数论分块的过程大概如下：考虑和式 ∑i=1nf(i)⌊ni⌋\\sum_{i = 1}^{n} f(i) \\lfloor \\frac ni\\rfloor∑i=1n​f(i)⌊in​⌋ 那么由于我们可以知道 ⌊ni⌋\\lfloor \\frac ni \\rfloor⌊in​⌋ 的值成一个块状（就是同样的值都聚集在连续的块中），那么就可以用数论分块加速计算，降低时间复杂度。 利用上述结论，我们先求出 f(i)f(i)f(i) 的 前缀和（记作 s(i)=∑j=1if(i)s(i) = \\sum_{j = 1}^{i}f(i)s(i)=∑j=1i​f(i) ），然后每次以 [l,r]=[l,⌊n⌊ni⌋⌋]\\left[l, r \\right] = \\left[ l, \\left\\lfloor \\frac{n}{\\lfloor \\frac ni\\rfloor}\\right\\rfloor\\right][l,r]=[l,⌊⌊in​⌋n​⌋] 为一块，分块求出贡献累加到结果中即可。 ","link":"https://evrgardenviolet.github.io/post/shu-lun-fen-kuai/"},{"title":"莫比乌斯函数与容斥原理","content":"容斥原理与 莫比乌斯 函数 容斥原理 ∣⋃i=1n∣=∑i=1n∣Si∣−∑1≤i<j≤nn∣Si⋂Sj∣+∑1≤i<j<k≤n∣Si⋂Sj⋂Sk∣+......+(−1)n+1∣S1⋂...⋂Sn∣ \\left | \\bigcup_{i = 1}^{n} \\right | = \\sum_ {i = 1}^{n} \\left |S_i \\right | -\\sum_{1 \\le i < j \\le n}^{n} \\left |S_i\\bigcap S_j \\right | +\\sum_{1 \\le i < j < k \\le n} \\left | S_i \\bigcap S_j \\bigcap S_k \\right | + ......+ (-1)^{n+1} \\left | S_1 \\bigcap ...\\bigcap S_n \\right| ∣∣∣∣∣​i=1⋃n​∣∣∣∣∣​=i=1∑n​∣Si​∣−1≤i<j≤n∑n​∣∣∣​Si​⋂Sj​∣∣∣​+1≤i<j<k≤n∑​∣∣∣​Si​⋂Sj​⋂Sk​∣∣∣​+......+(−1)n+1∣∣∣​S1​⋂...⋂Sn​∣∣∣​ 所以看着是不是非常的头痛，所以我们数形结合用文氏图来直观的表示一下： 这样就相对直观一点。 接下来我们再看一下 多重集的组合： 设 S={n1⋅a1,n2⋅a2,...,nk⋅ak}S = \\left \\{ n_1 \\cdot a_1,n_2 \\cdot a_2,...,n_k \\cdot a_k \\right \\}S={n1​⋅a1​,n2​⋅a2​,...,nk​⋅ak​} 是由 n1n_1n1​ 个 a1a_1a1​ ，n2n_2n2​ 个 a2a_2a2​ , ..., nkn_knk​ 个 aka_kak​ 组成的多重集。设 n=∑i=1knin = \\sum_{i = 1}^{k} n_in=∑i=1k​ni​ ,对于任意整数 r≤nr \\le nr≤n，从 SSS 中取出 rrr 个元素组成一个多重集（不考虑顺序），产生的多重集的数量为： Ck+r−1k−1−∑i=1kCk+r−ni−nj−3k−1−...+(−1)kCk+r−∑i=1kni−(k+1)k−1C_{k+r-1}^{k-1}-\\sum_{i=1}^{k}C_{k+r-n_i-n_j-3}^{k-1}-...+(-1)^k C_{k+r- \\sum_{i=1}^{k}n_i-(k+1)}^{k-1}Ck+r−1k−1​−∑i=1k​Ck+r−ni​−nj​−3k−1​−...+(−1)kCk+r−∑i=1k​ni​−(k+1)k−1​ Mo¨biusM \\ddot{o}biusMo¨bius 函数 设正整数 NNN 按照算数基本定理分解质因数为 N=p1c1p2c2...pmcmN=p_{1}^{c_1}p_{2}^{c_2}...p_{m}^{c_m}N=p1c1​​p2c2​​...pmcm​​， 定义函数 μ(N)={0∃i∈[1,m],ci>11m≡0(mod 2),∀i∈[1,m],ci=1−1m≡1(mod 2),∀i∈[1,m],ci=1\\mu(N)=\\left\\{\\begin{matrix} 0 & \\exists i\\in [1,m],c_i>1\\\\ 1 & m\\equiv 0(mod\\ 2),\\forall i \\in[1,m],c_i=1\\\\ -1 & m\\equiv 1 (mod\\ 2),\\forall i\\in [1,m],c_i=1 \\end{matrix}\\right.μ(N)=⎩⎨⎧​01−1​∃i∈[1,m],ci​>1m≡0(mod 2),∀i∈[1,m],ci​=1m≡1(mod 2),∀i∈[1,m],ci​=1​ 称 μ(N)\\mu(N)μ(N) 为 Mo¨biusM \\ddot{o}biusMo¨bius 函数。 性质 莫比乌斯函数不仅是积性函数，还有如下性质： ∑d∣nμ(d)={1n=10n≠1\\sum_{d \\mid n} \\mu(d) = \\begin{cases}1&n= 1\\\\ 0 & n\\neq 1\\\\ \\end{cases} d∣n∑​μ(d)={10​n=1n​=1​ 即 ∑d∣nμ(d)=ε(n),μ∗1=ε\\sum_{d \\mid n}\\mu(d) = \\varepsilon(n), \\mu * 1 = \\varepsilon∑d∣n​μ(d)=ε(n),μ∗1=ε 证明 设 n=∏i=1kpici,n′=∏i=1kpin = \\displaystyle\\prod_{i = 1}^k{p_i}^{c_i}, n' = \\prod_{i = 1} ^k p_in=i=1∏k​pi​ci​,n′=i=1∏k​pi​ 那么 ∑d∣nμ(d)=∑d∣n′=∑i=0kCki⋅(−1)i=(1+(−1))k\\displaystyle\\sum_{d \\mid n}\\mu(d) = \\sum_{d \\mid n'} = \\sum_{i = 0}^k C_k^i\\cdot(-1) ^ i = (1 + (-1))^kd∣n∑​μ(d)=d∣n′∑​=i=0∑k​Cki​⋅(−1)i=(1+(−1))k 根据二项式定理，易知该式子的值在 k=1k = 1k=1 即 n=1n = 1n=1 是值为 111 否则为 000 ， 这也同时证明了 ∑d∣nμ(d)=[n=1]=ε(n)\\displaystyle\\sum_{d \\mid n}\\mu(d) = \\left[ n = 1\\right] = \\varepsilon(n)d∣n∑​μ(d)=[n=1]=ε(n) 以及 μ∗1=ε\\mu * 1 = \\varepsilonμ∗1=ε 例题 Acwing215 Zap ","link":"https://evrgardenviolet.github.io/post/mo-bi-wu-si-han-shu-yu-rong-chi-yuan-li/"},{"title":"莫比乌斯反演","content":"莫比乌斯反演 莫比乌斯反演是数论中的重要内容。对于一些函数 f(n)f(n)f(n) , 如果很难直接求出它的值，而容易求出其倍数和或约数和 g(n)g(n)g(n) ，那么可以通过莫比乌斯反演简化运算，求得 f(n)f(n)f(n) 的值。 前置芝士 数论分块， DirichletDirichletDirichlet 卷积 莫比乌斯函数 关于莫比乌斯函数的补充结论 反演结论： [gcd⁡(i,j)=1]=∑d∣gcd⁡(i,j)μ(d)\\displaystyle\\left[ \\gcd(i, j) = 1\\right] = \\sum_{d \\mid \\gcd(i, j)} \\mu(d)[gcd(i,j)=1]=d∣gcd(i,j)∑​μ(d) 直接推导：如果看懂了上一个结论，这个结论稍加思考便可以推出：如果 gcd⁡(i,j)=1\\gcd(i, j) = 1gcd(i,j)=1 的话，那么代表着我们按上个结论中枚举的那个 nnn 是 111， 也就是式子的值是 111 反之，有一个与 [gcd⁡(i,j)=1]\\left[ \\gcd(i,j) = 1\\right][gcd(i,j)=1] 相同的值： 000 利用 ε\\varepsilonε 函数 ：根据上一结论， [gcd⁡(i,j)=1]=ε(gcd⁡(i,j))\\left[ \\gcd(i, j) = 1\\right] = \\varepsilon(\\gcd(i, j))[gcd(i,j)=1]=ε(gcd(i,j)) ，将 $ \\varepsilon $ 展开即可。 线性筛 拓展 φ∗1=id⁡\\varphi * 1 = \\operatorname{id} φ∗1=id 证明： 将 nnn 分解质因数： n=∏i=1kpici\\displaystyle n = \\prod_{i =1 }^k p_i^{c_i}n=i=1∏k​pici​​ 首先，因为 φ\\varphiφ 是积性函数，故只要证明当 n′=pcn' = p^cn′=pc 时 φ∗1=∑d∣n′φ(n′d)=id⁡\\displaystyle \\varphi * 1 = \\sum_{d \\mid n'}\\varphi(\\dfrac{n'}{d}) = \\operatorname{id}φ∗1=d∣n′∑​φ(dn′​)=id 成立即可。 因为 ppp 是质数， 于是 d=p0,p1,p2,⋯ ,pcd = p^0, p^1, p^2, \\cdots, p^cd=p0,p1,p2,⋯,pc 易知如下过程： φ∗1=∑d∣nφ(nd)=∑i=0cφ(pi)=1+p0⋅(p−1)+p1⋅(p−1)+⋯+pc−1⋅(p−1)=pc=id⁡\\begin{aligned} \\varphi \\ast 1 &= \\sum_{d\\mid n}\\varphi(\\frac{n}{d})\\\\ &= \\sum_{i = 0} ^ c\\varphi(p^i)\\\\&= 1 + p^0\\cdot(p - 1) + p ^ 1\\cdot(p - 1) + \\cdots + p ^ {c - 1}\\cdot(p - 1)\\\\&= p ^ c\\\\&= \\operatorname{id}\\\\ \\end{aligned} φ∗1​=d∣n∑​φ(dn​)=i=0∑c​φ(pi)=1+p0⋅(p−1)+p1⋅(p−1)+⋯+pc−1⋅(p−1)=pc=id​ 该式子两侧同时卷 μ\\muμ 可得 φ(n)=∑d∣nd⋅μ(nd)\\displaystyle \\varphi (n) = \\sum_{d\\mid n}d \\cdot \\mu(\\frac{n}{d})φ(n)=d∣n∑​d⋅μ(dn​) QED. 莫比乌斯变换 设 f(n),g(n)f(n), g(n)f(n),g(n) 为两个数论函数。 形式一：如果有 $ f(n) = \\sum_{d\\mid n}g(n)$， 那么有 g(n)=∑d∣nμ(d)f(nd)g(n) = \\sum_{d \\mid n}\\mu(d)f(\\frac{n}{d})g(n)=∑d∣n​μ(d)f(dn​) 。 这种形式下，数论函数 f(n)f(n)f(n) 称为数论函数 g(n)g(n)g(n) 的莫比乌斯变换，数论函数 g(n)g(n)g(n) 称为数论函数 f(n)f(n)f(n) 的莫比乌斯逆变换（反演）。 容易看出，数论函数 g(n)g(n)g(n) 的莫比乌斯变换，就是将数论函数 g(n)g(n)g(n) 与常数函数 111 进行狄利克雷卷积。 (PS.根据狄利克雷卷积与狄利克雷生成函数的对应关系，数论函数 g(n)g(n)g(n) 的莫比乌斯变换对应的狄利克雷生成函数，就是数论函数 g(n)g(n)g(n) 的狄利克雷生成函数与黎曼函数 ζ\\zetaζ 的乘积。 形式二：如果有 f(n)=∑n∣dg(d)f(n) = \\sum_{n \\mid d}g(d)f(n)=∑n∣d​g(d) ，那么有 g(n)=∑n∣dμ(dn)f(d)g(n) = \\sum_{n \\mid d}\\mu(\\dfrac{d}{n})f(d)g(n)=∑n∣d​μ(nd​)f(d) 。 证明： 法一：对原式做数论变换。 ∑d∣nμ(d)f(nd)=∑d∣nμ(d)∑k∣ndg(k)=∑k∣ng(k)∑d∣nkμ(d)=g(n)\\displaystyle \\sum_{d \\mid n}\\mu(d)f(\\frac{n}{d}) = \\sum_{d \\mid n}\\mu(d)\\sum_{k \\mid \\frac nd}g(k) =\\sum_{k \\mid n}g(k)\\sum_{d \\mid \\frac nk}\\mu(d) = g(n) d∣n∑​μ(d)f(dn​)=d∣n∑​μ(d)k∣dn​∑​g(k)=k∣n∑​g(k)d∣kn​∑​μ(d)=g(n) 用 ∑d∣nμ(d)f(nd)\\sum_{d \\mid n}\\mu(d)f(\\frac nd)∑d∣n​μ(d)f(dn​)， 再变换求和顺序。最后一步变换的依据： ∑d∣nμ(d)=[n=1]\\sum_{d \\mid n} \\mu(d) = \\left[ n = 1\\right]∑d∣n​μ(d)=[n=1] ，因此在 nk=1\\frac nk = 1kn​=1 时第二个和式的值才为 111 。此时 n=kn = kn=k ，故原式等价于 ∑k∣n[n=k]⋅g(k)=g(n)\\displaystyle \\sum_{k\\mid n}\\left[n = k\\right]\\cdot g(k) = g(n)k∣n∑​[n=k]⋅g(k)=g(n) 法二：运用卷积。 原问题为：已知 f=g∗1f = g * 1f=g∗1 ， 证明 g=f∗μg = f * \\mug=f∗μ 易知如下转化：f∗μ=g∗1∗μ ⟹ f∗μ=gf * \\mu = g * 1 * \\mu \\implies f\\ast\\mu = gf∗μ=g∗1∗μ⟹f∗μ=g （其中 1∗μ=ε1 * \\mu = \\varepsilon1∗μ=ε ） 对于第二种形式： 类似上面的方法一，我们考虑逆推这个式子。 ∑n∣dμ(dn)f(d)=∑k=1+∞μ(k)f(kn)=∑k=1+∞μ(k)∑kn∣dg(d)=∑n∣dg(d)∑k∣dnμ(k)=∑n∣dg(n)ϵ(dn)=g(n)\\begin{aligned} &\\sum_{n \\mid d}{\\mu(\\frac{d}{n})f(d)} \\\\=& \\sum_{k = 1}^{+\\infty}{\\mu(k)f(kn)} = \\sum_{k = 1} ^ {+\\infty}{\\mu(k)\\sum_{kn \\mid d}{g(d)}} \\\\ =& \\sum_{n \\mid d}{g(d)\\sum_{k \\mid \\frac{d}{n}}{\\mu(k)}} = \\sum_{n \\mid d}{g(n)\\epsilon(\\frac{d}{n})} \\\\= & g(n) \\end{aligned} ===​n∣d∑​μ(nd​)f(d)k=1∑+∞​μ(k)f(kn)=k=1∑+∞​μ(k)kn∣d∑​g(d)n∣d∑​g(d)k∣nd​∑​μ(k)=n∣d∑​g(n)ϵ(nd​)g(n)​ 我们把 ddd 表示为 knknkn 的形式，然后把 fff 的原定义代入式子。 发现枚举 kkk 再枚举 knknkn 的倍数可以转换为直接枚举 nnn 的倍数再求出 kkk ，发现后面那一块其实就是 ϵ\\epsilonϵ , 整个式子只有在 d=nd = nd=n 的时候才能取到值。 QED. 实战例题 Problem B ∑d=1min⁡(⌊nk⌋,⌊mk⌋)μ(d)⌊nkd⌋⌊mkd⌋\\sum_{d = 1}^{\\min\\left( \\lfloor \\frac nk \\rfloor ,\\lfloor \\frac mk \\rfloor\\right)} \\mu(d) \\lfloor\\frac n{kd}\\rfloor\\lfloor\\frac m{kd}\\rfloor d=1∑min(⌊kn​⌋,⌊km​⌋)​μ(d)⌊kdn​⌋⌊kdm​⌋ YY的GCD ∑T=1n⌊nT⌋∗⌊mT⌋∑k∣T,k∈primeμ(Tk)\\sum_{T = 1}^n \\lfloor\\frac nT\\rfloor*\\lfloor\\frac mT\\rfloor \\sum_{k \\mid T, k \\in prime}\\mu(\\dfrac{T}{k}) T=1∑n​⌊Tn​⌋∗⌊Tm​⌋k∣T,k∈prime∑​μ(kT​) 数字表格 ∏T=1n(∏d∣Tf(d)μ(Td))⌊nT⌋⋅⌊mT⌋\\prod_{T =1}^n(\\prod_{d \\mid T}f(d)^{\\mu(\\frac Td)})^{\\lfloor\\frac nT\\rfloor\\cdot\\lfloor\\frac mT\\rfloor} T=1∏n​(d∣T∏​f(d)μ(dT​))⌊Tn​⌋⋅⌊Tm​⌋ ","link":"https://evrgardenviolet.github.io/post/mo-bi-wu-si-fan-yan/"},{"title":"拉格朗日插值","content":"拉格朗日插值 用处 设 f(x)f(x)f(x) 是一个 nnn 次多项式，现在知道 x+1x + 1x+1 个点满足多项式 f(x)f(x)f(x) ，求这个这个多项式上的任意的另一个点。 方法 ​ 对于大多对于拉格朗日的讲解都过于的复杂，这里有一种较为简单的理解： ​ 对于已知的 x+1x + 1x+1 个的点，我们可以依次使得 xix_ixi​ 的 f(xi)=1f(x_i) = 1f(xi​)=1 其余的 f(xi)f(x_i)f(xi​) 都等于 111 。于是我们可以得到 x+1x + 1x+1 个方程，然后就可以求解了！ 公式 f(k)=∑i=1nyi∏j≠ik−xjxi−xjf(k) = \\sum^{n}_{i = 1} y_i \\prod_{j \\ne i} \\dfrac{k - x_j}{x_i - x_j} f(k)=i=1∑n​yi​j​=i∏​xi​−xj​k−xj​​ 证明： 由多项式除法可得： f(x)≡f(a)(mod (x−a))f(x) \\equiv f(a) (\\mod (x - a)) f(x)≡f(a)(mod(x−a)) 这样我们就可以列一个关于 f(x)f(x)f(x) 的多项式线性同余方程组： {f(x)≡y1(mod(x−x1))f(x)≡yn(mod(x−x2))⋯f(x)≡yn(mod(x−xn))\\begin{cases} f(x)\\equiv y_1 \\pmod{(x - x_1)}\\\\ f(x)\\equiv y_n\\pmod{(x - x_2)}\\\\\\cdots\\\\f(x)\\equiv y_n\\pmod{(x - x_n)} \\end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​f(x)≡y1​(mod(x−x1​))f(x)≡yn​(mod(x−x2​))⋯f(x)≡yn​(mod(x−xn​))​ 我们根据中国剩余定理，有： M=∏i=1n(x−x1),mi=Mx−xi=∏j≠i(x−xj)M = \\prod_{i = 1}^n{(x - x_1)}, m_i = \\dfrac M{x - x_i} = \\prod_{j\\ne i}{(x - x_j)} M=i=1∏n​(x−x1​),mi​=x−xi​M​=j​=i∏​(x−xj​) 则 mim_imi​ 模 (x−xi)(x - x_i)(x−xi​) 意义下的逆元就是： mi−1=∏j≠i1xi−xjm_i ^ {-1} = \\prod_{j \\ne i} \\dfrac 1{x_i - x_j} mi−1​=j​=i∏​xi​−xj​1​ 所以就有： f(x)≡∑i=1nyimimi−1≡∑i=1nyi∏j≠ix−xixi−xj(modM)f(x) \\equiv \\sum^n_{i = 1}y_i m_im_i ^{-1} \\equiv \\sum ^n_{i = 1}y_i \\prod_{j\\ne i}\\dfrac{x - x_i}{x_i - x_j}\\pmod M f(x)≡i=1∑n​yi​mi​mi−1​≡i=1∑n​yi​j​=i∏​xi​−xj​x−xi​​(modM) 所以在模意义下 f(x)f(x)f(x) 就是唯一的，即： f(k)=∑i=1nyi∏j≠ik−xjxi−xjf(k) = \\sum^{n}_{i = 1} y_i \\prod_{j \\ne i} \\dfrac{k - x_j}{x_i - x_j} f(k)=i=1∑n​yi​j​=i∏​xi​−xj​k−xj​​ QED. 时间复杂度 O(n2)O(n^2)O(n2) ","link":"https://evrgardenviolet.github.io/post/la-ge-lang-ri-cha-zhi/"},{"title":"杜教筛","content":"杜教筛 积性函数 在数论题目中，常常需要根据一些 积性函数 的性质，求出一些式子的值。 积性函数：对于所有互质的 aaa 和 bbb，总有 f(ab)=f(a)f(b)f(ab)=f(a)f(b)f(ab)=f(a)f(b)，则称 f(x)f(x)f(x) 为积性函数。 常见的积性函数有： d(x)=∑i∣n1d(x)=\\sum_{i \\mid n} 1d(x)=∑i∣n​1 σ(x)=∑i∣ni\\sigma(x)=\\sum_{i \\mid n} iσ(x)=∑i∣n​i φ(x)=∑i=1x1[gcd⁡(x,i)=1]\\varphi(x)=\\sum_{i=1}^x 1[\\gcd(x,i)=1]φ(x)=∑i=1x​1[gcd(x,i)=1] μ(x)={1 x=1(−1)k ∏i=1kqi=10 max⁡{qi}>1\\mu(x)=\\begin{cases}1&\\ x=1 \\\\(-1)^k& \\ \\prod_{i=1}^k q_i=1\\\\0 &\\ \\max\\{q_i\\}>1\\end{cases}μ(x)=⎩⎪⎨⎪⎧​1(−1)k0​ x=1 ∏i=1k​qi​=1 max{qi​}>1​ 积性函数有如下性质： 若 f(x)f(x)f(x)，g(x)g(x)g(x) 为积性函数，则 h(x)=f(xp)h(x)=f(x^p)h(x)=f(xp) h(x)=fp(x)h(x)=f^p(x)h(x)=fp(x) h(x)=f(x)g(x)h(x)=f(x)g(x)h(x)=f(x)g(x) h(x)=∑d∣xf(d)g(xd)h(x)=\\sum_{d \\mid x} f(d)g(\\frac x d)h(x)=∑d∣x​f(d)g(dx​) 中的 h(x)h(x)h(x) 也为积性函数。 在莫比乌斯反演的题目中，往往要求出一些数论函数的前缀和，利用 杜教筛 可以快速求出这些前缀和。 杜教筛 杜教筛被用来处理数论函数的前缀和问题。对于求解一个前缀和，杜教筛可以在低于线性时间的复杂度内求解 对于数论函数 fff，要求我们计算 S(n)=∑i=1nf(i)S(n)=\\sum_{i=1}^{n}f(i)S(n)=∑i=1n​f(i). 我们想办法构造一个 S(n)S(n)S(n) 关于 S(⌊ni⌋)S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right)S(⌊in​⌋) 的递推式 对于任意一个数论函数 ggg，必满足 ∑i=1n∑d∣ig(d)f(id)=∑i=1ng(i)S(⌊ni⌋) ⟺ ∑i=1n(f∗g)(i)=∑i=1ng(i)S(⌊ni⌋)\\sum_{i=1}^{n}\\sum_{d \\mid i}g(d)f\\left(\\frac{i}{d}\\right)=\\sum_{i=1}^{n}g(i)S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right)\\\\ \\iff \\sum_{i=1}^{n}(f\\ast g)(i)=\\sum_{i=1}^{n}g(i)S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right) i=1∑n​d∣i∑​g(d)f(di​)=i=1∑n​g(i)S(⌊in​⌋)⟺i=1∑n​(f∗g)(i)=i=1∑n​g(i)S(⌊in​⌋) 略证： g(d)f(id)g(d)f\\left(\\frac{i}{d}\\right)g(d)f(di​) 就是对所有 i≤ni\\leq ni≤n 的做贡献，因此变换枚举顺序，枚举 d,idd,\\frac{i}{d}d,di​（分别对应新的 i,ji,ji,j） \\begin{split} &\\sum_{i=1}^n\\sum_{d \\mid i}g(d)f\\left(\\frac{i}{d}\\right)\\\\ =&\\sum_{i=1}^n\\sum_{j=1}^{\\left\\lfloor\\frac{n}{i}\\right\\rfloor}g(i)f(j)\\\\ =&\\sum_{i=1}^ng(i)\\sum_{j=1}^{\\left\\lfloor\\frac{n}{i}\\right\\rfloor}f(j)\\\\ =&\\sum_{i=1}^ng(i)S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right) \\end{split} 那么可以得到递推式 g(1)S(n)=∑i=1n(f∗g)(i)−∑i=2ng(i)S(⌊ni⌋)g(1)S(n)=\\sum_{i=1}^n(f\\ast g)(i)-\\sum_{i=2}^ng(i)S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right) g(1)S(n)=i=1∑n​(f∗g)(i)−i=2∑n​g(i)S(⌊in​⌋) 那么假如我们可以快速对 ∑i=1n(f∗g)(i)\\sum_{i=1}^n(f \\ast g)(i)∑i=1n​(f∗g)(i) 求和，并用数论分块求解 ∑i=2ng(i)S(⌊ni⌋)\\sum_{i=2}^ng(i)S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right)∑i=2n​g(i)S(⌊in​⌋) 就可以在较短时间内求得 g(1)S(n)g(1)S(n)g(1)S(n). 问题一 "P4213【模板】杜教筛（Sum）" 题目大意：求 S1(n)=∑i=1nμ(i)S_1(n)= \\sum_{i=1}^{n} \\mu(i)S1​(n)=∑i=1n​μ(i) 和 S2(n)=∑i=1nφ(i)S_2(n)= \\sum_{i=1}^{n} \\varphi(i)S2​(n)=∑i=1n​φ(i) 的值，n≤231−1n\\le 2^{31} -1n≤231−1。 莫比乌斯函数前缀和 由 狄利克雷卷积，我们知道： ∵ϵ=μ∗1\\because \\epsilon =\\mu \\ast 1∵ϵ=μ∗1（ϵ(n)= [n=1]\\epsilon(n)=~[n=1]ϵ(n)= [n=1]） ∴ϵ(n)=∑d∣nμ(d)\\therefore \\epsilon (n)=\\sum_{d \\mid n} \\mu(d)∴ϵ(n)=∑d∣n​μ(d) S1(n)=∑i=1nϵ(i)−∑i=2nS1(⌊ni⌋)S_1(n)=\\sum_{i=1}^n \\epsilon (i)-\\sum_{i=2}^n S_1(\\lfloor \\frac n i \\rfloor)S1​(n)=∑i=1n​ϵ(i)−∑i=2n​S1​(⌊in​⌋) =1−∑i=2nS1(⌊ni⌋)= 1-\\sum_{i=2}^n S_1(\\lfloor \\frac n i \\rfloor)=1−∑i=2n​S1​(⌊in​⌋) 观察到 ⌊ni⌋\\lfloor \\frac n i \\rfloor⌊in​⌋ 最多只有 O(n)O(\\sqrt n)O(n​) 种取值，我们就可以应用 整除分块（或称数论分块）来计算每一项的值了。 直接计算的时间复杂度为 O(n34)O(n^{\\frac 3 4})O(n43​)。考虑先线性筛预处理出前 n23n^{\\frac 2 3}n32​ 项，剩余部分的时间复杂度为 O(∫0n13nx dx)=O(n23)O(\\int_{0}^{n^{\\frac 1 3}} \\sqrt{\\frac{n}{x}} ~ dx)=O(n^{\\frac 2 3})O(∫0n31​​xn​​ dx)=O(n32​) 对于较大的值，需要用 map 存下其对应的值，方便以后使用时直接使用之前计算的结果。 欧拉函数前缀和 当然也可以用杜教筛求出 φ(x)\\varphi (x)φ(x) 的前缀和，但是更好的方法是应用莫比乌斯反演： ∑i=1n∑j=1n1[gcd⁡(i,j)=1]=∑i=1n∑j=1n∑d∣i,d∣jμ(d)\\sum_{i=1}^n \\sum_{j=1}^n 1[\\gcd(i,j)=1]=\\sum_{i=1}^n \\sum_{j=1}^n \\sum_{d \\mid i,d \\mid j} \\mu(d)∑i=1n​∑j=1n​1[gcd(i,j)=1]=∑i=1n​∑j=1n​∑d∣i,d∣j​μ(d) =∑d=1nμ(d)⌊nd⌋2=\\sum_{d=1}^n \\mu(d) {\\lfloor \\frac n d \\rfloor}^2=∑d=1n​μ(d)⌊dn​⌋2 由于题目所求的是 ∑i=1n∑j=1i1[gcd⁡(i,j)=1]\\sum_{i=1}^n \\sum_{j=1}^i 1[\\gcd(i,j)=1]∑i=1n​∑j=1i​1[gcd(i,j)=1]，所以我们排除掉 i=1,j=1i=1,j=1i=1,j=1 的情况，并将结果除以 222 即可。 观察到，只需求出莫比乌斯函数的前缀和，就可以快速计算出欧拉函数的前缀和了。时间复杂度 O(n23)O(n^{\\frac 2 3})O(n32​)。 使用杜教筛求解 求 S(i)=∑i=1nφ(i)S(i)=\\sum_{i=1}^n\\varphi(i)S(i)=∑i=1n​φ(i). 同样的，φ∗1=ID\\varphi\\ast 1=IDφ∗1=ID \\begin{split} &\\sum_{i=1}^n(\\varphi\\ast 1)(i)=\\sum_{i=1}^n1\\cdot S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right)\\\\ &\\sum_{i=1}^nID(i)=\\sum_{i=1}^n1\\cdot S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right)\\\\ &\\frac{1}{2}n(n+1)=\\sum_{i=1}^nS\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right)\\\\ &S(n)=\\frac{1}{2}n(n+1)-\\sum_{i=2}^nS\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right)\\\\ \\end{split} 代码实现 问题二 「LuoguP3768」简单的数学题 大意：求 ∑i=1n∑j=1ni⋅j⋅gcd⁡(i,j)(modp)\\sum_{i=1}^n\\sum_{j=1}^ni\\cdot j\\cdot\\gcd(i,j)\\pmod p i=1∑n​j=1∑n​i⋅j⋅gcd(i,j)(modp) 其中 n≤1010,5×108≤p≤1.1×109n\\leq 10^{10},5\\times 10^8\\leq p\\leq 1.1\\times 10^9n≤1010,5×108≤p≤1.1×109，ppp 是质数。 利用 φ∗1=ID\\varphi\\ast1=IDφ∗1=ID 做莫比乌斯反演化为 ∑d=1nF2(⌊nd⌋)⋅d2φ(d)(F(n)=12n(n+1))\\sum_{d=1}^nF^2\\left(\\left\\lfloor\\frac{n}{d}\\right\\rfloor\\right)\\cdot d^2\\varphi(d) \\left(F(n)=\\frac{1}{2}n\\left(n+1\\right)\\right)\\\\ d=1∑n​F2(⌊dn​⌋)⋅d2φ(d)(F(n)=21​n(n+1)) 对 ∑d=1nF(⌊nd⌋)2\\sum_{d=1}^nF\\left(\\left\\lfloor\\frac{n}{d}\\right\\rfloor\\right)^2∑d=1n​F(⌊dn​⌋)2 做数论分块，d2φ(d)d^2\\varphi(d)d2φ(d) 的前缀和用杜教筛处理： \\begin{split} &f(n)=n^2\\varphi(n)=(ID^2\\varphi)(n)\\\\ &S(n)=\\sum_{i=1}^nf(i)=\\sum_{i=1}^n(ID^2\\varphi)(i) \\end{split} 需要构造积性函数 ggg，使得 f×gf\\times gf×g 和 ggg 能快速求和 单纯的 φ\\varphiφ 的前缀和可以用 φ∗1\\varphi\\ast1φ∗1 的杜教筛处理，但是这里的 fff 多了一个 ID2ID^2ID2，那么我们就卷一个 ID2ID^2ID2 上去，让它变成常数： S(n)=∑i=1n((ID2φ)∗ID2)(i)−∑i=2nID2(i)S(⌊ni⌋)S(n)=\\sum_{i=1}^n\\left((ID^2\\varphi)\\ast ID^2\\right)(i)-\\sum_{i=2}^nID^2(i)S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right) S(n)=i=1∑n​((ID2φ)∗ID2)(i)−i=2∑n​ID2(i)S(⌊in​⌋) 化一下卷积 \\begin{split} &(ID^2\\varphi)\\ast ID^2)(i)\\\\ =&\\sum_{d \\mid i}(ID^2\\varphi)(d)ID^2\\left(\\frac{i}{d}\\right)\\\\ =&\\sum_{d \\mid i}d^2\\varphi(d)\\left(\\frac{i}{d}\\right)^2\\\\ =&\\sum_{d \\mid i}i^2\\varphi(d)=i^2\\sum_{d \\mid i}\\varphi(d)\\\\ =&i^2(\\varphi\\ast1)(i)=i^3 \\end{split} 再化一下 S(n)S(n)S(n) \\begin{split} S(n)&=\\sum_{i=1}^n\\left((ID^2\\varphi)\\ast ID^2\\right)(i)-\\sum_{i=2}^nID^2(i)S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right)\\\\ &=\\sum_{i=1}^ni^3-\\sum_{i=2}^ni^2S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right)\\\\ &=\\left(\\frac{1}{2}n(n+1)\\right)^2-\\sum_{i=2}^ni^2S\\left(\\left\\lfloor\\frac{n}{i}\\right\\rfloor\\right)\\\\ \\end{split} 分块求解即可 代码实现 ","link":"https://evrgardenviolet.github.io/post/du-jiao-shai/"},{"title":"FFT","content":"FFT 前置知识 复数 概念 离散傅里叶变换（Discrete Fourier Transform，缩写为 DFT），是傅里叶变换在时域和频域上都呈离散的形式，将信号的时域采样变换为其 DTFT 的频域采样。 FFT 是一种高效实现 DFT 的算法，称为 快速傅立叶变换（Fast Fourier Transform，FFT）。它对傅里叶变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。快速数论变换 (NTT) 是快速傅里叶变换（FFT）在数论基础上的实现。 在 1965 年，Cooley 和 Tukey 发表了快速傅里叶变换算法。事实上 FFT 早在这之前就被发现过了，但是在当时现代计算机并未问世，人们没有意识到 FFT 的重要性。一些调查者认为 FFT 是由 Runge 和 König 在 1924 年发现的。但事实上高斯早在 1805 年就发明了这个算法，但一直没有发表。 多项式表示 系数表示法 系数表示法就是用一个多项式的各个项系数来表达这个多项式，即使用一个系数序列来表示多项式： f(x)=a0+a1x+a2x2+⋯+anxn ⟺ f(x)={a0,a1,⋯ ,an}f(x) = a_0 + a_1 x + a_2 x ^ 2 + \\cdots +a_n x ^ n \\iff f(x) = \\{a_0, a_1, \\cdots, a_n\\} f(x)=a0​+a1​x+a2​x2+⋯+an​xn⟺f(x)={a0​,a1​,⋯,an​} 点值表示法 点值表示法是把这个多项式看成一个函数，从上面选取 n+1n + 1n+1 个点，从而利用这 n+1n + 1n+1 个点来唯一地表示这个函数。 设： f(x0)=y0=a0+a1x0+a2x02+a3x03+⋯+anx0nf(x0)=y0=a0+a1x0+a2x02+a3x03+⋯+anx0nf(x1)=y1=a1+a1x1+a2x12+a3x13+⋯+anx1nf(x2)=y2=a2+a1x2+a2x22+a3x23+⋯+anx2n⋮f(xn)=yn=an+a1xn+a2xn2+a3xn3+⋯+anxnn\\begin{array}{c}f(x_0) = y_0 = a_0 + a_1 x_0 + a_2 x_0 ^ 2 + a_3 x_0 ^ 3 + \\cdots + a_n x_0 ^ n\\\\ f(x_0) = y_0 = a_0 + a_1 x_0 + a_2 x_0 ^ 2 + a_3 x_0 ^ 3 + \\cdots + a_n x_0 ^ n\\\\ f(x_1) = y_1 = a_1 + a_1 x_1 + a_2 x_1 ^ 2 + a_3 x_1 ^ 3 + \\cdots + a_n x_1 ^ n\\\\ f(x_2) = y_2 = a_2 + a_1 x_2 + a_2 x_2 ^ 2 + a_3 x_2 ^ 3 + \\cdots + a_n x_2 ^ n\\\\ \\vdots \\\\ f(x_n) = y_n = a_n + a_1 x_n + a_2 x_n ^ 2 + a_3 x_n ^ 3 + \\cdots + a_n x_n ^ n\\\\ \\end{array} f(x0​)=y0​=a0​+a1​x0​+a2​x02​+a3​x03​+⋯+an​x0n​f(x0​)=y0​=a0​+a1​x0​+a2​x02​+a3​x03​+⋯+an​x0n​f(x1​)=y1​=a1​+a1​x1​+a2​x12​+a3​x13​+⋯+an​x1n​f(x2​)=y2​=a2​+a1​x2​+a2​x22​+a3​x23​+⋯+an​x2n​⋮f(xn​)=yn​=an​+a1​xn​+a2​xn2​+a3​xn3​+⋯+an​xnn​​ 那么用点值表示法表示 f(x)f(x)f(x) 如下 f(x)=yn=a0+a1x+a2x2+⋯+anxn ⟺ f(x)={(x0,y0),(x1,y1),⋯ ,(xn,yn)}f(x) = y_n = a_0 + a_1x + a_2 x^2 + \\cdots + a_n x ^ n \\iff f(x) = \\{(x_0, y_0), (x_1, y_1), \\cdots , (x_n, y_n)\\} f(x)=yn​=a0​+a1​x+a2​x2+⋯+an​xn⟺f(x)={(x0​,y0​),(x1​,y1​),⋯,(xn​,yn​)} 通俗地说，多项式由系数表示法转为点值表示法的过程，就是 DFT 的过程。相对地，把一个多项式的点值表示法转化为系数表示法的过程，就是 IDFT。而 FFT 就是通过取某些特殊的 xxx 的点值来加速 DFT 和 IDFT 的过程。 单位复根 考虑这样一个问题： DFT 是把多项式从系数表示转到了点值表示，那么我们把点值相乘之后，再还原成系数表示，就解决了我们的问题。上述过程如下： 假设我们 DFT 过程对于两个多项式选取的 xxx 序列相同，那么可以得到 f(x)=(x0,f(x0)),(x1,f(x1)),(x2,f(x2)),⋯ ,(xn,f(xn))g(x)=(x0,g(x0)),(x1,g(x1)),(x2,g(x2)),⋯ ,(xn,g(xn))\\begin{array}{c}f(x) = (x_0, f(x_0)), (x_1, f(x_1)), (x_2, f(x_2)), \\cdots , (x_n, f(x_n))\\\\ g(x) = (x_0, g(x_0)), (x_1, g(x_1)), (x_2, g(x_2)), \\cdots , (x_n, g(x_n))\\\\ \\end{array} f(x)=(x0​,f(x0​)),(x1​,f(x1​)),(x2​,f(x2​)),⋯,(xn​,f(xn​))g(x)=(x0​,g(x0​)),(x1​,g(x1​)),(x2​,g(x2​)),⋯,(xn​,g(xn​))​ 如果我们设 F(x)=f(x)⋅g(x)F(x) = f(x) \\cdot g(x)F(x)=f(x)⋅g(x) ，那么容易得到 F(x)F(x)F(x) 的点值表达式： F(x)={(x0,f(x0)g(x0)),(x1,f(x1)g(x1)),(x2,f(x2)g(x2)),⋯ ,(xn,f(xn)g(xn))}F(x) = \\{(x_0, f(x_0)g(x_0)), (x_1, f(x_1)g(x_1)), (x_2, f(x_2)g(x_2)), \\cdots, (x_n, f(x_n)g(x_n))\\} F(x)={(x0​,f(x0​)g(x0​)),(x1​,f(x1​)g(x1​)),(x2​,f(x2​)g(x2​)),⋯,(xn​,f(xn​)g(xn​))} 但是我们要的是系数表达式，接下来问题变成了从点值回到系数。如果我们带入到高斯消元法的方程组中去，会把复杂度变得非常高。光是计算 xi(0≤i≤n)x^i(0 \\le i \\le n)xi(0≤i≤n) 就是 nnn 项， 这就已经 O(n2)O(n^2)O(n2) 了， 跟别说还要把 n+1n + 1n+1 个方程进行消元…… 因此我们不去计算 xix^ixi .111 和 −1-1−1 的幂都很好算，但是仅仅有两个也不够，我们至少需要 n+1n + 1n+1 个。利用我们刚学的长度为 111 的虚数，这些数不管怎么乘长度都是 111 。我们需要的是 ωk=1\\omega^k = 1ωk=1 中的 ω\\omegaω ，容易想到 −i-i−i 和 iii 是符合的。除此以外： 观察上图，容易发现这是一个单位圆（圆心为原点，半径为 111 ），单位圆上的向量模长均为 111 ，根据复数的运算法则，两个复数相乘，在复平面上表示为两个向量模长相乘，辐角相加。因此两个模长为 111 的向量相乘，得到的仍是模长为 111 的向量，辐角为两个向量辐角的和。因此我们可以将 ωk=1\\omega ^ k = 1ωk=1 中的 ω\\omegaω 理解为复平面上的一个单位向量，满足它的辐角的 kkk 倍恰好是 360∘360^ \\circ360∘ ——即把圆周 kkk 等分的角。我们把符合以上条件的复数（复平面上的向量）称为复根，用 ω\\omegaω 表示。 定义 严谨地，我们称 xn=1x^n = 1xn=1 在复数意义下的解是 nnn 次复根。显然，这样的解有 nnn 个，设 ωn=e2πin\\omega_n = e^\\frac{2\\pi i}{n}ωn​=en2πi​ ，则 xn=1x^ n = 1xn=1 的解集表示为 {ωnk∣k=0,0,1,⋯ ,n−1}\\{\\omega_n ^ k \\mid k = 0, 0, 1, \\cdots, n - 1\\}{ωnk​∣k=0,0,1,⋯,n−1} 。我们称 ω\\omegaω 是 nnn 次单位复根（the nnn -th root of unity）。根据复平面的知识，nnn 次单位复根是复平面把单位圆 nnn 等分的第一个角所对应的向量。其它复根均可以用单位复根的幂表示。 另一方面，根据欧拉公式，还可以得到 ωn=e2πin=cos⁡(2πn)+i⋅sin⁡(2πn)\\omega_n = e^\\frac{2 \\pi i}{n} = \\cos(\\dfrac{2\\pi}{n}) +i \\cdot \\sin (\\dfrac{2\\pi}{n})ωn​=en2πi​=cos(n2π​)+i⋅sin(n2π​) 。 举个例子，当 n=4n = 4n=4 时， ωn=i\\omega_n = iωn​=i ，即 iii 就是 444 次单位复根： 当 n=4n = 4n=4 的时候，相当于把单位圆等分 n=4n = 4n=4 份。将每一份按照极角编号，那么我们只要知道 ω41\\omega_4^1ω41​ 因为它的角度是相当于单位角度），就能知道 ω40,ω41,ω42,ω43\\omega_4^0, \\omega_4^1, \\omega_4^2, \\omega_4^3ω40​,ω41​,ω42​,ω43​ 。 ω40\\omega _4^0ω40​ 恒等于 111 ， ω42\\omega_4^2ω42​ 的角度是 ω41\\omega_4^1ω41​ 的两倍，所以 ω42=(ω41)2=i2=−1\\omega_4^2 = (\\omega_4^1)^2 = i^2=-1ω42​=(ω41​)2=i2=−1 ，依次以此类推。 性质 单位复根有三个重要的性质。对于任意正整数 nnn 和整数 kkk : ωnn=1ωnk=ω2n2kω2nk+n=−ω2nk\\begin{array}{c} \\omega_n^n = 1\\\\ \\omega_n^k =\\omega_{2n}^{2k}\\\\ \\omega_{2n}^{k + n} = -\\omega_{2n}^k\\\\ \\end{array} ωnn​=1ωnk​=ω2n2k​ω2nk+n​=−ω2nk​​ 快速傅里叶变换 FFT 算法的基本思想是分治。就 DFT 来说，它分治地来求当 x=ωnkx = \\omega_n^kx=ωnk​ 的时候 f(x)f(x)f(x) 的值。它的分治思想体现在将多项式分为奇次项和偶次项处理。 举个例子，对于一共 888 项的多项式 f(x)=a0+a1x+a2x2+a3x3+a4x4+a5x5+a6x6a7x7f(x) = a_0 + a _ 1 x + a _ 2 x ^ 2 + a _ 3 x ^ 3 + a _ 4 x ^ 4 + a _ 5 x ^ 5 + a _ 6 x ^ 6 a _ 7 x ^ 7 f(x)=a0​+a1​x+a2​x2+a3​x3+a4​x4+a5​x5+a6​x6a7​x7 按照次数的奇偶来分成两组，然后右边提出来一个 xxx cf(x)=(a0+a2x2+a4x4+a6x6)+(a1x+a3x3+a5x5+a7x7)=(a0+a2x2+a4x4+a6x6)+x(a1+a3x2+a5x4+a7x6)\\begin{aligned}{c}f(x) &= (a_0 + a_2 x ^ 2 + a_4 x ^ 4 + a_6 x ^ 6) + (a_1x + a_3 x ^ 3 + a_5 x ^ 5 + a_7 x ^ 7) \\\\ &= (a_0 + a_2 x ^ 2 + a_4 x ^ 4 + a_6 x ^ 6) + x(a_1 + a_3 x ^ 2 + a_5 x ^ 4 + a_7 x ^ 6)\\\\ \\end{aligned} cf(x)​=(a0​+a2​x2+a4​x4+a6​x6)+(a1​x+a3​x3+a5​x5+a7​x7)=(a0​+a2​x2+a4​x4+a6​x6)+x(a1​+a3​x2+a5​x4+a7​x6)​ 分别用奇偶次次项数建立新的函数 G(x)=a0+a2x+a4x2+a6x3H(x)=a1+a3x+a5x2+a7x3\\begin{array}{c}G(x) = a_0 + a_2x + a_4x^2 + a_6x^3\\\\ H(x) = a_1 + a_3x + a_5x ^ 2 + a_7x_3\\\\ \\end{array} G(x)=a0​+a2​x+a4​x2+a6​x3H(x)=a1​+a3​x+a5​x2+a7​x3​​ 那么原来的 f(x)f(x)f(x) 用新函数表示为 DET⁡(f(ωnk))=DET⁡(G((ωnk)2))+ωnk×DET⁡(H((ωnk)2))=DET⁡(G(ωn2k))+ωnk×DET⁡(H(ωn2k))=DET⁡(G(ωn/2k))+ωnk×DET⁡(H(ωn/2k))\\begin{aligned}\\operatorname{DET}(f(\\omega_n^k)) &=\\operatorname{DET}(G((\\omega_{n}^{k})^2)) + \\omega_{n}^{k} \\times \\operatorname{DET}(H((\\omega_n^k)^2))\\\\ &= \\operatorname{DET}(G(\\omega_{n}^{2k})) + \\omega_{n}^{k} \\times \\operatorname{DET}(H(\\omega_n^{2k}))\\\\ &=\\operatorname{DET}(G(\\omega_{n / 2}^{k})) + \\omega_{n}^{k} \\times \\operatorname{DET}(H(\\omega_{n / 2}^{k}))\\\\ \\end{aligned} DET(f(ωnk​))​=DET(G((ωnk​)2))+ωnk​×DET(H((ωnk​)2))=DET(G(ωn2k​))+ωnk​×DET(H(ωn2k​))=DET(G(ωn/2k​))+ωnk​×DET(H(ωn/2k​))​ 同理可得 DET⁡(f(ωnk+n/2))=DET⁡(G(ωn2k+n))+ωnk+n/2×DET⁡(H(ωn2k+n))=DET⁡(G(ωn2k))−ωnk×DET⁡(H(ωn2k))=DET⁡(G(ωn/2k))−ωnk×DET⁡(H(ωn/2k))\\begin{aligned}\\operatorname{DET}(f(\\omega_n^{k + n / 2})) &=\\operatorname{DET}(G(\\omega_{n}^{2k + n})) + \\omega_{n}^{k + n / 2} \\times \\operatorname{DET}(H(\\omega_n^{2k + n}))\\\\ &= \\operatorname{DET}(G(\\omega_{n}^{2k})) - \\omega_{n}^{k} \\times \\operatorname{DET}(H(\\omega_n^{2k}))\\\\ &=\\operatorname{DET}(G(\\omega_{n / 2}^{k})) - \\omega_{n}^{k} \\times \\operatorname{DET}(H(\\omega_{n / 2}^{k}))\\\\ \\end{aligned} DET(f(ωnk+n/2​))​=DET(G(ωn2k+n​))+ωnk+n/2​×DET(H(ωn2k+n​))=DET(G(ωn2k​))−ωnk​×DET(H(ωn2k​))=DET(G(ωn/2k​))−ωnk​×DET(H(ωn/2k​))​ 因此我们求出了 DFT⁡(G(ωn/2k))\\operatorname{DFT}(G(\\omega_{n / 2}^{k}))DFT(G(ωn/2k​)) 和 DFT⁡(H(ωn/2k))\\operatorname{DFT}(H(\\omega_{n / 2}^{k}))DFT(H(ωn/2k​)) 后，就可以同时求出 DFT⁡(f(ωnk))\\operatorname{DFT}(f(\\omega_{n}^{k}))DFT(f(ωnk​)) 和 DFT⁡(H(ωnk+n/2))\\operatorname{DFT}(H(\\omega_{n}^{k + n / 2}))DFT(H(ωnk+n/2​)) 。于是对 GGG 和 HHH 分别递归 DFT即可。 考虑到分治 DFT 能处理的多项式长度只能是 2m(m∈N∗)2^m(m \\in N ^ \\ast)2m(m∈N∗) ，否则在分治的时候左右不一样长，右边就取不到系数了。所以要在第一次 DFT 之前就把序列向上补成长度为 2m(m∈N∗)2^m(m \\in N ^ \\ast)2m(m∈N∗) （高次系数补 000 ）、最高项次数为 2m−12^m - 12m−1 的多项式。 在代入值的时候，因为要代入 nnn 个不同值，所以我们代入 ωn0,ωn1,ωn2,⋯ ,ωnn−1(n=2m(m∈N∗))\\omega_n^0, \\omega_n^1, \\omega_n^2, \\cdots, \\omega_n^{n - 1}(n = 2^m(m \\in N^\\ast))ωn0​,ωn1​,ωn2​,⋯,ωnn−1​(n=2m(m∈N∗)) 一共 2m2^m2m​ 个不同值。 代码实现方面，STL 提供了复数的模板，当然也可以手动实现。两者区别在于，使用 STL 的 complex 可以调用 exp 函数求出 ωn\\omega_nωn​ 。但事实上使用欧拉公式得到的虚数来求 ωn\\omega_nωn​ 也是等价的。 时间复杂度 O(nlog⁡n)O(n \\log n)O(nlogn) 。 位逆序置换 这个算法还可以从“分治”的角度继续优化。我们每一次都会把整个多项式的奇数次项和偶数次项系数分开，一直分到只剩下一个系数。但是，这个递归的过程需要更多的内存。因此，我们可以先“模仿递归”把这些系数在原数组中“拆分”，然后再“倍增”地去合并这些算出来的值。 以 888 项多项式为例，模拟拆分的过程： 初始序列为 {x0,x1,x2,x3,x4,x5,x6,x7}\\{x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7\\}{x0​,x1​,x2​,x3​,x4​,x5​,x6​,x7​} 一次二分之后 {x0,x2,x4,x6},{x1,x3,x5,x7}\\{x_0, x_2, x_4, x_6\\}, \\{x_1, x_3, x_5, x_7\\}{x0​,x2​,x4​,x6​},{x1​,x3​,x5​,x7​} 两次二分之后 {x0,x4},{x2,x6},{x1,x5},{x3,x7}\\{x_0, x_4\\}, \\{x_2, x_6\\}, \\{x_1, x_5\\}, \\{x_3, x_7\\}{x0​,x4​},{x2​,x6​},{x1​,x5​},{x3​,x7​} 三次二分之后 {x0}{x4}{x2}{x6}{x1}{x5}{x3}{x7}\\{x_0\\}\\{x_4\\}\\{x_2\\}\\{x_6\\}\\{x_1\\}\\{x_5\\}\\{x_3\\}\\{x_7\\}{x0​}{x4​}{x2​}{x6​}{x1​}{x5​}{x3​}{x7​} 规律：其实就是原来的那个序列，每个数用二进制表示，然后把二进制翻转对称一下，就是最终那个位置的下标。比如 x1x_1x1​ 是 001，翻转是 100，也就是 4，而且最后那个位置确实是 4。我们称这个变换为位逆序置换（bit-reversal permutation，国内也称蝴蝶变换）。 根据它的定义，我们可以在 O(mlog⁡n)O(m \\log n)O(mlogn) 的时间内求出每个数变换后的结果： 快速傅里叶逆变换 傅里叶逆变换可以用傅里叶变换表示。对此我们有两种理解方式。 线性代数角度 IDFT（傅里叶反变换）的作用，是把目标多项式的点值形式转换成系数形式。而 DFT 本身是个线性变换，可以理解为将目标多项式当作向量，左乘一个矩阵得到变换后的向量，以模拟把单位复根代入多项式的过程： [y0y1y2y3⋮yn−1]=[1111⋯11ωn1ωn2ωn3⋯ωnn−11ωn2ωn4ωn6⋯ωn2(n−1)1ωn3ωn6ωn9⋯ωn3(n−1)⋮⋮⋮⋮⋱⋮1ωnn−1ωn2(n−1)ωn3(n−1)⋯ωn(n−1)2][a0a1a2a3⋮an−1]\\begin{bmatrix}y_0 \\\\ y_1 \\\\ y_2 \\\\ y_3 \\\\ \\vdots \\\\ y_{n-1} \\end{bmatrix} = \\begin{bmatrix}1 & 1 & 1 & 1 & \\cdots & 1 \\\\ 1 & \\omega_n^1 & \\omega_n^2 & \\omega_n^3 & \\cdots & \\omega_n^{n-1} \\\\ 1 & \\omega_n^2 & \\omega_n^4 & \\omega_n^6 & \\cdots & \\omega_n^{2(n-1)} \\\\ 1 & \\omega_n^3 & \\omega_n^6 & \\omega_n^9 & \\cdots & \\omega_n^{3(n-1)} \\\\ \\vdots & \\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\ 1 & \\omega_n^{n-1} & \\omega_n^{2(n-1)} & \\omega_n^{3(n-1)} & \\cdots & \\omega_n^{(n-1)^2} \\end{bmatrix} \\begin{bmatrix} a_0 \\\\ a_1 \\\\ a_2 \\\\ a_3 \\\\ \\vdots \\\\ a_{n-1} \\end{bmatrix} ⎣⎢⎢⎢⎢⎢⎢⎢⎡​y0​y1​y2​y3​⋮yn−1​​⎦⎥⎥⎥⎥⎥⎥⎥⎤​=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡​1111⋮1​1ωn1​ωn2​ωn3​⋮ωnn−1​​1ωn2​ωn4​ωn6​⋮ωn2(n−1)​​1ωn3​ωn6​ωn9​⋮ωn3(n−1)​​⋯⋯⋯⋯⋱⋯​1ωnn−1​ωn2(n−1)​ωn3(n−1)​⋮ωn(n−1)2​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤​⎣⎢⎢⎢⎢⎢⎢⎢⎡​a0​a1​a2​a3​⋮an−1​​⎦⎥⎥⎥⎥⎥⎥⎥⎤​ 现在我们已经得到最左边的结果了，中间的 xxx 值在目标多项式的点值表示中也是一一对应的，所以，根据矩阵的基础知识，我们只要在式子两边左乘中间那个大矩阵的逆矩阵就行了。由于这个矩阵的元素非常特殊，它的逆矩阵也有特殊的性质，就是每一项取倒数，再除以 nnn ，就能得到它的逆矩阵。 为了使计算的结果为原来的倒数，根据单位复根的性质并结合欧拉公式，可以得到 1ωk=ωk−1=e−2πik=cos⁡(2πk)+i⋅sin⁡(−2πk) \\frac{1}{\\omega_k}=\\omega_k^{-1}=e^{-\\frac{2\\pi i}{k}}=\\cos\\left(\\frac{2\\pi}{k}\\right)+i\\cdot \\sin\\left(-\\frac{2\\pi}{k}\\right) ωk​1​=ωk−1​=e−k2πi​=cos(k2π​)+i⋅sin(−k2π​) 因此我们可以尝试着把单位根 ωk\\omega_kωk​ 取成 e−2πike^{-\\frac{2 \\pi i}{k}}e−k2πi​ 这样我们的计算结果就会变成原来的倒数，而其它的操作过程与 DFT 是完全相同的。我们可以定义一个函数，在里面加一个参数 111 或者是 −1-1−1 ，然后把它乘到 π\\piπ 上。传入 111 就是 DFT，传入 −1-1−1 就是 IDFT。 单位复根周期性 利用单位复根的周期性同样可以理解 IDFT 与 DFT 之间的关系。 考虑原本的多项式是 f(x)=a0+a1x+a2x2+⋯+an−1xn−1=∑i=0n−1aixif(x)=a_0+a_1x+a_2x^2+\\cdots+a_{n-1}x^{n-1}=\\sum_{i=0}^{n-1}a_ix^if(x)=a0​+a1​x+a2​x2+⋯+an−1​xn−1=∑i=0n−1​ai​xi​ 。而 IDFT 就是把你的点值表示还原为系数表示。 考虑 构造法。我们已知 yi=f(ωni),i∈{0,1,⋯ ,n−1}y_i=f\\left( \\omega_n^i \\right),i\\in\\{0,1,\\cdots,n-1\\}yi​=f(ωni​),i∈{0,1,⋯,n−1} ，求 {a0,a1,⋯ ,an−1}\\{a_0,a_1,\\cdots,a_{n-1}\\}{a0​,a1​,⋯,an−1​} 。构造多项式如下\\ A(x)=∑i=0n−1yixi A(x)=\\sum_{i=0}^{n-1}y_ix^i A(x)=i=0∑n−1​yi​xi 相当于把 {y0,y1,y2,⋯ ,yn−1}\\{y_0,y_1,y_2,\\cdots,y_{n-1}\\}{y0​,y1​,y2​,⋯,yn−1​} 当做多项式 AAA​ 的系数表示法。 这时我们有两种推导方式，这对应了两种实现方法。 方法一 设 bi=ωn−1b_i = \\omega_n^{-1}bi​=ωn−1​ ，则多项式 AAA 在 x=b0,b1,⋯ ,bn−1x=b_0,b_1,\\cdots,b_{n-1}x=b0​,b1​,⋯,bn−1​ 处的点值表示法为 {A(b0),A(b1),⋯ ,A(bn−1)}\\left\\{ A(b_0),A(b_1),\\cdots,A(b_{n-1}) \\right\\}{A(b0​),A(b1​),⋯,A(bn−1​)} 对 A(x)A(x)A(x) 的定义式做一下变换，可以将 A(bk)A(b_k)A(bk​) 表示为 A(bk)=∑i=0n−1f(ωni)ωn−ik=∑i=0n−1ωn−ik∑j=0n−1aj(ωni)j=∑i=0n−1∑j=0n−1ajωni(j−k)=∑j=0n−1aj∑i=0n−1(ωnj−k)i \\begin{aligned} A(b_k)&=\\sum_{i=0}^{n-1}f(\\omega_n^i)\\omega_n^{-ik}=\\sum_{i=0}^{n-1}\\omega_n^{-ik}\\sum_{j=0}^{n-1}a_j(\\omega_n^i)^{j}\\\\ &=\\sum_{i=0}^{n-1}\\sum_{j=0}^{n-1}a_j\\omega_n^{i(j-k)}=\\sum_{j=0}^{n-1}a_j\\sum_{i=0}^{n-1}\\left(\\omega_n^{j-k}\\right)^i\\\\ \\end{aligned} A(bk​)​=i=0∑n−1​f(ωni​)ωn−ik​=i=0∑n−1​ωn−ik​j=0∑n−1​aj​(ωni​)j=i=0∑n−1​j=0∑n−1​aj​ωni(j−k)​=j=0∑n−1​aj​i=0∑n−1​(ωnj−k​)i​ 记 S(ωna)=∑i=0n−1(ωna)iS\\left(\\omega_n^a\\right)=\\sum_{i=0}^{n-1}\\left(\\omega_n^a\\right)^iS(ωna​)=∑i=0n−1​(ωna​)i 当 a=0(mod n)a = 0 \\left(\\mod n\\right)a=0(modn) 时， S(ωna)=nS(\\omega_n^a) = nS(ωna​)=n 。 当 a≠0(mod n)a \\neq 0 (\\mod n)a​=0(modn) 时， 我们错位相减 S(ωna)=∑i=0n−1(ωna)iωnaS(ωna)=∑i=1n(ωna)iS(ωna)=(ωna)n−(ωna)0ωna−1=0 \\begin{aligned} S\\left(\\omega_n^a\\right)&=\\sum_{i=0}^{n-1}\\left(\\omega_n^a\\right)^i\\\\ \\omega_n^a S\\left(\\omega_n^a\\right)&=\\sum_{i=1}^{n}\\left(\\omega_n^a\\right)^i\\\\ S\\left(\\omega_n^a\\right)&=\\frac{\\left(\\omega_n^a\\right)^n-\\left(\\omega_n^a\\right)^0}{\\omega_n^a-1}=0\\\\ \\end{aligned} S(ωna​)ωna​S(ωna​)S(ωna​)​=i=0∑n−1​(ωna​)i=i=1∑n​(ωna​)i=ωna​−1(ωna​)n−(ωna​)0​=0​ 也就是说 S(ωna)={n,a=00,a≠0 S\\left(\\omega_n^a\\right)= \\left\\{\\begin{aligned} n,a=0\\\\ 0,a\\neq 0 \\end{aligned}\\right. S(ωna​)={n,a=00,a​=0​ 也就是说给定点 bi=ωn−1b_i = \\omega_n^{-1}bi​=ωn−1​ ， 则 AAA 的点值表示法为 {(b0,A(b0)),(b1,A(b1)),⋯ ,(bn−1,A(bn−1))}={(b0,a0⋅n),(b1,a1⋅n),⋯ ,(bn−1,an−1⋅n)} \\begin{aligned} &\\left\\{ (b_0,A(b_0)),(b_1,A(b_1)),\\cdots,(b_{n-1},A(b_{n-1})) \\right\\}\\\\ =&\\left\\{ (b_0,a_0\\cdot n),(b_1,a_1\\cdot n),\\cdots,(b_{n-1},a_{n-1}\\cdot n) \\right\\} \\end{aligned} =​{(b0​,A(b0​)),(b1​,A(b1​)),⋯,(bn−1​,A(bn−1​))}{(b0​,a0​⋅n),(b1​,a1​⋅n),⋯,(bn−1​,an−1​⋅n)}​ 综上所述，我们取单位根为其倒数，对 {y0,y1,y2,⋯ ,yn−1}\\{y_0,y_1,y_2,\\cdots,y_{n-1}\\}{y0​,y1​,y2​,⋯,yn−1​} 跑一遍 FFT，然后除以 nnn 即可得到 f(x)f(x)f(x) 的系数表示。 方法二 我们直接将 ωni\\omega _n^iωni​ 代入 A(x)A(x)A(x) 。 推导的过程与方法一大同小异，最终我们得到 A(ωnk)=∑j=0n−1ajS(ωnj+k)A(\\omega_n^k) = \\sum_{j=0}^{n-1}a_jS\\left(\\omega_n^{j+k}\\right)A(ωnk​)=∑j=0n−1​aj​S(ωnj+k​) 。 当且仅当 j+k=0(modn)j+k=0 \\pmod{n}j+k=0(modn) 时有 S(ωnj+k)=nS\\left(\\omega_n^{j+k}\\right) = nS(ωnj+k​)=n ，否则为 000 。因此 A(ωnk)=an−k⋅nA(\\omega_n^k) = a_{n-k}\\cdot nA(ωnk​)=an−k​⋅n 。 这意味着我们将 {y0,y1,y2,⋯ ,yn−1}\\{y_0,y_1,y_2,\\cdots,y_{n-1}\\}{y0​,y1​,y2​,⋯,yn−1​} 做 DFT 变换后，反转再除以 nnn ，同样可以还原 f(x)f(x)f(x) 的系数表示。 代码实现 所以我们 FFT 函数可以集 DFT 和 IDFT 于一身。代码实现如下： 快速数论变换 若要计算的多项式系数是别的具有特殊意义的整数，那么 FFT 全部用浮点数运算，从时间上比整数运算慢，且只能用 long double 类型。 要应用数论变化从而避开浮点运算精度问题，参见 快速数论变换。 ","link":"https://evrgardenviolet.github.io/post/fft/"},{"title":"Dirichlet 卷积","content":"Dirichlet 卷积 定义 对于两个数论函数 f(x)f(x)f(x) 和 g(x)g(x)g(x) ， 则它们的狄利克雷卷积得到的结果 h(x)h(x)h(x) 定义为： h(x)=∑d∣xf(d)g(xd)=∑ab=xf(a)g(b)h(x) = \\sum_{d|x}f(d)g(\\frac xd) = \\sum_{ab = x} f(a)g(b) h(x)=d∣x∑​f(d)g(dx​)=ab=x∑​f(a)g(b) 上式简记为 h=f∗gh = f * g h=f∗g 狄利克雷卷积是数论函数的重要运算，数论函数的许多性质都是通过这个运算挖掘出来的。 狄利克雷卷积与狄利克雷生成函数（DGF）密切相关。对于两个序列 f,gf, gf,g ， 其狄利克雷生成函数之积，对应的是两者的狄利克雷卷积序列的狄利克雷生成函数： F~(x)G~(x)=∑i∑jfigi(ij)x=∑i1ix∑d∣ifdgid\\tilde{F}(x)\\tilde{G}(x) = \\sum_{i} \\sum_{j}\\frac{f_i g_i}{(ij)^x} = \\sum_{i} \\frac{1}{i^x}\\sum_{d|i}f_d g_\\frac id F~(x)G~(x)=i∑​j∑​(ij)xfi​gi​​=i∑​ix1​d∣i∑​fd​gdi​​ 性质 交换律： f∗g=g∗ff * g = g * ff∗g=g∗f 。 结合律： (f∗g)∗h=f∗(g∗h)(f * g) * h = f * (g * h)(f∗g)∗h=f∗(g∗h) 。 分配率： (f+g)∗h=f∗h+g∗h(f + g) * h = f * h + g * h(f+g)∗h=f∗h+g∗h。 等式的性质： f=gf = gf=g 的充要条件是 f∗g=g∗ff * g = g * ff∗g=g∗f ， 其中数论函数 h(x)h(x)h(x) 要满足 h(x)≠0h(x) \\ne 0h(x)​=0 。 单位元： 单位函数 ε\\varepsilonε 是 Dirichlet 卷积运算中的单位元，即对于任何数论函数 fff ， 都有 f∗ε=ff * \\varepsilon = ff∗ε=f 。 逆元： 对于任何一个满足 f(x)≠0f(x) \\ne 0f(x)​=0 的数论函数，如果有另一个数论函数 g(x)g(x)g(x) 满足 f∗g=εf * g = \\varepsilonf∗g=ε ， 则称 g(x)g(x)g(x) 是 f(x)f(x)f(x) 的逆元。由 等式的性质 可知，逆元是唯一的。（PS.狄利克雷卷积运算中的逆元，在狄利克雷生成函数中相当于倒数运算。） 容易构造出 g(x)g(x)g(x) 的表达式为： g(x)=ε(x)−∑d∣x,d≠1f(d)g(xd)f(1)g(x) = \\dfrac{\\varepsilon(x) - \\sum_{d\\mid x, d\\ne 1}{f(d)g\\left(\\dfrac{x}{d}\\right)}}{f(1)} g(x)=f(1)ε(x)−∑d∣x,d​=1​f(d)g(dx​)​ 重要结论 两个积性函数的 Dirichlet 卷积也是积性函数 证明： 设两个积性函数为 f(x)f(x)f(x) 和 g(x)g(x)g(x) ， 再记 h=f∗gh = f * gh=f∗g 。 设 gcd⁡(a,b)=1\\gcd(a, b) = 1gcd(a,b)=1 ，则： h(a)=∑d1∣af(d1)g(ad1),h(b)=∑d2∣bf(d2)g(bd2),h(a) = \\sum_{d_1\\mid a} f(d_1)g(\\dfrac{a}{d_1}), h(b) = \\sum_{d_2 \\mid b}f(d_2)g(\\frac{b}{d_2}), h(a)=d1​∣a∑​f(d1​)g(d1​a​),h(b)=d2​∣b∑​f(d2​)g(d2​b​), 所以： h(a)h(b)=∑d1∣af(d1)g(ad1)∑d2∣bf(d2)g(bd2)=∑d∣abf(d)g(abd)=h(ab)\\begin {aligned}h(a)h(b)&= \\sum_{d_1\\mid a}{f\\left(d_1\\right)g\\left( \\frac{a}{d_1}\\right)}\\sum_{d_2\\mid b}{f(d_2)g\\left(\\dfrac b{d_2}\\right)}\\\\ &= \\sum_{d\\mid ab}{f(d)g\\left(\\dfrac{ab}d \\right)}\\\\&= h(ab) \\end{aligned} h(a)h(b)​=d1​∣a∑​f(d1​)g(d1​a​)d2​∣b∑​f(d2​)g(d2​b​)=d∣ab∑​f(d)g(dab​)=h(ab)​ 综合以上两点，结论成立。 证毕 积性函数的逆元也是积性函数 证明略（滑稽） ","link":"https://evrgardenviolet.github.io/post/dirichlet-juan-ji/"}]}