Pozhu's blog

对数论中一些基础知识点的整理

诗句选

Maximum Sine题意求 $[a, b]$ 中使得 $f(x) = \left|\sin\left(\frac{p}{q}\pi x\right)\right|$ 取得最大值的整数 $x$。且 $x$ 可能有多个取值，请输出符合条件的最小的 $x$。 $t$ 组询问，每次给出 $a,b,p,q$。 数据范围满足 $1 \le t \le 100,0 \le a \le b \le 10^9,1 \le p,q \le 10^9$ 单独为本题开一篇文章，理由在于其具有复杂度优秀的三种解法，复杂度逐渐变低而效率逐渐提高。 扩展做法将专注于解决从本题中抽象出的模型。 于是先放一个最好理解的本题做法，作为讲本题时的内容 题解观察容易得出要求一个小于线性的做法。 考虑如何转化本题的设问。 要求使 $f(x) =\left|\sin\left(\frac{p}{q}\pi x\right)\right|$ 最大的整数 $x$，考虑三角函数的周期性，我们有如下转化。 要求上式 $\sin$ 的绝对值最大，即要求 $\sin$ 括号内的值 $\frac{p}{q}\pi x $ 最接近于 $(k ...

杂题选讲Xor Sum给出正整数 $N$。 求出整数对 $u$ 和 $v$ $(0 \le u,v \le N)$ 的数目，使得存在两个非负整数 $a$ 和 $b$ 满足 $a\ xor\ b = u$ 和 $a\ +\ b= v$ 。这里，$xor$ 表示按位异或。 要求对答案取模 $10^9 + 7$。 $N \le 10^{18}$ 题解 ： 云剪贴板 すぬけ君の塗り絵 2题意 ： 平面上有一个左下角坐标 $(0,0)$ 右上角坐标 $(W,H)$ 的矩形，起初长方形内部被涂白。 现在给定 $n$ 个点，你每次在以下 $4$ 种操作中选择一种： 将矩形内 $x<x_i$ 的区域涂黑 将矩形内 $x>x_i$ 的区域涂黑 将矩形内 $y<y_i$ 的区域涂黑 将矩形内 $y>y_i$ 的区域涂黑 现在你需要最大化操作后白色矩阵周长。 $1 \le W,H \le 10^8$ $1 \le N \le 3 \times 10^5$ $x_i,y_i$ 取值保证合法，输入都是整数，给定的 $n$ 个点坐标两两不同。 题解 ： ARC063F すぬけ君の塗り絵 ...

索引

群论的最基础内容，不深入探究。

这里记录一些见到过的动态规划及常见优化，备忘用。 由于笔者时间不足，或许会写得很简略。 [ARC059E] キャンディーとN人の子供 前缀和优化DP 一个拆贡献的想法是单独考虑每个人的贡献。 设 f[i][j] 表示前 $i$ 个人发了 $j$ 颗糖的答案。 所以贡献应当是每一个分开计算。 然后计算的方法就是相当于把这个人的这一项提出来，剩下的部分进行求和。 式子 : f[i][j] = \sum_{k=0}^j f[i-1][j-k] \left ( \sum_{x = a_i}^{b_i} x^k \right )显然答案是 f[n][c] 枚举当前(第 $i$ 个)人获得了 $k$ 块糖果，那么新的贡献是前边人的贡献乘上他的贡献。 为什么能这么计算呢？ 显然小编也不会，所以小编才在补NOIp2021T2时回来翻这题。

这是关于NOIp2021VP的总结和改题记录 可惜VP之前忘了周日提前回宿舍，所以没有打足时，少打了50min左右。 但是得分也想必不会有很大波动——最多再多出T4的不到30分暴力。 最终得分情况是 100 + 10 + 32 + 0 = 142 ，在去年可以擦线省一，但是对于难以有更高的奢望。 这分数是不令人满意的，所以我应当从中汲取经验。 赛时出现了几个失误 ： 对数组空间预估错误。 T1开场想到筛法，然后觉得 $1e7$ 数组开不下转而乱搞。虽然最终也能过题，但是乱搞过题是不应当的，而且浪费了大量时间进行卡常，并具有不正确的复杂度。 后来经交流发现数组开的下，于是先想了线性筛。发现不会写之后转为埃氏筛，但是总时间花费很短。 T2暴力没有优化到最优，且没有想到状压DP正解。 想不出正解是能力问题，应当多做DP题加以训练。 暴力则是因为没有优化掉一个显然可以优化掉的 $n$ 导致少了 $10$ 分。这是不应当的。 T3没有观察出关键性质，最终只靠乱搞骗到 $32$ 分，然而看出性质的乱搞可以过题。 关键性质是由单调递增看出操作的本质是差分数组上进行交换。 在此性质的 ...

记一些图论中的定理和结论