2020-2021:teams:i_dont_know_png:week_summary_4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_4 [2020/05/30 17:32] qxforever [比赛] |
2020-2021:teams:i_dont_know_png:week_summary_4 [2020/05/31 13:39] (当前版本) qxforever [本周推荐] |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | === Codeforces Round #645 (Div. 2) === | + | === 2020.05.26 Codeforces Round #645 (Div. 2) === |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| 行 24: | 行 24: | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | |||
| + | |||
| + | |||
| + | === 范围相同的互质对统计 === | ||
| + | |||
| + | $$ | ||
| + | \sum _{i=1} ^n \sum _{j=1} ^n [(i, j)=1] = 2\sum _{i=1}^n \varphi(i) - 1 | ||
| + | $$ | ||
| + | |||
| + | 两两互质个数减去 $(1, 1)$ 的情况。也可以写成 | ||
| + | |||
| + | $$ | ||
| + | \sum _{i=1} ^n \sum _{j=1} ^n [(i, j)=1] = \sum _{d=1}^n \mu(d) \left\lfloor \frac nd \right\rfloor ^2 | ||
| + | $$ | ||
| + | |||
| + | === $\mu$ 的拆解 === | ||
| + | |||
| + | $$ | ||
| + | \mu(ab) = \mu(a) \mu(b) [(a, b) = 1] | ||
| + | $$ | ||
| + | |||
| + | 这个比较显然，因为存在平方因子就是 $0$ 了。 | ||
| + | |||
| + | === $\varphi$ 的拆解 === | ||
| + | |||
| + | 若 $(a, p) = 1$，则 | ||
| + | |||
| + | $$ | ||
| + | \varphi(ap^k) = \varphi(a) \cdot \varphi(p) \cdot p^{k-1} | ||
| + | $$ | ||
| + | |||
| + | 这说明对 $k > 1$ 的质因数 $p$，它都可以直接丢出来。换句话说，如果 $n = \prod p_i^{k_i}$，令 $x = \prod p_i,\ y = \prod p_i^{k_i-1}$，则 | ||
| + | |||
| + | $$ | ||
| + | \varphi(n) = \varphi(xy) = \varphi(x) \cdot y | ||
| + | $$ | ||
| + | |||
| + | 暂时不知道可以做什么。 | ||
| + | |||
| + | === min_25 筛与分块点 === | ||
| + | |||
| + | min_25 筛中，分块的方案是这样的（令 $n = 10$）： | ||
| + | |||
| + | ^值 ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^ | ||
| + | |向下取整 |10 |5 |3 |2 |2 |1 |1 |1 |1 |1 | | ||
| + | |分块点 |√ |√ |√ | |√ | | | | |√ | | ||
| + | |||
| + | 即是说，分块点是向下取整的值相同时，能取到的最大值。所以在两个分块点 $(a, b]$ 的部分就是一块，可以直接用 $f(b) - f(a)$ 当前缀和。 | ||
| + | |||
| + | |||
| 行 29: | 行 79: | ||
| - | === === | + | === ARC 092 B - Two Sequences === |
| - | [[|题目链接]] | + | [[https://atcoder.jp/contests/arc092/tasks/arc092_b|题目链接]] |
| - | **题意**： | + | **题意**：给两个非负序列 $a_1, a_2, \ldots, a_n$ 和 $b_1, b_2, \ldots, b_n$，求所有 $a_i + b_j$（可重复）的异或和。 |
| - | **题解**： | + | $n \in [1, 2 \times 10^5]$，数组元素在 $[0, 2^{28}]$ 内。 |
| + | **题解**：显然可以按位考虑贡献。如果我们固定了一个 $a$ 和二进制中的某一位 $k$，相当于考虑有多少个 $b_i$，满足 $a + b_i$ 的第 $k$ 位是 $1$。 | ||
| - | ===== 个人训练 - qxforever ===== | + | 这个东西就很好玩了：如果给所有 $a + b_i$ 模 $2 \cdot 2 ^{k-1}$，则余数落在 $[2^{k-1},\ 2 \cdot 2^{k-1})$ 之间的数都是满足要求的。 |
| + | 归纳一下，二进制表示中 $x$ 的第 $k$ 位为 $1$ 的充要条件是，$x \in [2^{k-1},\ 2 \cdot 2^{k-1}) \pmod {2 \cdot 2 ^{k-1}}$。这个性质可以用来统计加减法操作中的位运算结果。 | ||
| + | |||
| + | |||
| + | |||
| + | ===== 个人训练 - qxforever ===== | ||
| + | |||
| + | 本周基本没有训练 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| 行 50: | 行 108: | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| ==== 本周推荐 ==== | ==== 本周推荐 ==== | ||
| 行 56: | 行 114: | ||
| === === | === === | ||
| - | [[|题目链接]] | + | 无 |
| ===== 个人训练 - Potassium ===== | ===== 个人训练 - Potassium ===== | ||
| + | |||
| + | 本周进入考期，暂停训练。 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | 无 | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| - | ==== 本周推荐 ==== | ||
| + | ==== 本周推荐 ==== | ||
| - | === === | + | 无 |
| - | + | ||
| - | [[|题目链接]] | + | |
| - | + | ||
| - | **题意**： | + | |
| - | + | ||
| - | **题解**： | + | |
2020-2021/teams/i_dont_know_png/week_summary_4.1590831169.txt.gz · 最后更改: 2020/05/30 17:32 由 qxforever
