24.4.18 考试小记

发布于 2018-04-24  2.86k 次阅读


T2

给定n、m$$\sum _{i=1} ^{n} \sum _{j=1} ^{n} \sum _{d=1} ^{m} f_{d} (gcd(i,j))$$

其中:$$f_{d}(n)= \prod (-1) ^{a_i} [a_i \leq d]$$ $$ n=\prod p_{i} ^{a_{i}},n \leq 10^{10},m \leq 40$$

考试的时候大力反演了一波,把式子大概弄成了n^0.75?,之后线性筛f(),这也是我的算法的瓶颈了,加上m=1杜教筛的部分分,一共得到了60分,如果分段打表,还能多骗10分。

正解把我的mu的部分换成了phi,然后这个部分可以直接杜教筛了,那么就来推一推式子:

$$ans=\sum _{i=1} ^{n} \sum _{d=1} ^{m} f_{d}(i) t( \lfloor \frac{n}{i} \rfloor )$$

其中:$$t(n)= \sum _{i=1} ^{n} \sum _{j=1} ^{n} [gcd(i,j)=1] \\ =2(\sum _{i=1} ^{n} \phi (i) ) -1$$

这一部分可以杜教筛,时间复杂度为O(n^0.67)。之后,我们只要快速算出前一部分的f,就可以解决问题了。

$$F_{d}(n)=\sum _{i=1} ^{n} f_{d}(i) \\ = \sum _{i=1} ^{n} \mu(i) \sum _{j=1} ^{ \lfloor \frac {n} {i^{d+1}} \rfloor} \lambda (i^{d+1}j)$$

这一部分的意思其实就是枚举至少不合法的部分进行容斥,具体就是首先让其变成不合法的,剩下的部分就随便选了。接下来,由于lambda其实是一个完全积性函数,所以我们可以直接提出来,变形:

$$= \sum _{i=1} ^{ \lfloor n ^ { \frac {1} {d+1}} \rfloor} \mu(i) \lambda (i^{d+1}) \sum _{j=1} ^{ \lfloor \frac {n} {i^{d+1}} \rfloor} \lambda (j)$$

因为i的上界很小(最大才n^0.5),且作为分母变化很快,所以我们根本不必分块,我们只要做到快速求出lambda的前缀和,这个式子就可以干掉了。

要继续,首先要通过打表或者观察有一个并不显然的结论(其实可以感性理解):

$$\sum _{d|n} \lambda (d) = [n为完全平方数] $$

之后,就可以卷积一下用杜教筛直接搞定了,对于比较小的直接在线性筛的时候处理出来,总复杂度O(n^0.67)。

一点常数优化的技巧就是mu可以直接弄成char,还有这道题的模数很好,直接让int自然溢出。

 

T1

久违的数据结构。

长度为n的序列,查询q次,给定常数w,每次查询区间k小值,如果某个数值出现次数超过了w则直接忽略。

因为我们加上了恶心的限制,所以需要考虑更多维数的信息。考虑每个位置的数对于左右端点在一定范围内查询的影响。假设一次查询中,最后出现的至多w个相同数字有贡献1,那么如果存在倒数第w+1个,则它的贡献是-w。这样,其实我们的操作就是矩形加法,单点查询了。具体实现上,由于左端点的范围是一个前缀,而右端点的范围则可以是正常的区间,因此可以使用主席树套主席树,外层对于序列的每一个位置开一棵前缀主席树,外层主席树的下标就是值域,因此我们可以每次差分之后在外面跑二分,每个外层节点内套一个主席树,下标是序列的下标,表示右端点的范围限制,过程比较鬼畜不太好想象。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974