感觉题目质量比较高,所以挖了个坑((。
X2
前三题简单不写
洛谷 - P10855
傻逼赛时想出两种正确思路都他妈的没仔细想,真糖丸了
不妨将题目中要求的式子化简。
\[\begin{equation} \begin{split} \sum\limits_{i=1}^n\sum\limits_{j=1}^i \gcd(j,i\oplus j)^k&= \sum\limits_{j=1}^n\sum\limits_{i=j}^n \gcd(j,i\oplus j)^k\\ &=\sum\limits_{j=1}^n\sum\limits_{x=1}^{\min(2^{18}-1,2n)} \gcd(j,x)^k[j\le x\oplus j \le n] \\ &=\sum\limits_{d=1}^nd^k\sum\limits_{j=1}^ n\sum\limits_{x=1}^{\min(2^{18}-1,2n)} [d\mid j][d\mid x][j\le x\oplus j \le n] \\ \end{split} \end{equation} \]不妨记 \(f_d\) 为 $\sum\limits_{j=1}^ n\sum\limits_{x=1}{\min(2-1,2n)} [d\mid j][d\mid x][j\le x\oplus j \le n] $,本质上表示合法的 \(d\mid \gcd(j,x)\) 的数量,记 \(g_d\) 为合法的 \(d=\gcd(j,x)\) 的数量,有 \(g_d=f_d-\sum\limits_{i=1}^n g_i[d\mid i]\)。
考虑如何计算 \(f_d\) ,有异或操作通常在 Trie 上进行操作,将所有合法的 \(x\) 加入 Trie 中,将 \([j\le x\oplus j \le n]\) 差分,只统计 \([x\oplus j \le r]\) 两遍即可,而这是较为容易的,具体见代码。
总复杂度为 \( \mathcal{O}(\sum\limits_{i=1}^n \frac{n}{i}\times \log n)= \mathcal{O}(n\log^2n)\),可以通过此题。
洛谷 - P10856
怎么都说被出烂了,我怎么没见过??我怎么没见过??我怎么没见过??我怎么没见过??我怎么没见过??我怎么没见过??
若在一次 2 操作前做了若干次 1 操作,我们可以看作只进行了一次 1 操作,因为有结合律。
有区间询问不妨使用线段树,注意到 \(n\) 为 2 的整数次幂,所以线段树的结构类似与 01-trie 的结构,左儿子表示当前这一位为 0 所包含的区间,右儿子表示当前这一位为 1 所包含的区间,一个结点内所有包含的位置的二进制前缀相同,即对于一段线段树上的区间 \([l,r]\),若其在第 \(i\) 层(从 0 开始,则 \([l,r]\) 二进制前 \(i\) 位相同,后面的位为 \([0,2^{(k-i)}-1]\)。
考虑修改操作 \(x\) 对于一段线段树区间 \([l,r]\) 的变换,不妨设区间 \([l,r]\) 的深度在第 \(i\) 层。
若 \(x\le r-l+1\),由上发现变换后原先的数还在 \([l,r]\) 中。
若 \(x\ge r-l+1\),由上发现 \([l,r]\) 的前缀改变了,转换成了另一个区间 \([l',r']\),且满足两个区间同层且 \([l,r]\) 的固定前缀 \(\oplus\) \(x\) 前 \(i\) 位 \(= [l',r']\) 的固定前缀! 那么\([l,r]\oplus x\) 变换为 \([l',r'] \oplus x后k-i位\)。
不妨预处理出 \(x\le r-l+1\) 的答案,答案的形式为 \(1+\sum a_{i}\neq a_{i+1}\),维护后者即可。总复杂度 \(O(n\log n)\)
洛谷 - P10857
本月找时间补
标签:le,赛时,limits,sum,mid,VP,oplus,MX,gcd From: https://www.cnblogs.com/smilemask/p/18358638