BZOJ 2301
题意：给定$a, b, c, d, k$, 求
$$
\sum_{i=a}^{b} \sum_{j=c}^{d} [\gcd(i,j)=k]
$$

(下面默认$n \leq m$, 不满足则交换)
解：
我们可以将答案分成几个部分求解，然后$ans=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)$
依题意设出$f(k)$为$gcd(i,j)=k$的个数$(1 \leq i \leq n, 1 \leq j \leq n)$
但是这个并不好求，看见两个求和符号，我们可以想到用莫比乌斯反演来求解。
显然用变形后的两个式子，我们就可以设$g(k)$为$k|gcd(i,j)$的个数$(1 \leq i \leq n, 1 \leq j \leq n)$
$g(k)$非常好算，$g(k)=\lfloor \frac n{k} \rfloor \lfloor \frac m{k} \rfloor$
而显然$g(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} f(ki)$
那么可以莫比乌斯反演
$$
f(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} \mu(d) \lfloor \frac n{kd} \rfloor \lfloor \frac m{kd} \rfloor
$$
换元$\lfloor \frac nk \rfloor$，整除分块即可。

注意有$n,m$的整除分块是取两者最小值，复杂度也是有保证的。

poj 2288
题意：求一个无向图中的一条哈密顿路，这条路价值最大。
价值计数方法为：所有点权+两连续点权积+三连续点构成三角形积 (算法竞赛进阶指南例题)

这种方程的转移能力还是差。。
设$dp(S,i,j)$为状态为$S$，最后访问的两个点依次为$i,j$的最大值
那么转移就是$dp(S,i,j)=dp(S-k,j,k)+val_i+val_i \cdot val_j$，如果$i,k$连通则加上$val_i \cdot val_j \cdot val_k$
这个转移相当于当前路径是$k->j->i$，从$(k,j)$转移到$(j,i)$

初始化$dp(S, i, j) = val_i + val_j + val_i \cdot val_j$，两点连通对答案的贡献
然后之后的 DP 都从这些转移过来，记得判无效状态！

Bzoj 2165

本题是个倍增DP，在图上做。这个图给的明显是个分层图，我们逆向运用，分层图转成一个图。
然后就可以设$dp(p,i,j)$为坐了$p$次电梯$i$到$j$能到达的最高楼层。则
$dp(p,i,j)=max(dp(p/2, i, k)+dp(p / 2, k, j))$
那么这是一个倍增DP形式，我们也可以设$2^p$的状态。
我们发现邻接矩阵自乘就是这个方程的转移，所以矩阵快速幂上就行
如果第一行有一个$\geq m$，那么不用再DP下去
然后求答案就贪心像倍增LCA那样补，同时也要一直判断第一行是否有一个$\geq m$，有就说明当前不能乘
第一行有一个$\geq m$说明当前已经到达题目要求
注意修改矩阵乘法的地方所有值都应该小于$m$

倍增DP的思想，其实ST表、LCA的pre数组求法都是这种思路。

BZOJ 1875
题意：求无权无向图中$A$走$k$步到$B$的路径条数。过程中不能走过刚刚走过的边。

没有后面的条件就是模板题了
我们可以先设$dp(i,j)$为走了$i$步到$j$点，而这个没有记录上一条边，就不行了
刚开始想在状态记录前驱点，但是似乎不方便进行转移。。
那么从边的角度来考虑，设$dp(i,j)$为走了$i$步到第$j$条边终点结束，将无向边变成两条有向边。
那么转移$dp(i,j)=\sum dp(i-1,k), k,j$通过某点连接
但是这个DP还是会TLE
这个DP仔细想想可以满足矩阵乘法的要求，那么矩阵快速幂即可。

其实这里可以将边变成一些点。具体是如果一条边可以通过某个节点到另一条边，这两条边在新图中的点连一条边，这条边不能是一条无向边分化的有向边。
那么这里就构造了一个新的图矩阵，这个新图满足了上述条件，在原图中走$k$步相当于在新图中走$k-1$步，那么矩阵快速幂即可。
这个新图矩阵和前面的优化一样，所以是本质一样的算法，一个从 优化 DP 角度，一个从 Floyd 角度

BZOJ 1706
Luogu P2886
无向连通图，求$S$到$E$经过$k$条边的最短路

