数论函数定义域在正整数上的函数称为数论函数。 积性函数若对于任意的互质的一对数$x$和$y$，有$f(x\times y)=f(x)\times f(y)$，则称函数$f$为积性函数。 卷积$(f* g)(n)$称为函数$f$与$g$的卷积。 (f* g)(n)=\sum\limits_{\tau = -\infty}^{\infty}f(\tau)g(n-\tau)狄利克雷卷积若$f$和$g$都 ...

欧拉函数定义所有满足小于$m$且与$m$互质的数的个数，称为欧拉函数，记为$\varphi(m)$。 计算公式将$m$分解质因数，得$m=p_1^{a_1}p_2^{a_2}…p_n^{a_n}$ 则$\varphi(m)=m\prod\limits_{i=1}^{n}(1-\dfrac{1}{p_i})$ 证明对于任意一个$p_i$，它的所有倍数在$[1,m]$内是均匀分布的。 因此$\dfra ...

同余即余数相同。同余问题是$OI$中比较常见的问题。 基本概念整除假设有两个整数$a$和$b$，且满足$ka = b (k \in Z)$，则称$b$整除$a$，记为$a | b$。 取模模数也就是余数。整数$a$除以整数$b$的余数记为$a \bmod b$。 另一种形式的定义是:若$a=kb+r(a\ge b, a,k,b,r\in Z)$，则$a \bmod b=r$。 根据定义，我们可以得 ...

基本概念矩阵即由$n$行$m$列的数字(也可以嵌套矩阵)构成的一个方阵。如:$\begin{bmatrix}1&2\\3&4\end{bmatrix}$，$\begin{bmatrix}a\\b\end{bmatrix}$等都是矩阵。 有一种特殊的矩阵叫做单位矩阵，它相当于数字乘法中的$1$。单位矩阵的行列数相同，且每一个满足$i=j$的数字$a_{ij}$的值都为1，其他的数字都 ...

$dp$时，如果需要用负数作为数组下标，可以考虑数组平移。我的方法是声明常量P，把可能有负数的下标位置上的变量加上P，使得该变量在任何可能情况下都为非负整数。 例如：洛谷P1282-多米诺骨牌。$dp$时这样写:for (int i = 2; i <= n; i++) for (int j = -5000; j <= 5000; j++) dp[i][j + P] ...

基本思想对于二叉搜索树的每个节点，其左子树的所有节点的值都比它小，右子树的所有节点的值都比它大(当然也可以反过来)。我们可以根据这个性质进行很多操作。比如要插入一个数，则只要用当前节点的值与插入的数字比较，然后根据比较结果往下走即可。 然而如果出题人毒瘤，二叉搜索树可能会被卡成一条链，这样时间效率就会大大降低。因此就诞生了可以随时保持平衡的二叉搜索树——平衡树。 平衡树主要有权值树和区间树两种用途 ...

从今天开始，把自己平常刷题时出现的各种sb错误记录下来，以免再犯。 2019.5.2-洛谷P3398-仓鼠找sugar众所周知，倍增求lca时需要用到一个存储父亲及祖先编号的数组。把$dp[100100][21]$写成了$dp[100100][20]$导致数组访问越界，喜提WA0分。 2019.5-洛谷P3369-【模板】普通平衡树写kth时把赋值语句搞错了顺序，导致WA。 错误代码:x = ...

原来用的服务器是github上的，由于在国外访问速度比较慢，今天换成了国内的腾讯云开发者平台服务器，速度有所加快。

这是一道很适合拿来练习树形dp的题目。 题意解读首先我们读一下题。题意并不难懂，但有一点需要注意：一个职员不能参加舞会，当且仅当他的直接上司参加了舞会，与更高级的上司去不去舞会无关。 为什么这道题可以用dp求解？下面简单分析一下： 一个职员组成的子树能够贡献的最大快乐指数可以由其下属组成的子树的最大快乐指数转移来，因此满足最优子结构； 一个职员组成的子树能够贡献的最大快乐指数只与其下属组成的 ...

原来说要写线段树的，但是普通线段树还是比较容易理解的，个人感觉比树状数组要好理解，再加上我只会普通线段树，所以暂时就不对线段树详细讲解了。不过下面还是简单介绍一下完事。 基本思想概述简单来说，线段树就是一棵完全二叉树，其中每个节点维护了一段区间的信息。每个非叶子节点维护的区间长度一定大于1，否则它就是叶子节点。线段树的深度为$log(n)$。在修改和查询时，需要从根结点开始向下遍历，最多需要访 ...