杜教筛

求 $\sum_{i=1}^{n} \phi(i^2)$

基本上是裸的杜教筛

一个关于 $\phi$ 的性质：$$\phi(ij) = \frac{\phi(i)\phi(j)gcd(i,j)}{\phi(gcd(i,j))}$$

证明：该式本质上是容斥，$\phi$ 的原式子是，当 $n = {p_1}^{c_1}\times {p_2}^{c_2} \times ··· \times {p_m}^{c_k}$

$\phi(n) = n \times \prod_{i=1}^{m} (1 - \frac{1}{p_i})$

这里式子就表示为先把 $i$ 和 $j$ 的质因数乘上在除去 $i,j$ 的共同质因数，即 $\phi(gcd(i,j))$，最后再消掉 $gcd(i,j)$ 即可得到该式。

然后开始推式子：

$$ \sum_{i=1}^{n} \phi(i^2) = \sum_{i=1}^{n} i \times \phi(i) $$

不难发现该式等于 $\phi \cdot id$

$$ (\phi \cdot id) \ast id = \sum_{d\mid n} d * \phi(d) * \frac{n}{d} = n \times \sum_{d\mid n} \phi(d) = id^2$$

我们设 $f(n) = n \times \phi(n),S(n) = \sum_{i=1}^{n} f(i)$ ,这里的 $id$ 与 $id^2$ 的前缀和都比较好求。

运用杜教筛公式可得：

$$ S(n) = \sum_{i=1}^{n}i^2 - \sum_{i=2}^{n} i * S(\lfloor\frac n i\rfloor)$$

$$ = \frac{n(n+1)(2n+1)}{6} - \sum_{i=2}^{n} i * S(\lfloor\frac n i\rfloor)$$

线性筛出前 $n^{\frac{2}{3}}$ 项，整除分块即可

点击查看题解

幸せな明日を願うけど 底なしの孤独をどうしよう

もう うめき声しか出ない  わたし ぎゅうぐらりん

强度最低的一集。

考虑一个点 $(p_1,...,p_k)$ 的距离应该怎么算。

不难发现只可能是他们奇/偶最短路的最大值。也就是在距离最大的点到达前，其他所有的点都在某条边上来回横条。

记 $f_{u,0/1}$ 表示点 $u$ 的偶/奇最短路，那么答案就是

$$\sum_{S=\{p_1,...,p_k\}}{\min(\max_{u\in S}(f_{u,0}),\max_{u\in S}(f_{u,1}))}$$

既有min又有max，不是很好算。考虑min-max容斥，则答案为

$$\sum_S{\max_{u\in S}(f_{u,0})}+\sum_S{\max_{u\in S}(f_{u,1})}-\sum_S{\max_{u\in S}(\max(f_{u,0},f_{u,1}))}$$

注意到三者完全等价，我们只考虑第一项。

考虑将 $u$ 按 $f_{u,0}$ 升序排序后依次扫，那么问题转化为：

每次往某个组加入一个点，求从每个组中各选出一个点的方案数。

预处理逆元，容易做到线性复杂度。

观察题图可知，一个骑士能攻击到的格子与自己所在的格子异色，所以有一种摆法是都摆在同一颜色的格子上，把一条相互攻击的关系变为网络流路径，这样就将扔掉骑士转化为了求最小割

因为一个骑士能与多个骑士互相攻击，所以可以共用路径

建图如下：

·源点向每个黄格子连边，流量为1

·每个黄格子向能攻击到的红格子连边，流量为∞

·每个红格子向汇点连边，流量为1

跑最大流求出最少扔掉几个骑士，答案为n^2−m−maxflow

あがいた梦を捨てて揺れる今日は眠って誤魔化せ

失くした言葉を知らないなら　各駅停车に乗り込んで

非常好凸包题，我不会一点。

首先尝试将答案写的形式化一点。令路径依次经过 $(i,a_i)$，则 $a_0=1,a_x=y,a_i\le a_{i-1}$，答案为

$$\sum_{i=1}^{x-1}{C_{a_i}}+\sum_{i=1}^{x}{(a_i-a_{i-1})i^2} =x^2y-1 +\sum_{i=1}^{x-1}{C_{a_i}-(2i+1)a_i} $$

令 $f_{i,j}$ 表示 $a_i=j$ 时的最小答案，根据斜率优化，决策点应该在 $(j,c_j)$ 的下凸包在斜率 $2i+1$ 的切点。

而我们注意到，随着 $i$ 的增大，$2i+1$ 也增大，那么决策点会单调右移。

如果从 $f_{x,y}$ 开始倒序模拟决策过程，那么就是在 $1\sim y$ 的下凸包上，先找到斜率 $2x+1$ 的切点 $p$，之后不断在 $p$ 原地决策，直到 $2i+1$ 小于 $p$ 与 $p-1$ 之间的斜率后，决策点会变为 $p-1$，然后重复……

注意到除了最开始的 $p$，再往后的决策是固定的，可以直接预处理贡献。而 $p$ 可以凸包二分求出，$p$ 的贡献也是容易计算的。

对于多组询问，注意到不同的只有 $y$ 的限制。考虑将询问离线挂到 $y$ 上，在维护到 $1\sim y$ 的凸包时计算答案。

时间复杂度 $O(q\log n)$。

君よ いっそいっそ いなくなれ

変わらない このままなら

显然题中生成的BST就是笛卡尔树，但是如果因此就往子树合并类的DP想的话就寄了（比如我）。

正确的做法是，将点的深度转化为祖先的个数，进而转化为每个点成为它祖先的方案数。即

$$Ans_u=\sum_v{\sum_{BST} [v\in anc(u) ]}$$

而 $ [v\in anc(u) ]$ 的充要条件是 $v$ 是 $u,v$ 间的最小值。

如果不考虑 $(u,v)$ 的限制，计算恰有 $k$ 个逆序对的排列数是经典的。令 $f_{i,j}$ 表示 $i$ 个数的排列，已有 $j$ 个逆序对的方案数，枚举 $p_i$ 与前 $i-1$ 位的相对大小，有

$$f_{i,j}=\sum_{k=0}^{i-1} f_{i-1,j-k}$$

这是可以写作生成函数的，令 $F_i=\sum f_{i,j}x^j$，有

$$F_n=\frac{\prod_{i=1}^n(1-x^i)}{(1-x)^n}$$

这允许我们 $O(n^3)$ 的计算总方案数。

现在有了 $(u,v)$ 的限制，先考虑 $u>v$ 的情况。

注意到上面的DP实际上是在往排列中一个一个塞数，而往最前端塞和最后端塞实际上是等价的。

那我们可以先将 $u,v$ 间的数先塞完，那么其它数就跟正常一样的。而增加的限制无非就是在塞 $v$ 的时候令 $k=0$，因为 $v$ 最小，无法产生逆序对。记 $L=u-v+1$，那么我们只用撤销第 $L$ 次转移，即

$$G=\frac{\prod_{i=1}^n(1-x^i)}{(1-x)^n} \frac{1-x}{1-x^L}$$

那么当前的贡献就是 $[x^k]G$。

上面的式子直接算的话是 $O(n^4)$ 的。

我们可以先预处理 $\prod_{i=1}^n(1-x^i)$，并递推求出 $(1-x)^{n-1}G$，然后计算 $[x^k]G$，就可以做到 $O(n^3)$了。

对于 $u<v$ 的情况，无非就是在塞 $v$ 的时候令 $k=L-1$，做法是类似的，不再赘述。

注意到还有 $u=v$ 的贡献，其实就是没有限制的方案数。

于是总时间复杂度 $O(n^3)$。