矩阵经典问题，看这里

图中DP：设$dp(i,x)$为走了$i$步在$x$点位置，则转移$dp(i,x)=\sum dp(i-1, y)+w(y, x)$，其中$(x,y) \in E$
同上面不好算。
我们定义$dp(k,i,j)$为$i$到$j$经过$k$个点(走$k$步)的最短路。则
$$dp(k,i,j)=min(dp(k-1,i,k)+dp(k-1,k,j))$$
压掉第一维，则$dp(i,j)=min(dp(i,k)+dp(k,j))$
我们发现和上面式子很像，那么我们可以试图修改一下矩阵乘法定义如下

$$C[i,j]=min(A[i,k]+B[k,i])$$

易推导结合律。可以用矩阵快速幂加速。

其实这也体现出 Floyd 的倍增思想。相当于对一个图做几次 Floyd 就是走了几步。矩阵快速幂就是倍增的过程。
这题在图上DP思想实际上就是分层图思想，每一步对应一张新图。与 NOIP2017Day1T3 有点像

BZOJ 1588
题意：求$\sum_{i=1}^n min_{1 \leq j \leq i}(|a_i-a_j|)$

BZOJ 1208
题意：找比某数差别最小的数。

第一个我一开始想写桶然后每次循环 $i$ 桶上下找最近有值，但是绝对被卡。
然后发现这个中间的空间都浪费了，其实绝对值差最小(两数差别最小)就是找前驱后继，用 set 维护即可。

这题也是平衡树题，由于查询的东西有限，写 set

记得 1208 要模

链表离线做法：
将原数组排序，然后弄成一个链表。记录原数组每个位置的数在现在链表的哪个位置。从后往前扫一遍，类似前面的能找到前驱后继，然后处理完删除本点。

模板及讲解

最小表示法是什么

最小表示法就是说我们有一个字符串$S$，然后将其首尾相连之后找到一个$|S|$长的子串使得字典序最小。
这个最小表示法可以用来看两个字符串是否同构，也就是两个字符串是否可以通过环变换互相转换。

解法

对于环的问题，我们可以断环成链，也就是将序列复制一遍放在后面，然后在$[1,n]$范围内为起点$|S|$长的子串都是环上的某种序列。

如果要判断是否同构，可以将一个字符串 Hash，然后再将断环以后的字符串 Hash，在$[1,n]$范围内找起点为$|S|$长的子串，求出Hash值比较即可。

同构也可以用最小表示法来解。也就是说两个不同字符串，如果他们同构，那么他们一定最小表示法一样。

本文是本网站的总结

微积分定理

中值定理

中值定理：函数$y=f(x)$满足：

• $f(x)$在$[a,b]$上连续
• $f(x)$在$(a,b)$上可导
  那么在$(a,b)$上，至少存在一个点$c$，使得
  $$
  \begin{equation}
  f’(c)=\frac{f(b)-f(a)}{b-a}
  \end{equation}
  $$
  或
  $$
  \begin{equation}
  f(b)-f(a)=f’(c)(b-a)
  \end{equation}
  $$

与此相关的是函数的增减性和导数的关系。

极值定理

极值定理：若$y=f(x)$在$[a,b]$上有定义且连续，则在$[a,b]$上存在点$c,d$，使得$f(c)\geq f(x)\geq f(d), x \in [a, b]$

与此相关的是函数的极值和导数的关系。

介值定理

介值定理：如果在$[a,b]$上$y=f(x)$有定义且连续，那么函数值都在$f(a)$和$f(b)$之间；也就是说，如果$K$是$f(a)$和$f(b)$之间的任何一个数，那么在$(a,b)$内至少存在一点$c$，使得$f(c)=K$。

与此相关的是函数根存在定理，即勘根定理

隐函数

定义

如果方程$F(x,y)=0$能确定$y$是$x$的函数，那么称这种方式表示的函数是隐函数。

求导

将$y$看成$x$的函数，对整个式子求导即可。
例
$$
x^2+y^2+2x=0
$$
两边求导，得
$$
2x+2yy’+2=0
$$
即
$$
y’=\frac{-x-1}{y}
$$

求导应用

1、对二次曲线方程求导
2、对显函数两边求$\log$降幂后求导

高阶导数

