Difference between revisions of "2018 Multi-University, HDU Day 9"

From EOJ Wiki
Jump to navigation Jump to search
 
Line 29: Line 29:
 
现在对于这两种情况分开计算。
 
现在对于这两种情况分开计算。
  
先计算奇偶性完全相同的部分,$a,b$ 一定能表示成 $a=xc^2,b=xd^2$,其中 $x$ 无平方因子。枚举 $x$,那么就是计算 $\sum_{x=1}^n \mu^2(x)(\lfloor \sqrt {\lfloor \frac{n}{x} \rfloor }\rfloor)$,其中 $\sum_{i=1}^{n} \mu^2(i)=\sum_{i=1}^n \sum_{d^2|i} \mu(d)=\sum_{d=1}^\sqrt n \mu(d) \lfloor \frac{n}{d^2} \rfloor$ 可以暴力计算(需要常数优化),而 $\lfloor \sqrt {\lfloor \frac{n}{x} \rfloor }\rfloor$ 的取值至多 $O(\sqrt n)$,那么这部分能够在 $O(n^{\frac{3}{4}})$ 的时间内解决,这部分复杂度类似杜教筛,如果预处理了前 $n^{\frac{2}{3}}$ 项的话复杂度能降为 $O(n^{\frac{2}{3}})$。
+
先计算奇偶性完全相同的部分,$a,b$ 一定能表示成 $a=xc^2,b=xd^2$,其中 $x$ 无平方因子。枚举 $x$,那么就是计算 $\sum_{x=1}^n \mu^2(x)(\lfloor \sqrt {\lfloor \frac{n}{x} \rfloor }\rfloor)$,其中 $\sum_{i=1}^{n} \mu^2(i)=\sum_{i=1}^n \sum_{d^2|i} \mu(d)=\sum_{d=1}^\sqrt n \mu(d) \lfloor \frac{n}{d^2} \rfloor$ 可以暴力计算,而 $\lfloor \sqrt {\lfloor \frac{n}{x} \rfloor }\rfloor$ 的取值至多 $O(\sqrt n)$,那么这部分能够在 $O(n^{\frac{3}{4}})$ 的时间内解决,这部分复杂度类似杜教筛,如果预处理了前 $n^{\frac{2}{3}}$ 项的 $\mu^2$ 前缀和的话复杂度能降为 $O(n^{\frac{2}{3}})$。
  
 
对于奇偶性不同的部分,考虑每个质数 $p​$ 产生的贡献。设 $A_p​$ 为 $[1,n]​$ 中 $p​$ 的指数为奇数的个数,那么 $p​$ 产生的贡献可以表示成 $p \times A_p \times (n - A_p)​$。其中 $A_p = \sum_{i\ge1} (-1)^{i-1} \lfloor \frac{n}{p^i} \rfloor​$。对于不超过 $\sqrt n​$ 的素数 $p​$,暴力计算这部分贡献,复杂度是 $O(\frac{\sqrt n}{\ln \sqrt n} \log n)=O(\sqrt n)​$。对于超过 $\sqrt n​$ 的素数 $p​$,有 $A_p = \lfloor \frac{n}{p} \rfloor ​$,由于 $A_p​$ 的取值只有 $O(\sqrt n)​$ 中,对于特定的 $A_p​$,需要求出一定区间内素数的和,这部分使用 $O(n^{\frac{3}{4}}/\log n)​$ 的亚线性筛(洲阁筛 或者 Min_25筛 的前半部分(其实是一样的))处理(只需要计算一次 $\sum_{i=1}^n i [i \text{ is prime}]​$,就会顺便把所有需要的前缀和求出来)。
 
对于奇偶性不同的部分,考虑每个质数 $p​$ 产生的贡献。设 $A_p​$ 为 $[1,n]​$ 中 $p​$ 的指数为奇数的个数,那么 $p​$ 产生的贡献可以表示成 $p \times A_p \times (n - A_p)​$。其中 $A_p = \sum_{i\ge1} (-1)^{i-1} \lfloor \frac{n}{p^i} \rfloor​$。对于不超过 $\sqrt n​$ 的素数 $p​$,暴力计算这部分贡献,复杂度是 $O(\frac{\sqrt n}{\ln \sqrt n} \log n)=O(\sqrt n)​$。对于超过 $\sqrt n​$ 的素数 $p​$,有 $A_p = \lfloor \frac{n}{p} \rfloor ​$,由于 $A_p​$ 的取值只有 $O(\sqrt n)​$ 中,对于特定的 $A_p​$,需要求出一定区间内素数的和,这部分使用 $O(n^{\frac{3}{4}}/\log n)​$ 的亚线性筛(洲阁筛 或者 Min_25筛 的前半部分(其实是一样的))处理(只需要计算一次 $\sum_{i=1}^n i [i \text{ is prime}]​$,就会顺便把所有需要的前缀和求出来)。

Latest revision as of 17:39, 8 September 2018

两个半小时签完到,最后两个 Last Hour。人生大起大落真刺激。

Problem A

Solved by zerol & kblack. 02:33 (+)

题意:在 n×m 的方格中填 1~nm 的数,使得只有一个数是它所在行列的最大值。

题解:显然那唯一一个数就是 nm。考虑从大到小依次填数,每个数肯定得填在一个之前填过的数的同一行或者同一列。dp[i][j][k] 表示已经填了 k 个数,已经有 i 行 j 列有数字的方案。转移有两种,一种是新开一行,一种是新开一列,还有就是填到 i 行 j 列的交叉处。


无比艰难的签到。

Problem B

Solved by kblack. 04:43 (+3)

题意:给一个 $n \times m$ 的 01 阵,一行删一个,错位不能超过 $K$ 问压缩掉删除的位置后组成的图案有几种。

