流离之人追逐幻影。
BZOJ3529
大力推公式就可以了
先不考虑$a$的限制，那么
$$\begin{align}
Ans & =\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma_0(gcd(i,j)) \\
& =\sum_{d}\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d} \rfloor}\sigma_0(d)\epsilon(gcd(i,j)) \\
& =\sum_{d}\sigma_0(d)\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{d}\rfloor}\sum_{d’|gcd(i,j)}\mu(d’) \\
& =\sum_{d}\sum_{d’}\sigma_0(d)\mu(d’)\lfloor\frac{n}{dd’}\rfloor\lfloor\frac{m}{dd’}\rfloor \\
& =\sum_{T}\sum_{d|T}\sigma_0(d)\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor
\end{align}$$
设${\rm F}(n)=\sum_{d|n}\sigma_0(d)\mu(\frac{n}{d})$
那么只要处理出${\rm F}(n)$的前缀和就可以$O(\sqrt n)$计算答案了
显然可以用倍增筛法$O(n\lg n)$做
再来考虑$a$的限制，发现题目并没有强制在线，那么可以离线所有询问，按照$a$的大小排序，每次询问拿出$\sigma_0(n)\leq$当前$a$的$n$，去更新它的倍数的${\rm F}$
用树状数组维护${\rm F}$前缀和
BZOJ3530
很显然的AC自动机上的Dp
先建出AC自动机，然后做两次Dp
第一次：设$g[i][j]$表示串长为i，该串在AC自动机上匹配到节点$j$，并且串首数字不是0的方案数
第二次：设$f[i][j][1/0]$表示串长为$i$，该串在AC自动机上匹配到节点$j$，是/否已经比N小，并且串首数字不是0的方案数
yy一下转移
BZOJ3531
模板题
按照Dfs序树链剖分，那么一条重链在Dfs序中是连续的一段区间，这样一种颜色只要开一棵线段树就行了
BZOJ3532
第一问拆点最小割
第二问，贪心考虑最小的$c$能否取到，也就是问这个点对应的边是否在最小割当中。
那么看一下从$u$到$u’$有没有增广路，就知道有没有被割掉了
如果最小的$c$能取到，那么从$u’$向$u$退流，否则不退流。然后继续取第二小的。
因为$c$两两不同，所以贪心一定是对的
BZOJ3533
可以发现，一次询问的区间中，答案点一定在这些点组成的凸包上，更确切一些，当询问为$(x,y)$，当$y\leq 0$时答案在下凸包上，否则答案在上凸包上。
而且感觉好像应该大概发现答案具有三分性。
开始的想法是分块，每$\sqrt n$个点维护一个凸包，询问时在凸包上三分
但是似乎会很慢，不知道会不会被卡掉，就没敢写
可以建立线段树，将每次询问分割成$\log_{2}n$个树上节点，然后可以类似记忆化搜索的方式处理：如果询问的一个节点上没有信息，那就暴力建立凸包再三分；否则在已经建立好的凸包上三分。
分析一下复杂度：线段树节点的总长度不超过$O(n\lg n)$，每次建立凸包是$O(凸包大小)$的，所以建立所有凸包的复杂度为$O(n\lg n)$。询问的节点数不超过$O(n\lg n)$，每次三分是$O(n\lg n)$的，所以完成所有询问的复杂度为$O(n\lg^2 n)$。
BZOJ3534
总结了一下一类矩阵树问题的解决规律
考虑最基本的矩阵树定理，可以求解无向图无标号有根树（什么乱七八糟的有根没根有标号无标号根本搞不清楚）的个数。
Kirchhoff矩阵构造：考虑点，$A[i][i]$为$i$的度数。考虑边，若存在一条边$(i,j)$，那么$A[i][j]=-1$。
一个很重要的性质：每一行和每一列的元素总和都为0
算法原理其实是：这个算法考虑了每一个包含$n-1$条边的集合，若该集合能够形成一棵树，那么在最终答案中加$1$
矩阵树定理的拓展：假设每条边上有一个权值，并且要求所有生成树的边权乘积之和。那么考虑每条边$(i,j)$，$A[i][j]$为边权的相反数。考虑每个点，$A[i][i]$为与该点相连的所有边权（为了满足那条性质）。然后照旧求一下随便一个余子式就行了。
对于这道题，我们要求$$\sum_{T}\prod_{e\in T}P_e\prod_{e\notin T}(1-P_e)$$
那么我们先使e的边权为$\frac{P_e}{1-P_e}$，那么可以用拓展矩阵树定理求出$$\sum_{T}\prod_{e\in T}\frac{P_e}{1-P_e}$$
然后令$S=\prod_{e}1-P_e$
那么
$$\begin{align}
Ans & =S*\sum_{T}\prod_{e\in T}\frac{P_e}{1-P_e} \\
& =\sum_{T}\prod_{e\in T}P_e\prod_{e\notin T}(1-P_e)
\end{align}$$