LWLAymh的备忘录

随机化算法 基本分析 Union Bound 即: ,取等当且仅当所有 互斥. Markov 不等式 若 ,则 . Example(Max Cut算法) 一个无向无权图,将点集划分成两个部分,使得跨越这两部分的边尽可能多. 直接随机划分,容易见到每条边有 的概率是割边,因此期望自…

本文除特殊说明,所涉及数均为整数. 整除性及相关 如果 且 是一个整数,我们就说 整除 ,记作 . 能同时整除两个数 和 的数称为 和 的公因子,所有公因子中最大的那个称为最大公因子,记作 .而最小的能同时被 和 整除的非零数被称为他们的最小公倍数,记作 .不难发现 . 欧几里得…

2024寒假学堂(部分) Problem4 设 ,求 . Solution4 考虑求出 .直接取三次单位根 ,自然有 ,所以 . 所以答案显然是 . Problem10 等差数列中, ,公差 ,求最大的正整数 ,使得 . Solution10 显然 . Problem11 全为整…

反演 假设有两个函数 和 满足: ,已知f求g的过程称为反演. 一般情况下,求反演只能高斯消元,但是有一些形式的反演有巧妙解法. 子集反演 一般形式: 证明: 不难发现,这个子集反演也就相当于在做高维前后缀和. Example1(2019zrpzt七连day1D) 根据子集反演,…

KMP Example1(zr23省选第一轮集训day5b) 必须提一下的是,能用KMP的前提是可以比较两个字符串是否相等,不一定是比较两个字母相等.只要能比较两个字符串是否相等,并且已知 能快速判断是否有 ,那么就可以使用KMP.并不要求 并且 才有 . 因此,我们取 的置换 …

反悔贪心 扫描线 第一题 https://www.luogu.com.cn/problem/P6940 首先发现,从上往下扫行,然后对于每个右下角匹配一个列最近的左上角是最优秀的.所以拿set维护上述过程. 第二题 https://www.luogu.com.cn/problem…

本质相同 Example1 对于所有满足以下条件的长度为 的序列 ,我们称它是好的: 对于每一个数 ,求它在每个好的序列中出现的次数的平方和.其中 ,任意模数. 首先注意到可以枚举每个数 出现的次数,这样就转化为对满足某些位置是 的好的序列计数. 对于一个没有限制的好的序列,设 …

OI中的线性代数 线性基 Example1 给定 个非平方因子数 ,求有多少种选取一个子集的方式满足每个质因子都在子集中恰好出现偶数次. . 考虑将每个数的质因子压成一个二进制数,那所求也就是问有多少种选取子集的方式使得子集内二进制数异或和为 .自然想到线性基. 的自由变量的数量…

动态规划的设计 分析状态 Example1 给定一个序列,初始为空,进行多次操作,每次在序列末尾等概率加入一个 中的数字,然后进行以下判断: 1. 如果当前序列末尾两个数字相同且小于 ,假设都是 ,那就将它们都删去,加入一个 . 2. 如果当前序列没有可以删的数字,并且序列长度为…