比翼鼠の博客

摘要： 阶 设 \(n > 1\) 且 \(a\) 是满足 \((a, n) = 1\) 的整数，则必定有一个 \(a^r \equiv 1 \pmod n\)，其中 \(r \in [1, n - 1]\)。 原因是 \(a^0, ...,a^{n - 1}\) 都与 \(n\) 互质，所以它们模 \(n 阅读全文

摘要： 晚上去吃火锅了，到家都九点半了，成功错过这一场。还好报了 Unrated。 E 神秘计数题。 这东西看着就必须根号才能过，而且很能写成整除分块的形式。 然后要先考虑枚举一个数再确定剩下两个数，感觉过去枚举 \(b\) 最好，然后你发现 \(a = kb + c\)，于是如果你确定了 \(a\) 那 阅读全文

摘要： CF797E 根号分治，预处理一个 \(f_{p, k}\) 表示询问 \(p, k\) 需要的操作次数答案。 CF337D 点分树模板。 现学的点分树，思路是对于每棵子树以重心为根重建完预处理出 \(sgt\) 和 \(ch\) 两棵线段树，分别用于查询子树内距离重心距离为 \([l, r]\) 阅读全文

摘要： 更好阅 前言 本文记录个人对于 \(\mathcal{Miller-Rabin}\) 和 \(\mathcal{Pollard-Rho}\) 的一些理解，一些证明可能不是很完美，欢迎指出。 喵呜喵呜喵喵喵~ Miller-Rabin 二次探测定理 如果 \(p\) 是奇素数，则 \(x^2 \equ 阅读全文

摘要： 更好的阅读体验？ AcWing 都是学长的推题！ P12421 【MX-X12-T4】「ALFR Round 5」游戏 注意到 \(n\) 个点的树，最多只能查询 \(n - 1\) 次，所以考虑每次至少排除一个点的做法。 考虑每次对着叶子操作，那么如果返回的是距离，就可以排除这个叶子或者确定这个叶 阅读全文

摘要： 真的会有人看这种东西吗。 夕阳洒在蒙德的广场上，傍晚的风吹起塔利雅的粉色发丝。塔利雅抚摸着胸前的水神之眼，注视着眼前的雕像。 大广场的风神像清洁一直都是塔利雅的工作。温迪还在蒙德时，他总能遇见坐在神像手心中的吟游诗人。 只是温迪已经半年没来过了。塔利雅闭上眼，双手合十，跪在风神像前祈祷。赤霞浸染了塔 阅读全文

摘要： 更好阅 ARC193C Grid Coloring 3 考虑题目中给出的十字覆盖正着计数很困难，所以正难则反，倒过来做。 考虑反过来的第一次操作相当于把一个颜色相同的十字上的颜色都换成 \(0\)（我们把 \(0\) 定义为可以表示任何数的颜色）。进一步，我们考虑恰好有 \(r\) 行 \(c\) 阅读全文

摘要： 奖池还会继续累加 P1654 OSU! 考虑记录 \(a_i\) 位前 \(i\) 位且第 \(i\) 位为 \(1\) 的连续 \(1\) 长度的期望，注意这里对于诸如 \(1101\) 的贡献为 \(1\)。 那么有 \(a_i = (a_{i - 1} + 1) \times p_i\)。 同 阅读全文

摘要： D - Logical Filling 由于 \(X\) 保证非空，所以一定不存在不合法的情况比如 oo。 首先所有 o 旁边的两个空一定是 .，然后就剩下一些连续的问号段。容易发现如果有一段问号 \([l, r)\)，那么它对 o 的贡献最多是 \(\frac{r - l + 1}{2}\)。 如 阅读全文

摘要： 首先观察题面，期望乘上 \((\frac{n(n + 1)}{2})^q\) ，即乘上所有可能的操作数。其实就是求所有可能的值乘上方案数。可以根据期望的定义感性理解一下。 所有我们不妨先把答案的式子写出来，即 \(ans_i = \sum v_j \times h(i, v_j)\)，其中 \(h( 阅读全文