2022-02-10 Test

real: 68 + 0 + 0

expect: 100 + 40 + 0

T1 被卡常了，T2 被输入埋了

links

sol

# 简单最优化问题

​ 枚举个$gcd$ ，使用 $Dirichlet$ 前缀和优化。

# 简单数学题

​ 一种题解做法是枚举第 $i$ 个位置有贡献然后使用积分。

​ 实际上可以下一步转换不必使用积分，而是考虑每个位置，他们的可取值域要每次相对来说会乘一个阶乘，而给他们任意取值后每个位置成为最大值的机会均等，然后就可以推出柿子：

$$Ans= \sum_{i=1}^n {(i-1)!\over i^i}$$

上面那个 $(i-1)!$ 就是乘了一个 $1\over n$ 后的剩余结果。

这个柿子直接 $\mathrm O(n\mathrm log n)$ 即可做到 40pts ，我们考虑线性做法，就是要快速算出 $i^i$ 。利用原根，我们知道 $i^i=g^{i\times \mathrm{log_gi}}$

然后 $\mathrm {log}_gi$ 扫一遍就好

这题 tm 卡常，奇技淫巧我也不会。

# 简单数据结构题

考虑如果我们知道一个点子树内所有数字权值的 $\texttt{bitset}$ ，如果是手写的，我们很容易求出答案即 $val(sd)\&val(sd+k)$ ，$val(x)$ 表示取 $x$ 后 $64$ 位。

考虑优化，显然可以按 $dfn$ 序分块，我们可以预处理两两块之间的 $\texttt{bitset}$ ，然后这题卡空间，于是利用 $dfn$ 的性质，两两子树区间只可能包含或不交，于是我们要处理的相当于是一棵 二叉树上的所有节点，叶子有 $B$ 个，也就是 $2B$ 个区间，之间预处理就好。

题解的分块方式是在树上选一些点为关键点，处理他们子树中的 $\texttt{bitset}$ ，若一个点 $u$ 内子树最大一个被处理过的关键点 $mx$ 使得 $siz_u-siz_{mx} \ge B$ ，你就把这个点也给染黑。

由于这题 tmd 卡空间，所以需要调参卡一下块长。

出题人诚实谦卑。