目录 \[\mathfrak{Defining~\LaTeX~macros\dots} \newcommand{\floor}[1]{\left\lfloor #1\right\rfloor} \newcommand{\lcm}[0]{\operatorname{lcm}} \]
03.11
准备好 制造混乱 BOOM!
还是没熟练应对三题场啊… 思考效率挺低的. 下来想几下就都会了.
别用大样例调参! 别用大样例调参! 别用大样例调参!
A. 太阳照常升起
给出积性函数 \(\tau(p^c)=(-1)^c\), \(\xi=\tau\star I\), 求
\[\sum_{i=1}^n\sum_{j=1}^m\xi(ij). \]\(n,m\le10^{12}\).
- 「A.数学-数论」
设 \(\xi\) 在某个 \(p\) 的 Bell 级数为 \(\Xi(z)\), 显然有
\[\Xi(z)=\frac{1}{(1+z)(1-z)}=\frac{1}{2}\left(\frac{1}{1+z}+\frac{1}{1-z}\right), \]于是可以快速发现结论
\[\operatorname{SEQ}~\Xi(z)=\lang 1,0\rang^{+\infty}. \]所以 \(\xi(n)\) 即 "\(n\) 是完全平方数" 的真值.
省略一些奇奇怪怪的思路试错, 我们可以通过枚举 \(i\) 的出现奇数次的素因子积 (\(j\) 出现奇数次的素因子积也应当如此), 来拆掉一层和式. 不妨设 \(n\le m\), 有:
\[\textit{ans}=\sum_{k=1}^n\mu(k)^2\floor{\sqrt{n/k}}\floor{\sqrt{m/k}}. \]注意其中 \(\mu(k)^2=\mu(k)\cdot\mu(k)\), 限制了 \(k\) 只能是不同素数的一次幂乘积. 到此我们已经有了 \(\mathcal O(n)\) 的算法.
由于 \(\mu^2(p)=1=I(p)\), 对喜欢 Powerful Number 的兔诱惑巨大! 来尝试以此求出 \(\sum_{k=1}^n\mu(k)^2\), 设 \(\mu\cdot\mu=f\star I\), 那么
\[\sum_{k=1}^n\mu(p)^2=\sum_{i=1}^nf(i)\sum_{j=1}^{n/i}I(j), \]还是利用 Bell 级数可知 \(F(z)=1-z^2\), 这样就有 \(\mathcal O(\sqrt n)\) 求单点前缀和的算法. 很可惜 \(\mathcal O(n^{3/4})\) 还是过不了.
[KEY] 但是! 我们的任务始终是求出答案而非 "根号个前缀和"! 既然求不了, 我们不妨把 \(f\) 带回到原和式中:
\[\textit{ans}=\sum_{i=1}^nf(i)\sum_{k=1}^{n/i}\floor{\sqrt{n/(ki)}}\floor{\sqrt{m/(ki)}}. \]注意到有意义的 \(i\) 一定是完全平方数. 因而又可以写成
\[\textit{ans}=\sum_{i=1}^{\floor{\sqrt n}}f(i^2)\sum_{k=1}^{n/i^2}\floor{\sqrt{n/(ki^2)}}\floor{\sqrt{m/(ki^2)}}. \]可以两次整除分块算… 吗? 复杂度:
\[\begin{aligned} T(n) &\sim \sum_{i=1}^{n^{1/3}}(n/i^2)^{1/2}+\sum_{i=1}^{n^{1/3}}i^{1/2}\\ &\sim n^{1/2}\int_0^{n^{1/3}}\frac{\text dx}{x}+\int_0^{n^{1/3}}x^{1/2}\text dx\\ &\sim \mathcal O(\sqrt n\ln n). \end{aligned} \]结束. 顺带一提, \(f(i^2)=\mu(i)\), 回溯几步可以得到另一种推导路径, 只不过这个方法对兔更有启示罢了.
Remark.
没想到可以把 \(f\) 带回去算. 该说 PN 这些东西该被当成一种转化手段而非 "求前缀和的模板". 当然其他任何算法都是这样.
啊… 不知道这个复杂度是不是严格的, 两项的复杂度并没有平衡, 可能可以通过一些手段算出更严的上界.
B. 丧钟为谁而鸣
给定序列 \(\{a_n\}\) 和比例常数 \(p\%\). 进行 \(m\) 次区间赋值或区间查询, 查询时回答出所有在区间出现次数最多的颜色. 但若出现次数小于 \(p\%\) 倍区间长度, 则不需回答.
\(p\ge 20\), \(n\le10^5\), \(m\le3\times10^4\).
- 「A.随机化」
就, 随机化嘛. 珂朵莉树维护同色段, 每次询问在区间上测试 \(C\) 次: 随机一个位置, 查询其颜色在区间的出现次数, 然后按照要求保留答案. 单次测试的正确率是 \(\mathcal O(p\%)\) 的, 所以 \(C\) 取 \(100\) 左右就能做到全局的 \(99.999\%\) 以上的正确率. 可以 \(\mathcal O(mC\log n)\), 不过 \(n,m,C\) 没有平衡, 可能需要用一些根号算法平衡复杂度.
C. 老人与海
给定 \(\{a_n\}\), \(q\) 次询问, 每次给出 \(h\), 求
\[G(z)=\prod_{i=1}^n\frac{1}{1-z^{a_i}} \]从低到高第一项系数 \(\ge h\) 的项, 或指出其不存在.
\(n\le5\), \(a_i\le10\), \(q\le100\), \(h\le10^{15}\).
- 「A.数学-生成函数」「B.Tricks」
\(G(z)\) 不方便提取系数的原因是 \(a_i\) 不同, 而它们都在无穷级数中呈现, 因而我们没法化简也没法暴力算. [KEY] [TRICK] 既然如此, 我们可以将不同的 \(a_i\) 放在有穷的地方, 然后暴力求出对应多项式. 当然, motivation 是不平凡的, 构造是信手拈来的, 令 \(w=\lcm_{i=1}^n\{a_i\}\), 构造
\[G(z)=\frac{1}{(1-z^w)^n}\prod_{i=1}^n\frac{1-z^w}{1-z^{a_i}}, \]看, 前面无穷的都一样, 后面有穷的随你怎么不一样都可以直接来. 设后面的乘积为 \(P(z)\), 那么
\[[z^k]G(z)=\sum_i\binom{n+i-1}{n-1}[z^{k-iw}]P(z). \]又显然, \(\forall k\in[1,n]\), 当 \(i<j\) 且 \(i\equiv j\pmod{a_k}\) 时, \([z^i]G(z)\le[z^j]G(z)\). 我们对每个剩余类二分求出最小的合法位置再取最小值作答案即可. 询问复杂度总和精细描述为 \(\mathcal O(q\cdot \min\{a_i\}\cdot wn/w\cdot\log h^{1/n})\), 分别对应询问次数, 最优剩余类划分数量, 求 \([z^k]G(z)\), 二分上界 (通过上面的推导可以看出, 系数是关于指标的 \(n\) 次多项式), 这一复杂度即 \(\mathcal O(q\min\{a_i\}\log h)\), 非常快. 可惜求 \(P(z)\) 需要 \(\mathcal O(n^2w)\). 反正出题人肯定没想到这一步, 不知道还能不能优化.
标签：mu,Set,frac,floor,sum,Solution,sqrt,Simus,mathcal From： https://www.cnblogs.com/rainybunny/p/17206555.html