Pozhu's blog

前言被大佬WeLikeStudying 花了几乎一下午的时间讲明白之后有感而发决定写一篇题解来报答dalao的恩情。 原题链接 : U238921 大凯的疑惑（买得到的数目） 所以参考资料就是dalao的题解 题意给定 $a,b$ ，求能被 $ax+by$ （ $x,y$ 是非负整数）表示出来的第 $k$ 小数的大小。多测， $1 \le T \le 10^4$ 题解很相似的一道题是 小凯的疑惑（买不到的数目） 不过这题显然是那题的超级加强版（ 暴力做法首先考虑暴力，然后尝试优化。 可惜暴力也需要前置（ 由裴蜀定理的推论可知最大的不能被表示的数为(官方题解也给出了这个定理，并且它有自己的名字叫“麦乐鸡定理”)（所以知道这个定理的话就可以爆切小凯了） 并且由同一个推论稍微走远一点就可以得出一个对称性 ： $x$ 和 $ab-a-b-x$ 有且只有一个可以被表示出来， $ab-a-b-x+1$ 及以后的数都可以被表示，负数都不能被表示，我在 数论算法、定理和常用变换 的裴蜀定理板块给出了详细证明。 于是对于 $c > \frac{ab-a-b+1}{2 ...

内容摘要 ：本文主要包含以下数论基础知识点 ： 整除 、gcd 、lcm 、exgcd 、同余、同余方程 快速幂、费马小定理、逆元 埃式筛法、线性筛 欧拉函数、卢卡斯定理 感谢zh_dou学长的博客赞助（大概这篇文就是数论·易+oi-wiki罢 注 ： 本文已经年久失修，由于本文内容已经分散在其他文章中进行了更新，这里给出链接 ： Part1,2 : 数论杂谈 Part3 : 筛法，亚线性和线性 Part4 : 数论函数总结 和 数论算法、定理和常用变换 以上文章内容中对与本文重合的部分可能会有修改和补充。 但仍保留本文（因为如果啥时候得讲课可以把这个课件修一修拿来用） Part 1让我们从整除开始，这样对吧定义：设 $a,b\in Z,a \neq 0$。如果 $ \exists q \in Z$，使得 $b=aq$ ，那么就说 $b$ 可被 $a$ 整除，记作 $a \mid b$ ，且称 $b$ 是 $a$ 的倍， $a$ 是 $b$ 的约数（因数）。 $b$ 不被 $a$ 整除记作 $a \nmid b$ 。 任何正整数都是 ...

原题链接： P5380 挺好写的一道比较出名的题解，思路顺畅就没什么问题。 那么我们就以这道题为例，尝试探究分析条件复杂的问题的方法，探索条理清晰的答题思路。 审题：拿到一道大模拟的时候，首先要做的就是审清题，决定要做这道题的话，一定要保持程序的条理性。 通过对于题目问题的分析我们发现：本题并没有想象中的类似猪国杀的按照某一规则移动棋子，而是对于给定的操作序列判断其是否合法，并处理出相应的一些状态。 那么这道题显然是一道判定类题目，总之要比求解类好些的多，让我们继续分析： 我们要判断操作是否合法——这是这道题最难的一部分。在这之后，在棋盘上移动棋子的过程也变得十分简单——操作合法的话，看看你移动到的位置是否有对方棋子，若有的话则吃掉。剩下的操作是判断将军局面和游戏结束。游戏结束自然简单——如果将帅少了其中之一游戏自然结束。判断将军似乎很难，实际上你只需要遍历棋盘，判断每颗棋子移动到对方将（帅）的移动操作是否合法即可。显然，当一方棋子存在一步合法移动到达对方将（帅）的位置时，我们称此时构成了一个将军局面。 那么我们的实现思路逐渐清晰起来： 我们要完成的核心操作是对于一 ...

前言：在这里记录一下挖了多少坑，不然开的坑太多就忘了填（ 想写的和写了没写完的都算在内 博客·坑： 线性代数： 矩阵（后边一堆更难的东西），线性基 筛法： 杜教筛，min_25筛 定理： 威尔逊定理,exlucas,欧拉定理 多项式：all in all 生成函数： 狄利克雷生成函数，排列与圆排列 析合树的板子（不打算补 K-D Tree学习笔记 圆方树学习笔记 替罪羊树 字符串： 有限状态自动机系列 FFT、NTT、MTT、FWT 插头DP 群论 概率论，数学期望，期望DP 可持久化数据结构、线段树分治、虚树 优化建图 分治、点分治 莫比乌斯反演、贝尔数 题·坑图论 ： P5344 【XR-1】逛森林 P8099 [USACO22JAN] Minimizing Haybales P 构造 ： P5884 [IOI2014]game 游戏P8491 [IOI2022] 囚徒挑战 数论 ： CF1139D Steps to One 期望 ： P8190 [USACO22FEB] Cow Cam ...

前言：下定决心搞数学之后就开了个这坑。打算同时期开一下多项式（但是这俩坑啥时候填完就不晓得了），参考文献是oi-wiki 写之前翻了翻笔记本，发现很多现在觉得难的吓人的玩意寒假的时候竟然学过！！！ 但是看笔记本的字迹就知道当时反正是睡得很香了（ 所以现在才来补坑），效率高的话应该还不晚 线性代数部分主要打算写一下矩阵和线性基，毕竟这俩基本是一窍不通 线性基线性基其实就是线性空间的一组基底，使用线性基可以表示出原来的整个线性空间。 OI中常用到的是异或线性基，于是这里只介绍这一种。 下文的线性基默认为异或线性基。 说人话的话，对于一个数列而言，其线性基就是一个数的集合，取线性基中的若干数字异或起来可以得到原序列的每一个数。 线性基拥有如下性质 ： 取线性基中的若干数字异或起来可以得到原序列的每一个数。 线性基不能表示出 $0$，因此涉及线性基的题目如要考虑 $0$ 应当特判。 线性基中数的个数唯一，且在能保证上述性质的前提下，数量最少。 实际上对于一个无限集合，其线性基的元素个数可能是无限个，但是我们在OI中很少会遇到这样的情况，于是我们只研究有限集。 于是直接看怎 ...

QBXT总结章

琪露诺的冰雪小屋原题链接 ： P3693 这是我至今在洛谷见过的细节最细的模拟题，也是我迄今施工时间最久的模拟题。 题面含义为模拟跟踪一个人从收集冰砖到建造冰屋的全过程，考虑了很多细节。 大致需要完成五个操作，难度呈递增排列且在最后直线上升（关于我在90分卡了20天这件事） 今天摸了一眼题解，想明白了一些实现，灵机一动对源程序进行了大修，侥幸通过了这道题。所以有感而发，写下这篇题解。 显然题干很长，但是本题对阅读理解的要求几乎不亚于语文的现代文阅读一。我们从前往后逐步分析各个操作 ： 第一个操作 ：ICE_BARRAGE R C D S 这是本题最好完成的操作，按照题意模拟即可，实现时可以专门开一个二维数组维护地面信息，用一个三维数组维护整个空间的冰块信息（反正后边肯定得开），注意地面的高度为$0$。代码如下 ： 12345678910111213inline void ice_barrage(int x,int y,int fx,int s){//toward fx,the strength of the ice barrage. int ans = ...

析合树学习笔记学习析合树 ：step1 ： 爆%机房巨佬Laffeystep剩下的 ： 听Laffey讲课学习笔记结束 参考内容 ： 巨佬Laffey的讲课内容、Laffey的博客、oi_wiki引入问题 ： CF526F 给定一个$n \times n$的棋盘，其中有$n$个棋子，每行每列恰有一个。求有多少个$k \times k$的棋盘中恰好有$k$个棋子。($n \le 3 \times 10^5$) 我们首先把问题抽象化 ： 已知每行每列恰有一个棋子，那么我们可以把原棋盘抽象成一个存储棋子纵坐标的数列，那么 原问题转化为求该数列中值域连续的区间个数。例如原棋盘为 ： \begin{bmatrix} \bigcirc & & & \\ & & \bigcirc & \\ & \bigcirc & & \\ & & & \bigcirc \end{bmatrix}我们就可以把它抽象为数列： 4,2,3,1我们发现既然每行有且只有一个棋子，那么最终的数列应当是1~n的一个排列 那么要求解的也就是这个数列中 ...

让我们从整除开始，这样对吧定义：设 $a,b\in Z,a \neq 0$。如果 $ \exists q \in Z$，使得 $b=aq$ ，那么就说 $b$ 可被 $a$ 整除，记作 $a \mid b$ ，且称 $b$ 是 $a$ 的倍数， $a$ 是 $b$ 的约数（因数）。 $b$ 不被 $a$ 整除记作 $a \nmid b$ 。 性质： $a \mid b \Longleftrightarrow -a \mid b \Longleftrightarrow a \mid -b \Longleftrightarrow |a| \mid |b|$ $a \mid b \space \wedge b \mid c \Longrightarrow a \mid c$ $a \mid b \space \wedge a \mid c \Longleftrightarrow \forall x,y \in Z ,a \mid (xb+yc)$ $a \mid b \wedge b \mid a \Longrightarrow b = \pm a$ 设 $m \neq 0$ ，那么 $a ...

筛法筛法是数学中的重要部分，线性筛是很多问题的开始，而亚线性筛是很多问题的结束所以现在由易到难，逐渐归纳数学中的筛法 一、埃氏筛(埃拉托斯特尼筛法)埃氏筛其实不是线性筛法所以它不配出现在这里，但是为了给亚线性筛打基础，还是得简单提一句 ：埃氏筛的思想简单易懂 ： 从小到大考虑范围内的每一个数，然后把质数的所有倍数都标记成合数，那么最后没有被标记的数就是质数了，下面给出代码 ：1234567891011121314//n为枚举上界，vis[i] == 1表示i为合数，p[]为质数数组，tot为质数个数，下同。void Eratosthenes(int n){ vis[0] = vis[1] = 1; for(int i = 2;i<=n;i++) { if(!vis[i]){ p[++tot] = i; if(i * i <= n) for(int j = i*i;j<=n;j+=i) vis[j] = 1; //小优 ...