题解:首先考察一行的情况,发现只有连续的字符中删除任意一个才能构成等价类。构造一个 $O(n m^3)$ 的算法,直到 $x$ 行,上一行选择 $[l, r]$ 的某种不同图案有 $dp[l, r]$ 种,考虑转移,先将区间扩展成 $[l-K, r+K]$ 然后用下一行的相同字符的区间去截,每个最多截出 $m$ 个区间,而且都是不同的图案,这么直接转移是 $O(m^3)$ 的。考虑优化这个过程,其实我们并不关心具体的区间,只要直到在某个范围里就会有若干种图案可以转移就好了。将区间拆成开闭,对于某个位置开头和结尾的数量分别记录。在扫描当前行前,先将所有开始标记左移动 $K$ 个位置,结束标签右移 $K$ 个位置,然后扫描过去,记录开头和结尾图案数的前缀和,当遇到当前行的分割点(颜色不同)的时候,我们只要把之前为闭合的区间(前缀和之差)手动闭合一下,下一个颜色开头的地方手动开启一下,就能轻松地维护与之前的区间等价的标记了,最后答案是最后一行的开头标记的和。

Problem C

Upsolved by zerol.

首先考虑 $d_{a,b}$ 的值,对于 $a,b$ 质因数分解后奇偶性不同的指数,可以花 $p$ 的代价修复,显而易见的是逐个修复比较划算(加法比乘法划算),特别的,如果 $a$ 和 $b$ 指数奇偶性完全相同,也要花费 $1$ 的代价。

现在对于这两种情况分开计算。

先计算奇偶性完全相同的部分,$a,b$ 一定能表示成 $a=xc^2,b=xd^2$,其中 $x$ 无平方因子。枚举 $x$,那么就是计算 $\sum_{x=1}^n \mu^2(x)(\lfloor \sqrt {\lfloor \frac{n}{x} \rfloor }\rfloor)$,其中 $\sum_{i=1}^{n} \mu^2(i)=\sum_{i=1}^n \sum_{d^2|i} \mu(d)=\sum_{d=1}^\sqrt n \mu(d) \lfloor \frac{n}{d^2} \rfloor$ 可以暴力计算,而 $\lfloor \sqrt {\lfloor \frac{n}{x} \rfloor }\rfloor$ 的取值至多 $O(\sqrt n)$,那么这部分能够在 $O(n^{\frac{3}{4}})$ 的时间内解决,这部分复杂度类似杜教筛,如果预处理了前 $n^{\frac{2}{3}}$ 项的 $\mu^2$ 前缀和的话复杂度能降为 $O(n^{\frac{2}{3}})$。

对于奇偶性不同的部分,考虑每个质数 $p​$ 产生的贡献。设 $A_p​$ 为 $[1,n]​$ 中 $p​$ 的指数为奇数的个数,那么 $p​$ 产生的贡献可以表示成 $p \times A_p \times (n - A_p)​$。其中 $A_p = \sum_{i\ge1} (-1)^{i-1} \lfloor \frac{n}{p^i} \rfloor​$。对于不超过 $\sqrt n​$ 的素数 $p​$,暴力计算这部分贡献,复杂度是 $O(\frac{\sqrt n}{\ln \sqrt n} \log n)=O(\sqrt n)​$。对于超过 $\sqrt n​$ 的素数 $p​$,有 $A_p = \lfloor \frac{n}{p} \rfloor ​$,由于 $A_p​$ 的取值只有 $O(\sqrt n)​$ 中,对于特定的 $A_p​$,需要求出一定区间内素数的和,这部分使用 $O(n^{\frac{3}{4}}/\log n)​$ 的亚线性筛(洲阁筛 或者 Min_25筛 的前半部分(其实是一样的))处理(只需要计算一次 $\sum_{i=1}^n i [i \text{ is prime}]​$,就会顺便把所有需要的前缀和求出来)。

Problem D

Solved by kblack. 01:29 (+1)

题意:和一个随机策略电脑玩限定猜拳©。

题解:似乎你随不随机都一样,那么就简单了,随便乘乘除除就好了。

kblack: 解决的关键一步在于发现样例四中 $19$ 是 $a+b+c$ 的倍数,将分数还原以后凑一下就发现公式了。

Problem J

Solved by ultmaster. 04:44 (+2)

题意:比较两个 $\log \cdots \log n ^{(\log \cdots \log n)^{(\log \cdots \log n)}}$ 的阶数。

题解:比赛的时候一通操作,动用了 Mathematica 观察了若干式子之后得出来一张图。在修了一堆 bug 之后发现算法根基就不大对,然后改改改,勉强 AC。

比赛后回顾了一下发现了半天的结论是显然的,如果更进一步的话,会发现完全没有这么复杂。

首先记 $\log \cdots \log n$ ($i$ 个 log) 为 $l(i)$ 两个式子都取 log 之后阶数的关系是不变的,会得到 $l(a) ^ {l(b)} l(c)$ 的形式。

记 $f(a,b) = l(a)^{l(b)}$,注意到 $l(c) \sim f(c,\infty)$。考虑一个更普适的问题比较两个 $f(a,b)f(c,d)$ 的阶数。只要两个里面阶数比较大的那个 $f$ 拿出来比较,如果相等,再比较小的即可。这又带来另一个问题就是如果比较两个 $f(a,b)$ 的阶数。注意到 $f(a,b) = l(a)^{l(b)}$,再取一次 log 即可。

注意处理一下 $\infty + 1 = \infty$。

Problem K

Solved by zerol. 00:47 (+)

温暖的签到。

zerol:那么迟才签到是因为看错题了。