不背图论板子要反省一下自己了。
A
求
\[\sum_{x=L}^{R}\sum_{y=L}^{R}[(x,y)\not=1,\frac{x}{(x,y)}\not=1,\frac{y}{(x,y)}\not=1] \]\(1\le L\le R\le 10^6\).
先容斥。假定 \(n\le m\).
\[\sum_{d=2}^{n}\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}[x\perp y,x\not=1,y\not=1] \]如果 \(x=1\) 或 \(y=1\) 那么 \((x,y)\) 一定被统计了，要减去 \(\displaystyle\lfloor\frac{n}{d}\rfloor+\lfloor\frac{m}{d}\rfloor-1\).
\[\Bigg(\sum_{d=1}^{n}\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}[x\perp y]-(\lfloor\frac{n}{d}\rfloor+\lfloor\frac{m}{d}\rfloor-1)\Bigg)-\sum_{x=1}^{n}\sum_{y=1}^{m}[x\perp y] \]前面一小块就是 \(nm\)，后面是 \(\displaystyle\sum_{p=1}^{n}\mu(p)\lfloor\frac{n}{p}\rfloor\lfloor\frac{m}{p}\rfloor\).
时间复杂度 \(O(n)\).
当然不用莫反估计也能做。
B
一张无向图。
-
问割边后两点的连通性。
-
问割点后两点的连通性。
\(n\le 10^5\)，\(m\le 5\times10^5\)，\(q\le 3\times10^5\).
第一个问题，边双缩点，判断树上两点所在的边双是否同时或同时不在一个点的子树内。
第二个问题，点双缩点，判断树上两点所在的点双的简单路径上是否包含一个点。
具体我也不知道码量多少。
正解应该是圆方树。
C
求 DAG 的一颗生成树，保证图上 \(in_n=0\)，试让所有非根节点的儿子数的最大值最小，并给出 \(0\sim n-1\) 的字典序最小的父亲序列。DAG 不连通输出 \(-1\).
\(n\le 50\).
不考虑字典序，先最小化儿子数的最大值，容易二分一个 \(k\)，建图直接跑最大流，\(maxflow=n\) 说明 \(k\) 合法。
再去想字典序的问题，假设已经确定 \(fa_{0\sim n-1}\)，枚举 \(fa_i\).
假设选择 \(fa_i\)，再建一遍图跑最大流，为 \(n\) 说明 \(fa_i\) 合法，继续枚举 \(i+1\).
要跑 \(n^2\) 次网络流，所以复杂度上界为 \(O(n^6)\)，常数小到爆炸。
标签：11,lfloor,le,frac,sum,rfloor,fa,2023.8 From： https://www.cnblogs.com/SError0819/p/17623059.html