Michael_Li的博客

原创 博客搬迁啦

博主的博客已搬迁至https://lnrbhaw.github.io

原创 莫比乌斯反演学习笔记

前言停更好久了，刚好我们老师讲了莫比乌斯反演，那我就来开数论这个天坑吧。莫比乌斯反演比如说我们现在有一个函数f(n)=∑d|ng(d)f(n)=∑d|ng(d)f(n)=\sum_{d|n}g(d) 假设f非常容易求得，但是g很难求，那么我们是不是可以通过f来求g呢 g(n)=∑d|nf(nd)∗μ(d)g(n)=∑d|nf(nd)∗μ(d)g(n)=\sum_{d|n}f(\...

原创 浅谈矩阵乘法的应用

前言矩阵乘法，常常被用作递推式的优化，如果把一个递推式一步的递推转换成乘上一个矩阵，那么由于矩阵乘法有结合律，所以我们就可以快速幂啦，起到优化的效果。而递推式出现最多的地方当然就是dp了，所以今天想简单的总结一下矩阵乘法优化dp。正文博主做的题比较少，见到的这类题也比较少，但有一道题感觉还是比较经典的。 给出一张有向图，问从1号点出发，走过路径长度为T，到达n号点的方案数，其中T...

原创 线性筛质数，线性求欧拉

前言本篇前半部分讲线性筛质数，也叫欧拉筛，后半篇讲解线性求欧拉函数。欧拉筛我们有一种筛质数的办法，就是枚举每个质数，然后把这个质数的倍数都筛掉，这个做法比较简单，在这里不做过多介绍。欧拉筛就是在这个方法的基础上，使得每个合数只会被它最小的那个质因子筛掉，保证了复杂度是线性的 memset(isprime,1,sizeof(isprime)); isprime[...

原创 浅谈虚树

前言先贴一道模板题https://www.luogu.org/problemnew/show/P2495 题意，给你一棵n个点的有边权树，有m次询问，每次询问k个点，要删除一些边使得这k个点均不与1号点联通。 数据范围：2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1； 考虑树形dpLL get_ans(int u){ bool leaf=1

原创 主席树

前言主席树，也叫可持久化线段树，所以他的本质是颗线段树，而可持久化指的是这颗线段树可以访问过去某个时刻线段树上的值，（一会儿还有详细的讲解，不理解一会儿再看）。应用应用的比较多的是查询区间的第k大值（因为其他的数据结构不好做）。实现下面来讲讲如何用主席树实现区间第k大。 这里的主席树是一颗权值线段树，即线段树上的一个点[l,r] [l,r]表示值在[l,r] [l,r]中的数有多少个。 例如：1

原创 笛卡尔树的妙用

前言笛卡尔树，与Treap类似，每个节点拥有两个值，key值和val值。key值是这个节点本身的大小值，在一颗treap中满足二叉查找树的性质，而val值则是一个随机值，学过treap的同学都知道，这个val值是拿来使得树的层高是期望log的，val值满足堆的性质，这里以小根堆为例讲解（当然大根堆不会有任何问题）。应用一般笛卡尔树都被用来建一颗treap，复杂度为O(n)的，n表示插入...

原创 浅谈线性基

线性基

原创 NOIP2018游记

NOIP2018游记前言今天说要写游记，机房的大佬们问我为什么现在才写，估计是因为以前也没写过不知道怎么写，而且今天正式才成绩出来，算是尘埃落定了吧。day-1以前所有的open day都不幸的被关在家里，这次这么好的机会当然要好好利用啦，结果不知是喝了咖啡还是自己过于兴奋，实在是睡不着，凌晨四点才好不容易落入了梦乡，没想到六点钟准时被生物钟叫起，只睡了两个小时，好困啊。。。。day0...

原创 bzoj 3696 化合物 树形dp （附复杂度证明！！！）

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=2318题目大意介于这是一道权限题，先讲一下题意有一棵根节点编号为1的数，给出每一个节点的父亲。对于点对(x,y)，令他们的LCA为k，定义这对点对的A值为dis[x][k])^dis[y][k]，dis即为两点间的最短距离(边数)，最后求出对于x=(1…n)，A值为x的点对的数量...

原创 威尔逊定理

前言好久没更博客了，今天讲一个比较冷门的定理，但在某些题中还是有一定用处的，叫威尔逊定理。主要是比较简单，笔者的垃圾水平能讲的清楚威尔逊定理(p−1)!≡−1(p-1)!\equiv-1(p−1)!≡−1(mod p) 当p是质数时。下面讲一下证明。以下的-1都是在模p意义下的，实际上就是p-1。我们知道1∗1≡11*1\equiv11∗1≡1(mod p),(−1)∗(−1)≡1(...

原创 Miller_Rabin&Pollared_Rho

Miller_Rabin质数判断我们朴素的质数判断算法是枚举小于等于n−−√n\sqrt{n}的数，判断是否都不能整除n，这样的复杂度是n−−√n\sqrt{n}，那么当n的数量级达到1018101810^{18}的时候就不够优越了。这时候我们的Miller_Rubin算法就闪亮登场了。我们的故事从费马小定理讲起，ap−1ap−1a^{p-1}≡1(mod p)，当p为质数的时候。 在费...

原创 bzoj3261 最大异或和 可持久化trie

链接https://www.lydsy.com/JudgeOnline/problem.php?id=3261做法我们先考虑没有修改操作，只有询问的话怎么做，我们记sum[i]表示i的后缀异或和，那么我们每个询问相当于查询区间对一个数x异或后的最大值，那么贪心很明显，位数从高到低，如果有数这个位置上可以和x异或起来是1，那么我肯定不会去选和x异或起来这位上是0的。根据这个性质，我们考虑...

原创 三角函数

特殊角的三角函数sin(16π)=12sin(16π)=12sin(\frac{1}{6}\pi)=\frac{1}{2} sin(13π)=3√2sin(13π)=32sin(\frac{1}{3}\pi)=\frac{\sqrt{3}}{2} cos(16π)=3√2cos(16π)=32cos(\frac{1}{6}\pi)=\frac{\sqrt{3}}{2} cos(13π)=...

原创 只是想谈谈学习kmp中的一点体会

我觉得写出一篇能够看一遍就能理解KMP的博客是很难的，理解这个算法是需要时间和能力的，所以我就不不自量力的去尝试了，所以我就谈一谈我认为kmp学习中比较难理解的点和比较重要的点。建议学习过kmp但还是有疑惑的同学看。 我们看next数组 上一张图片吧，我现在箭头指向的是我现在要求第i为的next值，而0..i-1的next值都求过了。 先看next[i-1] 假设两段红色的相等，然...

原创 bzoj 1483 [HNOI2009]梦幻布丁 线段树合并

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=1483做法网上好多的做法都是链表合并，我感觉有点难写，这里提供一种不一样的思路，线段树合并，复杂度是一样的，都是一个log，但是代码复杂度应该会比较简单。 我们对每个颜色建一棵线段树，线段树每个节点记录三个信息，size，ll，rr，分别表示这个颜色这段区间中的段数，左边是...

原创 bzoj 1212 [HNOI2004]L语言 AC自动机

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=1212做法首先看到多个单词匹配就直接想到AC自动机了啊，然后把AC自动机建出来，做匹配的时候有点不同，以f[i]表示以i结尾的前缀能否匹配，然后我是在每个单词的结尾挂了个vector，表示这个节点结尾的单词长度，用fin[i][j]表示。 那么我们每走到一个节点，把fail...

原创 bzoj 3252 攻略 长链剖分

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=3252做法贪心应该还是比较好像的，每一次走最长的链，然后这条链上点的权值就都为0了，那么我们发现题意转化成为一棵数分成若干条链，然后去前k大的链求加和。 那么这个链是怎么划分的呢，根据这个贪心可以发现，长链剖分一下就好了。 因为长链剖分会找到到叶子的最长的链，然后长链剖分...

原创 bzoj 2561 最小生成树 网络流

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=2561做法做这道题的时候，我想起了以前同学给我讲最小生成树的一个性质，基于kruskal的做法。 当你要加入一条边时，边权小于它的边一定都over了，而且哪些点构成一个联通块是确定了的，注意是小于，不是小于等于。 那么有了这个性质之后，这道题就非常easy了，考虑这条边能...

原创 bzoj 1901: Zju2112 Dynamic Rankings 树状数组套权值线段树

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=1901前言首先不得不说某些博客名称写的是树状数组套主席树的人，实际上写的是树状数组套权值线段树，这种把权值线段树和主席树划等号的人，简直是误人子弟。主席树实际上是可持久化的权值线段树，他的核心思想是现在这个时刻的权值线段树要继承上个时刻的权值线段树，而这道题目中没有用到这种方法，...

原创 BSGS算法

前言这个算法的全名是baby-step-giant-step，用来求解一个数的离散对数，说白了就是求 Ax=BAx=BA^{x}=B (modmodmod ppp)，方程中x解的个数。算法根据费马小定理，我们知道这个x的范围是在1..p-1中的，所以我们暴力枚举的复杂度是O(p)的。 这不够优，令q=sqrt(p)q=sqrt(p)q=sqrt(p)，那么x可以表示为x=q∗k...

原创 CF 895C-Square Subsets

题意简述给你一个有n个元素的可重集(n&amp;lt;=1e5，元素大小&amp;lt;=70)，从这个集合中选出若干元素使得这些元素的积为完全平方数，求方案数mod 1e9+7做法注意到元素非常的小，70以内的质数只有19个，那么我们想到状压dp，f[i][j]表示到第i个数，前面有质因子的集合是j的方案数，转移是O(2182182^{18})，状态是219∗n219∗n2^{19}*n的，会挂掉。...

原创 CF 876E-National Property

题意简述给你n个数字串，刚开始每个数字的优先级为2，你要把某些数字的优先级设为1，然后使得得这些串不降，就是后面一个串要大于等于前面一个串，这个判断大小就是按位比较，先比较优先级，然后比较大小。做法为了方便叙述，我们把优先级为1的叫做大写，优先级为2的叫做小写。 我们把每个串i和他前面一个串i-1比较，找到第一个不相同的位置j，分类讨论一波 1.如果a[i][j]&amp;gt;a[i...

原创 CF 939E-Maximize! (三分法）

题目链接http://codeforces.com/problemset/problem/939/E题意简述现在有一个数列，一开始为空，有两种操作。 1.加入一个数，保证这个数比之前的数都要大 2.在这个数列中选择一个子集S,是的S中的最大元素减掉S的平均值最大，输出这个最大值做法首先，每次加入一个数，有两种可能，一种是最大值不变，第二种是以当前加入的这个数为最大值...

原创 CF 980E-The Number Games

题目链接http://codeforces.com/problemset/problem/980/E题意简述给你n个点，n&amp;amp;amp;lt;=100w，每个点有点权，点权为2i2i2^i，再给你一个整数k，k&amp;amp;amp;lt;=100w，表示你要删除k个点后使得这棵树仍联通且剩余点的权值和最大，输出所有删除的点。 乍一看以为树形dp，突然发现k也小于等于100w，好像不行啊。 我们把题意转换为选择...

原创 [ZJOI2013]k大数查询——整体二分&树套树

题目链接https://www.luogu.org/problemnew/show/P3332前言这道题真的是好题，写了好多遍，本篇博客讲解两种方法，整体二分和线段树套线段树的做法。整体二分如果只有一个询问，那么我们对于这个询问二分一个答案mid，我们判断大于mid的数是否有询问的k个，遍历每一个修改，如果加入的这个数是大于mid的，说明会对这个k有影响，那么我们就用数...

原创 小结树状数组

原创 [CQOI2011]动态逆序对

题目链接https://www.luogu.org/problemnew/show/P3157做法这是一道cdq分治的好题，这道题的前置知识是cdq分治解决三维偏序问题，如果不会这个话请先自行学习。 首先第一个答案很显然就是逆序对的数量，然后后面每次的删除操作，我们考虑把这个被删除的点原先的贡献从答案中拿掉。我们用y表示这个点的数，del表示第几个被删除，若没有被删除则del=m...

原创 [HNOI2010]弹飞绵羊

题目链接https://www.luogu.org/problemnew/show/P3203做法一开始看这道题，我先把它模型转换了一下每个点向它被弹向的那个点连边，如果被弹飞了就向0号店连边，那么我们会得到一个n+1个点（因为还有0号点），n条边的连通图，显然这是一颗树，那么对应的询问操作就是查询到根的距离，对应的修改操作就是把一颗子树移动到另一个节点下面，好了，LCT模板题。 ...

原创 最大全0矩形（悬线法）

前言今天开到一道题，luogu1169棋盘制作，发现自己不会，问了一下同学，告诉我说是普及组题，感觉自己枉为提高组选手。。。 然后学习了一波悬线法。 以l[i][j]l[i][j]l[i][j]表示(i,j)这个点向左走碰到的第一个障碍，r[i][j]r[i][j]r[i][j]表示向右走碰到的第一个障碍。 h[i][j]h[i][j]h[i][j]即所谓的悬线，表示向上走最多能走几步，...

原创 网络流24题——23.家园

题目链接https://www.luogu.org/problemnew/show/P2754家园首先判断无解，把每一艘飞船能到的所有点都并查集并起来，判一下月球和地球是否联通就行了。 和分层图很像，每个新的时刻新建一层，把每艘飞船这个时刻的起点和终点连一条流量为飞船容量的边，每个点从上一层连一条容量为INF的边，然后每次跑一边最大流，如果最大流大于等于k了，表示我所有人都能到了...

原创 网络流24题——22.火星探险问题

题目链接https://www.luogu.org/problemnew/show/P3356火星探险问题这道题和18深海机器人问题基本相同，只要把有障碍物的点的连边全部删掉就行了

原创 网络流24题——21.餐巾计划问题

题目链接https://www.luogu.org/problemnew/show/P1251餐巾计划问题我们把每一天拆成早上和晚上，早上的流表示这天有多少干净的毛巾，晚上的流表示这天有多少脏的毛巾 建边分成6类，用A表示早上，B表示晚上 1.从i.A到T连流量为这一天的需求，费用为0的边，表示我这天需要这么多毛巾 2.从S到i.B连流量为这一天的需求，费用为0的边，表示我这...

原创 网络流24题——20.航空路线问题

题目链接https://www.luogu.org/problemnew/show/P2770航空路线问题我们把模型转换一下，相当于求两条从起点到终点的路径使得这两条路径除了起点和终点没有重复点。一看到一个点只能走一次就想到拆点，把每个点拆成入点和出点，连流量为1，费用为1的边，每条航线连流量为2，费用为0的边，这里一定要流量大于等于2，如果流量为1，那么起点和终点直接相连的话，这...

原创 网络流24题——19.数字梯形问题

题目链接https://www.luogu.org/problemnew/show/P4013数字梯形问题先讲一下这道题的边相交指的是连续两次走到同一个点。 第一问：如果点不想交显然边也不相交，所以我们只要把每个点拆成两个点，中间连流量为1，费用为这给点的贡献的边，S连第一行,最后一行连T，第i行连第i+1行，费用为0，流量为INF，最大费用最大流跑一发就行了。 第二问：每个点...

原创 网络流24题——18.深海机器人问题

题目链接https://www.luogu.org/problemnew/show/P4012#sub深海机器人问题考虑每条边的贡献只能算一次，那我们就连一条流量为1，费用为贡献的边，但是还要保证能走过去，所以再连一条费用为0，流量为INF的边，然后S向每个起点连流量为INF的边，终点向T连流量为INF的边就好了，当然这两种边的费用都是0，最后跑一个最大费用最大流就行了。...

原创 网络流24题——17.运输问题

题目链接https://www.luogu.org/problemnew/show/P4015运输问题S向仓库建容量为库存，费用为0的边，商店向T建容量为需求量，费用为0的边。 仓库向商店建容量为INF，费用为费用的边，跑费用流就行了。比较简单，不解释了。#include&lt;cstdio&gt;#include&lt;algorithm&gt;#include&l...

原创 网络流24题——16.最长k可重线段集问题

题目链接https://www.luogu.org/problemnew/show/P3357#sub最长k可重线段集问题和15非常的像，大家可以先看15再看本篇博客。 这道题就是长度的求法变了，当然这个并不会影响建边方法，还有就是这道题中一条线段可能会与x轴垂直，为了解决这一问题，我们把所有横坐标都∗∗*2，然后左端点++。对于那些垂直x轴的线段，就把左端点++改为左端点–即可...

原创 网络流24题——15.最长k可重区间集问题

题目链接https://www.luogu.org/problemnew/show/P3358最长k可重区间集问题先离散化，要去重，设去完重之后点数为size，每个点向后面一个点连流量为k，费用为0的边，当然，S向1连，size向T连，然后每条线段的左端点向右端点连流量为1，费用为区间大小的边，然后跑最大费用最大流就行了。 我们考虑每个点有两个决策，一个是走到下一个点，表示不取任...

原创 网络流24题——14.最长不下降子序列问题

题目链接https://www.luogu.org/problemnew/show/P2766最长不下降子序列问题第一问我们直接dp，记maxans为最长不下降子序列的长度。 第二问我们跑最大流 因为每个点只能用一次，我们把每个点拆成两个点，入点和出点，所有连入的边连入点，连出的边连出点。入点和出点连流量为1的边。 然后S向每个dp值==1的点连边，流量为1。每个dp值==m...