GPHP Vol.1
GPHP Vol.1 Math
Introduction: 本计划将记录杂题，采用循序渐进的方法，先给出 Hint，然后给出 Solution，力求还原思维过程。记录什么题随缘。
这是 GPHP 第一期。每期计划 4-5 个题目。
Table of Content
- <luogu> P3312 [SDOI2014] 数表
- <luogu> P5298 [PKUWC2018] Minimax
P3312 [SDOI2014] 数表
P3312 [SDOI2014] 数表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
标签
莫比乌斯反演，前缀和，数据结构，最大公约数Hints
Hint1
注意到如果不考虑限制就是求 $\sum_{i=1}^n\sum_{j=1}^m \sigma_1(\gcd(i,j))$Hint2
枚举 gcd 以进行化简（经典套路）Hint3
你应该得到了 $$\sum\limits_{T=1}^n\lfloor\dfrac{n}{T}\rfloor\lfloor\dfrac{m}{T}\rfloor\sum\limits_{d|T}\sigma_1(d)\mu(\dfrac{T}{d})$$ 观察它，发现后面这一部分非常独立 有很多次询问，但是并不意味着每次都必须重新计算后面的部分。 那么对于不同的 a，为了避免重复计算后面的部分，你知道应该怎么做了吗？Hint4
转换视角，要避免反复计算，最重要的就是不能枚举约数，而是枚举倍数。 考虑动态维护后面这个式子。我们必须保证每个数只被枚举一次倍数。Hint5
请把询问从小到大，按 a 排序。然后动态维护，并做整除分块。Date 2024/08/16
[思考程度] 3/5
Solution
先不考虑 \(a\) 的限制，那么要求的即：
\[\sum_{i=1}^n\sum_{j=1}^m \sigma_1(\gcd(i,j))
\]
处理套在函数里面的 \(\gcd\) 常用的方法是枚举他，并使用反演结论得到：
\[\sum\limits_{T=1}^n\lfloor\dfrac{n}{T}\rfloor\lfloor\dfrac{m}{T}\rfloor\sum\limits_{d|T}\sigma_1(d)\mu(\dfrac{T}{d})
\]
考虑 \(a\) 的限制，注意到后面的部分比较隔离，所以就避免重复计算，每次枚举 \(d\) 的倍数动态更新，考虑到调和级数的限制，复杂度为 \(n\ln n\) 级别，由于整除分块的时候要用到后面那个函数的前缀和，故最后为一个单点修改区间查询的问题，可以使用树状数组解决。
Trick \(\mu * 1=[n=1]\) 、动态维护的思路、枚举因数转枚举倍数
插播一条，要求一个积性函数的值只需要求质数幂位置上的。
P5298 [PKUWC2018] Minimax
Link
标签
树形 dp，线段树合并Date 2024/08/17
Hints
Hint1
树形 dp 好像可以做耶。先设个 dp 试试Hint2
两维树形 dp，可以设为 f[i][j] 表示在 i 点权值为 j 的概率。 这个转移方程是前后缀和形式的，可以优化吗Hint3
要想合并两个数组，你能想到什么？ 这里有一条性质提供给你：左右儿子的数组有值的位置不重复。Hint4
线段树合并。Hint5
但是我们需要前缀和和后缀和啊。怎么维护呢。SubHint
考虑合并两个线段树的过程，是否能够多维护一点信息来完成转移？Final Answer
维护一个区间和，每次朝两边走的时候都可以动态维护前后缀。 当有一棵树只剩一边有节点的时候，在这个节点上打区间乘法标记。思考程度 5/5
Solution
Hint 足够清晰了。
Trick 需要一个信息的时候，可以考虑能不能动态求出。