Deep_Kevin的娱乐空间

算法大纲组合数学11

powerful number指的就是每一种质因子的指数都≥2\geq2≥2的数。powerful number一定能被表示为a2b3a^2b^3a2b3的形式，当指数为偶数的情况下可以放到前面，当指数为奇数的时候可以拆一个3出来，然后把剩下的放到前面去。这样就可以得知1到n的powerful number的个数为∑i=1n(ni)13\sum_{i=1}^{\sqrt n} (\frac n i)^{\frac 1 3}∑i=1n​​(in​)31​，积一下分就可以知道是O(n)O(\sqrt n)O

正题Portal这种思想值得学习！我们知道最小割会将集合分为两部分S集和T集。考虑随意选出两个点A,BA,BA,B，显然在一个最小割中这两个点要么在同一个集合，要么不在同一个集合。在同一个集合十分好做：我们只需要将这两个点合并起来看作一个点考虑就可以了（边加权合并），因为可以简单分析得到，对于任意的一个点CCC，要么与A,BA,BA,B在同一个集合，要么不在同一个集合。如果我们知道不在同一个集合怎么做，我们就可以每次选两个点出来求一遍答案，然后合并（即考虑在同一个集合的答案），然后求所有这样答案

正题Portal可以得到这个定理：用一组最小割将S集和T集分开，则S集的一个点到T集的一个点的最小割权值都等于这个最小割权值。具体证明大概是考虑三个点之间的割：设三个点a,b,ca,b,ca,b,c若割(a,b)(a,b)(a,b)后，ccc在a集，那么存在割(a,b)≥(a,b)\geq(a,b)≥割(c,b)(c,b)(c,b)很好证明，因为ccc最多走回aaa之后然后再开始割，这样得出来的割一定不会比原来大，如果ccc在bbb集是相同的，因为这个定理对于任三点都适用，所以可以得到割(a,b)

正题很快啊。这道题就是模板题了。最小树形图指的是一个图(V,E)(V,E)(V,E)，满足其为弱连通图且存在一个点没有入边，其他点恰好一条入边的有向图，也就是一个有向外向树的形式。算法流程是这样的：1.找出最小边集。由于在这个图中，除了根节点外每一个点都有且仅有一个入度，所以我们可以从这里入手。因此找出每一个点的入边中权值最小的边mmin[i]，同时如果存在一个除了根节点以外的点没有入边，则可判定为无解2.判断是否有环。怎么判有环可以直接看代码，如果没有环而且没有缩点，那么直接返回就好了。如果有

正题 如果想要严格证明,请到这里,这里只是用来背结论和性质的. 弦图:每个大小>=4的环都必有一条不连接相邻点的边,注意辨析,只有三元环的图不一定是弦图,像一个六边形,中间有一个点,这个点连向所有六边形上的点,由于外部的六边形形成了一个环,但是没有一条不连接相邻点的边,所以这个图不是弦图. 团:完全图 诱导子图:点集是原图的点集的子集,边集是是原图边集的子集且满足两端点在点集内. 弦图的诱导子图是弦图 单纯...

正题 证明啥的都不用管,这篇Blog里面的记住就行了. 首先LGV引理只在DAG上有效. 对于一条路径,我们定义它的权值为路径S上边权之积记为 现在有k个起点,k个终点,对于一对起终点,我们定义,S是起终点的任意一条路径. 我们将放进一个k*k的矩阵当中,第i行第j列为. 我们对这个矩阵求行列式,就有: 前面的P枚举的是一个排列,指的是逆序对个数,后面的prod枚举的是每一组从的路径Q,这些路径要满足互不相交,...

正题 以前口胡了好多发的动态点分值,写起来的时候才知道有多恶心. 其实很多动态点分治的题都很板子,但是都很难写,因为要将自己的信息传给儿子,对于每个点要维护自己的信息和子树在父亲中的信息. 动态点分治实际上就是把点分治的那棵分治树保存下来,在题目不改变树的形态的情况下,可以通过对于每一个点维护一个数据结构来满足将点分治可以做的事情动态化,每次带个log.(分治树最大高度log 像这题:【模板】点分树 | 震波 对于每一个点,我们就用线段树...

正题 最小斯坦纳树问题是由斯坦纳提出来的,并被后人推广的一类问题. 问题原先提出时是这样的:有三个点,希望找到一个点,满足这个点到这三个点的路径长度和最小,感兴趣的可以找找来看解法和证明,已被推广到k个点了. OI中的最小斯坦纳树问题是给出一张无向联通图,有k个关键点,每条边有边权,现在要求出一种边集的方案满足将k个点联通. 具体可以参考洛谷的模板题 可以使用状压Dp来解决这个问题,令表示i这个点,联通S集合的关键点的最小代价....

正题 不能再半途而废了。 让我们现在开始讲一下Matirx-Tree定理。 其实这个定理是用来解决关于“用图建树的方案树”之类的问题的。 首先我们要了解几个定理及其证明。 1.我们定义一个n*n的矩阵A，它的行列式为 p是1到n的一个排列，laowang(p)指的是其中的逆序对个数。其实就是排列一个...

正题 由于回文自动机的代码十分的有趣,以至于半天都没看懂怎么实现. 为了解决广大苦困人民的烦恼,我决定写一篇针对代码的讲解 首先回文自动机有两个根,一个是偶根,一个是奇根. 偶根的长度为0,奇根的长度为-1. 为什么要这样设置?讲完前面部分再说 首先长度表示的是当前点所对应的回文串长度,从偶根或奇根往下遍历时,在两边同时加上转移边对应的字符,这样会使回文串长度+2,当从奇根往下遍历的时候,可以发现第一步其实只将长度变为了1(...

正题 以前一直都一直在凭感觉做概率期望，直到我遇到了这一公式题：排名估算 如果做不出来的话就让我们一起学习吧！ 如果做得出来给您跪了！ 首先了解几个符号： 表示A发生的机率。 B发生下A发生的概率 AB同时发生的概率。 你可能觉得这些东西并没有什么用，下面让百度说一个例子：...

正题 翻译过来就是 k维的树，很显然就可以看出它是一个高维数据结构。 因为它高维，所以它的局限性就比线段树要小很多。 一般可以做k维空间的信息，比如三维最近点对，之类的。 它使用一个二叉搜索树来维护的，每一维排序的关键字是循环的，比如说第一层按照第一维来排，第二层按照第二维来拍，...，第k层按照第k维来排，第(k+1)层按照第1维来排。...

正题 学过FFT的都知道单位根有一个这样的性质： 那么我们就可以解决这样的东西： 怎么解决呢？我们枚举一个j： 我们构造一个多项式 你会发现一个奇妙的事情： 如果我们要求，把它往上推发现第一条式子变成了 那么原来的式子就变成了。 好的这个式子就是k^2的，因为f可以快速算...

正题 先放一篇很好的LCT总结：https://www.cnblogs.com/flashhu/p/8324551.html 看这个就够了，讲得非常好，在这里我就不多说了。 说几个要点，学会可以帮助更好的理解LCT： 1.若给出的是一棵有根树，那么就不能makeroot这种操作。 2.其次，若要找两个点的lca，我们可以acce...

正题 原根相关 定义 群：非空集合 G 上定义了一种二元运算，满足封闭性、结合 律、单位元、逆元。 环：非空集合 R 上定义了加法和乘法，在加法下构成交换 群，满足乘法结合律、分配律。 域：非零元素都可逆的满足交换律的环。（也就是交换幺环） 循环群：指群可以由一个元素生成：G = x,x2,x3...。...

正题 菜就是菜。 其实真的不怎么喜欢字符串。 后缀自动机可以想象成一个函数，当一个串的后缀自动机建好的时候，你把这个串的一个后缀丢进去，他就会返回True，否则就会返回False。 先讲一些概念。状态State 把这个串的每一个子串p提出来，一个子串可能在这个串里面出现了很多次，设出现位置的右端点集合。 对于同...

正题 博弈论是信息学里面一个不常考的内容，一般以考了做不出而著称。在这里我们聊一聊。 我们以一个例题来引入：nim游戏。 为什么答案是石子的异或和是否为0？ sg[x]表示x的博弈状态，它一般的转移方式是：，其中y是x的后继状态，mex操作是找一个集合中第一个出现的非负整数。 首先一堆石子。x的后继状态就是，一开始我们设，表示0...

正题 今天碰到了一个很恶心的斐波那契数列的题，现在来讲讲斐波那契数列的性质。 递推式 通项公式 证明不会 矩阵转移 对于一个可以线性转移的式子，加入要求第n项，普通方法的时间复杂度是，k是线性转移单次代价。 我们可以用矩阵做到。 比如说斐波那契矩阵就是。...

正题 玩轮廓线Dp很久了。现在来好好玩玩插头Dp。 首先：插头Dp又称为连通性状态压缩动态规划。 我们以一道例题来引入今天的主题：Formula 1Ural1519, Timus Top Coders : Third Challenge 题意是这样子的：你一个m * n的棋盘，有的格子是障碍，问共有多少条回路使得经过每个非障碍格子恰好一次．...

引子 这里的东西很杂，只供复习，感兴趣的朋友也可以看一下。正题线性求逆元 然后循环过一遍就可以了，如果一时间证不出来，可以先处理阶乘和阶乘的逆元，然后通过来得出答案。卢卡斯定理的证明 先考虑一个这样的东西：。 那么。 两边的x的次幂项的系数相等，考虑在左边的的系数，只可能被右边的两项的...

正题 注意本文有些时候对[]的定义不太准确，有时候指的是向下取整，有时候指的是判断符号，当然看一看里面有没有<,>,<=,>=...就可以区分，不太严谨，望周知。 现在我们要解决这样一个问题： 我们考虑当的时候，应该怎么做。 很明显直接把它拆开来： 那么我们就得到了一条式子。...

正题 来自whzzt的定义，对于我来说，还是太难了。简单的素数判定方法 首先是两个简单的素数判定方法：。 Lucas-prp判定方法在网上很难找到证明，我们在这里只说一下Miller-Rabin素数判定方法。 它是根据一个东西来判定的：对于一个质数p，必定有。 而根据费马小定理，我们知道，所以我们找一个任意正整数a，然后求它...

正题 听说这个东西是最近几年，某个大佬Min_25提出的，帮助我们解决了许多积性函数前缀和问题。 为了方便，我们以loj6053:简单的函数一题来讲一讲什么是Min_25筛。 首先，正如开头所提到的，Min_25筛是用来解决积性函数前缀和问题的。而且，根据我的了解，这个积性函数要满足下面几个性质：1.对于一个质数，一定要是关于p的一个多项式；2.对于一个质...

正题 以前讲的东西并不是没有道理，但是如果要更严格地讨论生成函数，我们就要学习他的定义。 普通生成函数： 指数生成函数： 指数生成函数就是普通生成函数多了一个。 这个暂时先记下来，后面再讲有什么用。 先讲讲组合数卷积 如果题目给出两个多项式，要你求他们的组合数卷积，什么意思呢？ 也就是给...

正题 我们学会了快速傅立叶变换，狄利克雷卷积，现在我们来解决一下快速沃尔什变换。 它主要是解决这样的问题的：。 也就是说 其中那个你看不懂的符号指的是三则运算的其中一种：or,and,xor。 怎么做? 我们来模仿一下解决多项式乘法的过程，我们先是把原数组做一次傅立叶变换，然后再相乘，最后再做一次逆变换。 ...

正题 下述的所有例题可在洛谷上搜索“多项式”，找到。 Contents:快速傅里叶变换 NTT 多项式求逆 多项式取模 多项式ln 多项式exp 多项式多点求值 多项式快速插值 普通多项式转下降幂多项式 下降幂多项式转普通多项式 写代码时要注意的快速傅里叶变换 可以到我的blog学习，尽管写得不太好。NTT 可...

正题 解决问题：for(int i=0;i<n;i++) for(int j=0;j<n;j++) h[i+j]+=f[i]*g[j]; 前置知识 定义，其中i为负数单位。 在这里我们假设z是一个复数，也就是说 ，Re为实部，Lm为虚部。 加减法就是对应相加减：也就是说 但是乘法...

正题 当我们要求一个这样的东西的时候，我们就会很困惑。 或者。 通常这个n还很大，以至于你无法线性筛得到。 这时候我们就要用杜教筛来解决问题了。 记。 因为我们知道，也就是。（这条式子的证明看数论函数的介绍） 所以可以得到两条式子。 ，至于第一个等号，解释是，对于一个i要产生贡献，必定是...

正题      这节学习笔记我们来研究一下数学。数论       先介绍两个狭义上的集合：，前者表示的是完全剩余系，也就是，而后者表示的是简化生育系，也就是保留下来那些与n互质的数。比如说：      接着我们记为内与n互质的数。显然    逆元       若，那么我们称a为x在模n意义下的逆元。      可以证明x在模n意义下有逆元，当且仅当（互质）。    ...

正题      这节的东西理解起来可能有点难，但是相信这篇博客能够帮到你们。      首先，我们要发现一般图和二分图的区别。      很容易就可以知道，当增广路不存在环的时候，和二分图是没有任何差异的。      我们可以直接用一个没有匹配的点去找点，如果找到的点匹配过，我们就把他们的匹配点放入队列，然后知道找到一个未匹配点，再从头到尾更新增广路。       但是假如有环...

正题      我们今天讲一下线性规划，以这一道题为例：#179. 线性规划      首先面对一堆小于等于的约束，我们应该怎么做？      我们以样例来解释：      有四条约束，要同时满足：      同时，我们要使得最大。      首先，我们可以把可行解在一个二维平面上表示出来。      如图，可行解就是蓝色部分，我们要使得最大，那么我们就用一条的直线...

正题      平时我们用的都是Dinic算法，每次bfs之后，我们习惯用dfs来找增广路。时间复杂度是。而且有时候很接近上界。       ISAP给这个Dinic算法带来了许多优化：    第一个       I表示的是improved，也就是说我们不用bfs那么多遍，我们可以通过每一次修改分层图的标号h来达到这个目的，怎么修改呢？       考虑一个点一开始可以到达的点...

正题 这个zkw大神非常6，把两种很显然的网络流算法结合了起来。 zkw费用流=EK费用流+Dinic最大流 对，你没有看错。 我们回忆一下Dinic找增广路的过程，是不是一遇到一条可以走的边就走，走出来一条源点到汇点的一条可行的路径，就可以了。 我们再回忆一下EK费用流的过程，是不是先跑SPFA，使其找出一条流量不为...

正题 因为NOIP2018考了这一个东西，所以不得不学。 我们以这一题为例题来引入今天的学习：【模板】动态dp 我们显然可以用树形Dp去做，倒不如我们先把方程列出来。 这两条公式挺显然的吧。 假设我们现在无聊，往树链剖分的角度去考虑。 那么我们设一个数组g，表示的是从非重儿子转移来的状态，跟f数组的...

正题 我又来划水了。 2-SAT问题是类似于这样的形式： 给出n个数，m组条件，问你这m组条件是否能同时满足。 每组条件类似于这样的形式 怎么做？ 我们可以拆点！ 把每个点拆成两个点，一个表示选，一个表示不选。 那么假如有一个这样一个条件： 考虑x取1时，y必须取0；y取1...

正题      听说NOIP要考，所以临时补了一下，多了一种思考方式。      AC自动机是基于KMP和字典树的，要想透彻了解AC自动机，最好先学KMP和字典树。      那么，AC自动机是什么样子的呢？又是用来解决什么问题的呢？      【模板】AC自动机（简单版），可以以这题为例。      好像KMP是可以做的，试一下，发现时间复杂度会爆炸，因为文本串要遍历次。...

正题      这真是一个神奇的东西。      既然有这个算法，那么就一定有他能解决的题目。      我们以这一题为例：[POI2015]PUS。      给出n个数，m个操作，每次规定l到r中的k个数比这个区间的其他数大，询问是否有解。      简化问题，给出n个数，m个操作，每次规定第a个数比第b个数大。（还规定一些数的值      那么很明显是一个差分约束的问...

正题      Meet in the Middle，折半搜索。      用来解决一些普通搜索过不了的，但是支持合并的题目。      以这一题为例：[CEOI2015 Day2]世界冰球锦标赛      这题说的是什么呢。      集合满足元素之和小于m，求集合种数。      n才40，让我们来暴力。      发现不行，因为枚举种数为。      我们先把...

正题      好像大部分都是01分数规划？      它是解决这样的问题的，求      怎么做？      好像很麻烦。      我们来二分一个数k，      然后让这堆东西小于等于k，就变成了这个样子      所以，贪心取的就行了。      好像把简单的问题复杂化了。      其实每次我们就是判断是否有，也就是说，我们判断的是 是否有。 ...