洛谷4619 [SDOI2018]旧试题
Luogu LOJ 分析 首先要知道 显然我们可以 $O(C\log C)$ 预处理出 $f_a,f_b,f_c$ ,然而计算还是 $O(n^3)$ 的。 但是注意到 $O(n^3)$ 的枚举中会出现很多贡献为 $0$ 的情况: $\mu(x),\mu(y),\mu(z)$ 中有 $0$ 。 $\operatorname{lcm}(x,y)>A$ 或 $\operatorname{...
Luogu LOJ 分析 首先要知道 显然我们可以 $O(C\log C)$ 预处理出 $f_a,f_b,f_c$ ,然而计算还是 $O(n^3)$ 的。 但是注意到 $O(n^3)$ 的枚举中会出现很多贡献为 $0$ 的情况: $\mu(x),\mu(y),\mu(z)$ 中有 $0$ 。 $\operatorname{lcm}(x,y)>A$ 或 $\operatorname{...
Luogu 分析 下文中,设 $n\leq m$ ,$n/m=\left\lfloor\frac{n}{m}\right\rfloor$ 。 为了方便,设 $S(n)=\sum_{i=1}^ni=\frac{n(n+1)}{2}$ 。 令 $\mathbf{f}(i)=\frac{1}{i}$,$\mathbf{g}(i)=\mathbf{f}*\mu$ 。 括号内线性筛预处理,然后数论分...
Codefoces Luogu 分析 $\mathsf{\color{black}{x}\color{red}{gzc}}$ 讲这题,报警了... 首先要知道 $f$ 和 $g$ 都很好转移,同时 $dp$ 也很好转移了。 因为 DP 只统计了 $i<j$ 的情况,所以要答案要乘 $2$ ;最后答案记得还要乘上 $\frac{1}{n(n-1)}$ 。 其实这题写起来挺休闲的 代码 ...
Luogu 分析 首先要知道一个性质 即可。可以发现就是 这个题 $k=2$ 时的版本,直接复制过来即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #incl...
CodeForces 分析 对每个集合维护一个 bitset,第 $i$ 位表示 $i$ 作为因数的出现次数的奇偶性。 $1$ 操作预处理后直接赋值即可; $2$ 操作直接异或即可; $3$ 操作直接与即可。下面考虑 $4$ 操作怎么做。 设 $f(i)$ 表示 $i$ 作为因子的出现次数, $g(i)$ 表示 $i$ 的出现次数,那么有 $f(x)=\sum\limits_{x|d}g(d...
Luogu 分析 设 $\mathbf{f}(i)=i^k$,$\mathbf{g}(i)=\mathbf{f}*\mu$ 。 线性筛 $\mathbf{g}$ 的前缀和,然后数论分块计算即可。 代码 //It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib...