【算法介绍】CDQ分治的基本概念
文章总览：盐与犬豪德，失踪多年的我终于回来写文章了（什么？你说我干什么了？你怎么知道我出遐蝶了！），，，言归正传，这篇文章的内容是 CDQ 分治，最近做到了一道关于 CDQ 分治的题目，一看就发现不会，所以这篇文章来讲一下 CDQ 分治的一些基本原理与应用，所谓 CDQ 分治，更广泛的来说是一种思想，它在被提出之前就已经广泛流传于各大巨佬之间，后来被高中的 IOI2008 金牌得主陈丹琦总结，因此而得名。
话说这剧情怎么这么熟悉，上次讲莫队的时候好像和这个剧本完全一样
下为本文大纲：
二维数点问题的规律总结
CDQ分治思想的简单推导
CDQ分治模板题讲解
CDQ分治的简单应用
前情回顾：狮子之尾
友情链接：
【算法介绍】二维数点 | 祝馀宫【算法介绍】扫描线思想 | 祝馀宫
上面这两篇是我曾经结下的关于二维数点的一些文章。我们可以简单的总结一下，从最最开始的一维数点，是如何一步一步拓展到二维数点的呢？
首先来从一维数点讲起，这应该是数点问题的起源。什么是数点？举个例子，现在我有一个一维的数轴，我往上面标点，标了点以后，查询某一区间，或者某一前缀等等等等有多少个点。这就是一维数点问 ...
【九段第三课】LCM求和
题面：LCM求和大秦 为你打开 题目传送门
备用题面你的任务是求得以下代码的值
1234567unsigned long long allPairLcm( int n ) { unsigned long long res = 0; for( int i = 1; i <= n; i++ ) for( int j = i + 1; j <= n; j++ ) res += lcm(i, j); // lcm means least common multiple return res;}
注意：直接实现代码可能会超时
思路设 $S(n)=\sum_{i=1}^n\operatorname{lcm}(i,n)$ 答案就可以表示为 $ans[n]=ans[n-1]+(S(n)-n)$，这个是显然的，因为相较于原来的定义我们多算了 $\operatorname{lcm}(n,n)=n$ 的值，一会减去就可以了。
然后问题变成如何快速计算 $S(n)$，同样的从定义出发：
\begin{aligned}
\sum_{i ...
【算法介绍】概率与期望及其计算
文章总览：群星岸落之夜如你所见，这篇文章的主题是概率与期望。众所周知，概率与期望早就占领了各大领域，比如说投篮的命中率可以表达一个选手的投篮水准，竞赛题目设置很多测试点来测试代码本质是一种抽样调查，等等等等。但是说概率与期望，在初中或者高中课本中都是占比非常大的部分（刚刚好我也打算顺手学了），所以这篇文章的前半部分注重于一些课本上的基础知识介绍与讲解，后面会浅浅的说一些信竞方面的概率期望。
下为本文大纲：
概率基本知识介绍及计算
全概率公式与贝叶斯公式
期望、方差与线性相关性
二项、超几何及正态分布
期望线性性以及简单运用
随机游走的问题概率模型
概念基础：穿过锁孔之风
样本空间与概率定义
古典概型与概率加乘
独立事件与条件概率
全概率与贝叶斯公式
概率定义：这是魔法哟关于概率的定义，你可能会说：“这玩意不是烂大街了嘛吗？还有人不会的？”正确的，概率的定义其实大家都知道是那个意思，可是实际上从稍微严谨的角度出发的概念以及一些性质可能并不广为人知，我们要学概率，就要从最基础概念开始：概率的基础——事件。
对于一个事件，可以是世间万物，比如说下面几个都可以是事件：
在一个既有青蛙又 ...
【算法介绍】斯特林数与卡特兰数
文章总览：落井当下石这篇文章讲的内容是斯特林数和卡特兰数，两个非常常用的计数类型数列，初赛常考（好吧我怎么感觉斯特林数我从来没有见到过）
本文内容限定如下：
第一类斯特林数推导及实现
第二类斯特林数推导及实现
斯特林数例题
卡特兰数推导及应用
卡特兰数例题
算法其一：得胜必追击
第一类斯特林数推导及实现
第二类斯特林数推导及实现
第一类斯特林数第一类斯特林数就是：将 $n$ 个不同物体排成 $k$ 个互不区分的非空圆排列的方案数。
可以简单的分来讨论，对于第一类斯特林数 $S1(n,k)$：
对于第 $n$ 个数新开了一个圆排列，方案数为 $S1(n-1,k-1)$。
对于第 $n$ 个数插入了以前某一个圆排列，方案数为 $(n-1)\times S1(n-1,k)$，因为在插入这个数以前，一共有 $n-1$ 个数，由于是圆排列，环上的空位数量还是 $n-1$ 个，所以乘起来。
边界条件也是非常的明显是 dp[0][0]=1 。
123456dp[0][0] = 1;for(int i = 1; i <= n; i++) { for(int j = 1; ...
【奇技淫巧】欧拉函数与欧拉定理
文章总览：坠临万界的星芒欧拉函数和欧拉定理也是非常基础的数论知识。欧拉函数做为积性函数，并且自身携带欧拉名称加持各种优良性质，被广泛的运用到各个数学推导方面；而欧拉定理更是必不可少，计算逆元是它最基本的运用，它也是凌驾于费马小定理的存在（费马小定理可以从欧拉定理中得出）；并且其拓展即拓展欧拉函数还可以在取模运算中缩小大指数范围，等等等等。接下来我们介绍无所不能的——欧拉函数与欧拉定理。
欧拉函数推导
欧拉函数性质
欧拉函数的计算
欧拉函数拓展
欧拉定理推导
拓展欧拉定理推导
概念基础：因缘假合的人身
欧拉函数推导
欧拉函数性质
欧拉函数基础推导关于欧拉函数，就从最基础的开始讲起。我们定义函数 $\varphi(n)$ 表示从 $1$ 到 $n$ 的数字中与 $n$ 互质的有多少个。这就是欧拉函数所表示的信息。那么关于欧拉函数我们能有什么已知的值吗？
非常显然的，对于一个质数 $p$，其欧拉函数值 $\varphi(p)=p-1$ 这是显然的，因为 $p$ 作为质数显然与 $1\sim p$ 之间的除了它本身以外任何数字互质。其次有一个容易让人纰漏的点，那就是 $\varphi(1 ...
【算法介绍】排列组合问题汇总
文章总览：远行雪杖的清晨排列组合，这是初赛题目和复赛数学题目中必不可少的一部分，同时也是大多数计数类 DP 的重难点所在。其特点就是各种题目百出不厌，千变万化，让人措不及防，但是实际上中国有句古话叫做“万变不离其宗”，排列组合的问题也是有一定套路可言的。本篇文章旨在总结大多数类型的排列组合基础模型以及使用方式，排列组合问题计算时几个常见的思考方向，等等等。下为文本大纲：
组合数基础
二项式定理
隔板法基础
组合数例题
排列数基础
错位排列
圆排列
多重集合排列
康托展开
排列组合综合应用
组合基础：便携炉具的正午
组合数基础
二项式定理
隔板法基础
组合数基础推导组合数大家绝对不陌生，组合数指的就是 $n$ 个数里面选出 $m$ 个，不考虑取出的顺序，有几种取法，这个取法的方法数量就是大家常见的 $C_n^m$。
举个最常见的例子，我有 $6$ 个数字，我要从中选出 $3$ 个，那么他表示成刚刚的符号就是 $C_6^3$，但是问题是如何计算呢？非常显然的，如果我们考虑取数的顺序，那么计算出来的就是排列数，我们划去排列即可。
具体的，第一个数字有 $6$ 种取法，第二个数字就少了一 ...
【算法介绍】中国剩余定理及其拓展
文章总览：穷高极天，亢盈难久中国有句古话：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”上过小学一年级的我们都知道，这是非常经典的同余方程组，而它的解法，就是这篇文章要讲的中国剩余定理 $\tt Chinese\ Remainder\ Theorem$。
本文内容限定于下：
中国剩余定理证明
中国剩余定理实现
拓展中国剩余定理证明
拓展中国剩余定理实现
推导其一：威制八毒，灭却炎烟
同余方程的计算&通解形式
通解形式正确性证明
从实例出发的推导那么从开篇提到的“物不知数”问题出发，我们可以得到下面的同余方程组：
\begin{cases}
x\equiv 2\pmod 3\\
x\equiv 3\pmod 5\\
x\equiv 2\pmod 7
\end{cases}其实这个题目很早就有了答案，“三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知。”这是来自于明朝数学家程大位在《算法统宗》中的解答口诀。其含义即是关于这个问题的通解形式，其中第一个字的表示模数，最后一个词中的数字表示每一个同余方程余数要乘以的系数，最后加起来模 $10 ...
517九段第三课 A ：整数分块 again
题面：整数分块again大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
给出 $N$ 并计算下面表达式的值：
\sum_{i=1}^N i^4\left\lfloor\frac{N}{i}\right\rfloor答案对于 $M$ 取模。
思路拿到题面，注意到整数分块的经典部分，不难写出如下代码：123456789inline void Work() { ll ans = 0; for(ll l = 1, r = 1; r <= n; l = r + 1) { r = n / (n / l); (ans += ((f(r) - f(l - 1) + P) % P) * (n / l) % P) %= P; if(r == n) break; } printf("%lld\n", ans);}
那么这题主要的考点，其实就是计算一段区间内的四次方和。借助强大的搜索引擎我们可以轻松知道四次方和前缀和公式是：
\cfrac{n(n+1)(2n+1) ...
517九段第一课 E ：求和
题面：不互质的数大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
对于给定的 $N$，定义 $S(k)$ 为 $(x_1,x_2,…,x_k)$ 的数量。$(x_1,x_2,…,x_k)$ 满足以下条件：
$(x_1,x_2,…,x_k)$ 为正整数
$x_1+x_2+…+x_k=N$
现在需要你找到 $(S(1)+S(2)+…+S(N)) \bmod 10^9+7$
思路不难注意到对于 $N$ 而言 $S(k)=C_{N-1}^{k-1}$，我们要求的式子就可以化为 $\sum_{i=0}^{N-1}C_{N-1}^i=2^{N-1}$。但是 $N$ 特别大，大到需要高精度怎么办？快速幂显然不行，注意到 $2^{P-1}=1\pmod P$ 所以不断地从 $N$ 中提取出 $P-1$ 即可。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include<bits/stdc++.h>using namespa ...
517九段第一课 D ：不互质的数
题面：不互质的数大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
求 $1\sim N-1$ 中与 $N$ 不互质的数的和并对 $1e9+7$ 取模。
思路注意到 $k$ 与 $N$ 互质时，$N-k$ 也与 $N$ 互质，满足对称性，则利用类似等差数列求和的思路，可得 $n\times \varphi(n)/2$ 就是与 $N$ 互质的数的和，从总量减去即可。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include<bits/stdc++.h>using namespace std;typedef long long ll;// typedef __int128 int128;typedef pair<int , int > pii;typedef unsigned long long ull;namespace FastIO { ...