$$
y^{(n)}=(-1)^nn!x^{-(n+1)}
$$

牛顿迭代求根

$$
x_2=x_1-\frac{f(x_1)}{f’(x_1)}
$$
如此进行下去直到无定义为止。

微分

切线逼近

$$
\begin{equation}
f(x+dx)\cong f(x)+dy
\end{equation}
$$
其中$dy=f’(x)dx$，即
$$
\begin{equation}
f(x+dx)\cong f(x)+f’(x)dx
\end{equation}
$$

积分

不定积分

$$
\int f(x)dx=F(x)
$$

幂函数积分：
$$
\begin{equation}
\int x^ndx=\frac{x^{n+1}}{n+1},\quad n\neq -1
\end{equation}
$$

复合函数
$$
\begin{equation}
\int [f(x)^n]f’(x)dx=\frac{[f(x)]^{n+1}}{n+1},\quad n\neq -1
\end{equation}
$$

运算法则

$$
\begin{equation}
\int cf(x)dx=c\int f(x)dx
\end{equation}
$$

$$
\begin{equation}
\int [f(x)+g(x)]dx=\int f(x)dx+\int g(x)dx
\end{equation}
$$

Codeforces 1076E
题意：$m$次修改，$(v,k,x)$代表将$v$节点之下$k$层的节点全都加$x$，最后统一查询。即输出每个节点的值。

这题没有修改，并且询问只有最后一个，所以考虑离线。
我们发现这题就是子树+层次的题目，那么自然想到 DFS 序 或者 DFS 处理。
层次可以存每层DFS序，但是这样做没什么思路，我们不妨纵向看 (BFS 序相同的为序列的一个元素)
然后对于子树的问题，DFS子树型，即当前 DFS 只处理当前子树。那么这一种修改操作就是修改当前情况下层次序列$[dep,dep+d]$的值，那么我们修改后继续处理子树。然后如果这个子树全部处理完了，那么我们就回退。这些修改回退操作可以写一个区间修改单点查值的数据结构。显然差分 BIT 好写。但是我这里还是脑残写了个线段树。

模板及讲解

整数分块

求 $\sum_{i=1}^n \lfloor \frac ni \rfloor$。

显然可以暴力$O(n)$求。但是这里可以$O(\sqrt n)$ 求。

结论：对于所有的 $\lfloor \frac ni \rfloor$ 都是一段连续的块，并且块的端点可以被枚举。假设当前在 $i$ 处，那么 $\lfloor \frac ni \rfloor$的最后一个值在$\lfloor \frac{n}{\lfloor \frac ni \rfloor} \rfloor$

证明：设$\lfloor \frac ni \rfloor = \lfloor \frac n{i’} \rfloor=k$，并且$i’$为最大的位置。
设$i+d=i’$，$n=ik+p,n=(i+d)k+p’$
可得$p’=p-dk$，则$d_{max}= \lfloor \frac pk \rfloor$
那么$i’=i+d_{max}$
$$
=i+ \left \lfloor \frac pk \right \rfloor=i+\left\lfloor \frac {n\%i}{\left\lfloor \frac ni \right\rfloor} \right\rfloor=\left\lfloor i+ \frac {n\%i}{\left\lfloor \frac ni \right\rfloor} \right\rfloor=\left\lfloor \frac {i \cdot \left\lfloor \frac ni \right\rfloor}{\left\lfloor \frac ni \right\rfloor}+ \left\lfloor \frac {n\%i}{\left\lfloor \frac ni \right\rfloor} \right \rfloor \right\rfloor
$$

$$
= \left\lfloor \frac {i \cdot \left\lfloor \frac ni \right\rfloor+n-\left\lfloor \frac ni \right\rfloor \cdot i}{\left\lfloor \frac ni \right\rfloor} \right\rfloor= \left\lfloor \frac {n}{\left\lfloor \frac ni \right\rfloor} \right\rfloor
$$

得证。
易得$\lfloor \frac ni \rfloor$取值不超过$2\sqrt n$ 个，所以复杂度为$O(\sqrt n)$。

例题：Bzoj 1968

LL l = 1, r, ans = 0ll;
while (l <= n) {
    r = (n / (n / l));
    ans += (r - l + 1ll) * (n / l);
    l = r + 1ll;
}