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值比较即可。

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

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+\lfloor \frac pk \rfloor=i+\lfloor \frac {n\%i}{\lfloor \frac ni \rfloor} \rfloor=\lfloor i+ \frac {n\%i}{\lfloor \frac ni \rfloor} \rfloor=\lfloor \frac {i \cdot \lfloor \frac ni \rfloor}{\lfloor \frac ni \rfloor}+ \frac {n\%i}{\lfloor \frac ni \rfloor} \rfloor \rfloor
$$

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

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

例题：Bzoj 1968

1
2
3
4
5
6

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

模板及讲解

定义

定义 $\varphi(n)$为$[1,n]$与$n$互质的数的个数。

(1) 给出n的唯一分解式 $n = p^{a1}_1p^{a2}_2p^{a3}_3…p^{ak}_k$ , 求出 $1，2，3…，n$ 中与n互素的数的个数

公式(容斥原理)： $$\varphi(n) = \sum_{S\subseteq(p_1,p_2,…p_k)}(-1)^\left|s\right|\frac {n}{\prod_{p_i\subseteq S}p_i}$$
可变形为：$$\varphi(n) = n(1-\frac1{p_1})(1-\frac1{p_2})…(1-\frac1{p_k})$$
即可在$O(k)$的时间复杂度算出$\varphi(n)$

(2) 不给出唯一分解式求$\varphi(n)$：(Poj 2407)

根据变形的公式，可以枚举所有小于$\sqrt n$的因子，然后之后把他”除干净”(为了提取唯一分解式之中的$p_i$)即可

1
2
3
4
5
6
7
8
9
10

int phi(int n) {  
	int ans = n;//ans为最后的答案
	int m = (int)sqrt(n + 0.5);
	for (int i = 2; i <= m; i++) if (n % i == 0) {
		ans = ans / i * (i - 1);//ans初值为n，因为1-(1/p) = (p-1)/p，由变形后公式可得
		while (n % i == 0) n /= i;//除干净
	}
	if (n > 1) ans = ans / n * (n - 1);
	return ans;
}

性质

1、当$n$为质数时，$\varphi (n)=n-1$
2、$\varphi (n)$是积性函数
3、当$n=p^k$，则$\varphi(n)=p^k-p^{k-1}=(p-1)p^{k-1}$
4、
$$n=\sum_{d|n} \varphi(d)$$
5、
$$\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]=\sum_{i=1}^n\sum_{k\mid i,k\mid n}\mu(k)=\sum_{k\mid n}\mu(k)\lfloor\frac nk\rfloor$$
6、$p$为质数，$p,i$不互质，$\varphi(p \cdot i)=\varphi(i) \cdot p$ (线性筛)
7、小于$n$与$n$互质的数和为$\frac{n \cdot \varphi(n)}{2}$

线性筛欧拉函数

复杂度$O(n)$

1
2
3
4
5
6
7
8
9
10
11

phi[1] = 1, vis[1] = 1;
for (int i = 2; i <= n; ++i) {
    if (!vis[i]) pri[++tot] = i, phi[i] = i - 1;
    for (int j = 1; j <= tot && (LL)i * (LL)pri[j] <= (LL)n; ++j) {
    	vis[i * pri[j]] = 1;
    	if (i % pri[j] == 0) {
    		phi[i * pri[j]] = phi[i] * pri[j];
    		break;
    	} else phi[i * pri[j]] = phi[i] * phi[pri[j]];
	}
}

运用

$gcd, lcm$相关求和问题

本问题必须$n=m$才行，不相等就必须用莫比乌斯反演。

例题1：Uva 11426
题意：求
$$\sum_{i=1}^n \sum_{j=i+1}^n gcd(i,j)$$

解：

$$\sum_{i=1}^n \sum_{j=i+1}^n gcd(i,j)=\sum_{i=1}^n \sum_{j=1}^{i-1} gcd(i,j)​$$

$$\sum_{d=1} d\sum_{i=1}^n \sum_{j=1}^{i-1} [gcd(i,j)=d]=\sum_{d=1} d\sum_{i=1}^n \sum_{j=1}^{i-1}[gcd(i,j)=1]=\sum_{d=1} d\sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{j=1}^{i-1}[gcd(i,j)=1]=\sum_{d=1} d\sum_{i=1}^{\lfloor \frac nd \rfloor} \varphi(i)$$

设$sum\varphi(k)=\sum_{i=1}^{k} \varphi(i), sumx(k)=\sum_{i=1}^k i$

则答案为

$$\sum_{d=1}^n d \cdot sum\varphi(\lfloor \frac nd \rfloor)$$

线性筛欧拉函数，然后整除分块即可。

1
2
3
4
5
6
7
8
9

while (scanf("%lld", &n) == 1 && n) {
    LL l = 1, r, ans = 0ll;
    while (l <= n) {
         r = n / (n / l);
         ans += sumphi[n / l] * (sumx[r] - sumx[l - 1]);
         l = r + 1; 
    }
    printf("%lld\n", ans);
}

例题1扩展1：Luogu 2398

题意：求
$$\sum_{i=1}^n \sum_{j=1}^n gcd(i,j)$$

解：答案为前面的答案乘二加上$sumx(n)$。
因为相当于对称一个答案，然后加上$gcd(i,i)$的答案。

例题1扩展2：Bzoj 2818

题意：求(其中$p_i​$为素数)
$$\sum_{i=1}^n \sum_{j=1}^n [gcd(i,j)=p_i]$$

先求$j \in [1, i-1]$再对称求解。

$$\sum_{p_k} \sum_{i=1}^n \sum_{j=1}^{i-1} [gcd(i,j)=p_k]=\sum_{p_k} \sum_{i=1}^{\lfloor \frac {n}{p_k} \rfloor} \sum_{j=1}^{i-1} [gcd(i,j)=1]=\sum_{p_k} \sum_{i=1}^{\lfloor \frac {n}{p_k} \rfloor} \varphi(\lfloor \frac {n}{p_k} \rfloor)=\sum_{p_k}sum\varphi(\lfloor \frac {n}{p_k} \rfloor)$$

枚举质数然后直接求即可。

1
2
3

LL ans = 0;
for (LL i = 1; i <= tot; ++i) ans += sumphi[n / pri[i]];
printf("%lld\n", ans * 2 + tot);

总结

• 一般满足一点，$n=m$，否则要用莫比乌斯反演去求解；
• 化简这种式子一般要求$j \in [1,i-1]$，方便提公因数后$\varphi$的转化。若要求全部的，加上对称的答案，然后再加上$gcd(i,i)$这样的答案。
• 类似莫比乌斯反演，最后的式子可以用整除分块去优化；将判断式修改为$[gcd(i,j)=1]​$方便$\varphi​$的出现 (莫比乌斯反演左边不一定是$gcd​$)

常见题型