- 博客(371)
- 收藏
- 关注
RSS订阅
原创 广义圆方树学习笔记 & luogu P4320 道路相遇
背景：补一下坑吧。题目传送门：https://www.luogu.org/problem/P4320题意：一个图，每一次询问两个点的所有路径的交集的大小（对于一条路径，不能走过同样的点）。思路：我真的快想出正解了，但是不会实现。容易发现最后产生贡献的点一定是割点。一开始我的想法是用这个割点来代替点双里的所有的点，后来发现这样的做法极其难以实现，而且会被菊花图卡掉。于...
2019-09-24 15:59:43
297
1
原创 克鲁斯卡尔重构树学习笔记 & luogu P4197 Peaks
背景：下午翘课，因为 要拍视频，懒得去。题目传送门：https://www.luogu.org/problem/P4197题意：nnn个点，mmm条边，有点权，有边权。多组询问，求只经过权值小于等于xxx的边的第kkk大的点的权值。思路：容易想到离线按照询问点权升序，本质就是一棵树（由于已经连通，多余的边是废的），显然有一个主席树+主席树合并的做法，但是考虑到主席树合并...
2019-09-06 15:06:32
235
原创 整体二分学习笔记 & luogu P3834 【模板】可持久化线段树 1（主席树）
背景：有的时候树套树并不好打，所以我们需要一种优秀的做法。题目传送门：https://www.luogu.org/problem/P3834题意：求静态区间第kkk小。思路：想打线段树的请移步。整体二分是什么东西。个人感觉就是二分+分治。考虑离线。二分答案midmidmid。对于当前的区间来说，我们只需要统计小于等于midmidmid的有xxx个，若x≤kx≤k...
2019-08-26 10:31:49
202
原创 斯特林数 & 贝尔数学习笔记
背景：好久没有更blog\text{blog}blog，最近都在准备模拟（水 ）赛。第一类斯特林数：que\text{que}que：现在你有nnn个珠子，每一个珠子的颜色各不相同，求这些珠子组成mmm个项链的方案数。现在求1,2,3,...m1,2,3,...m1,2,3,...m时方案数。sol\text{sol}sol：设Sn,mS_{n,m}Sn,m表示上面的方案数...
2019-08-14 11:41:51
237
原创 二项式反演（广义容斥定理）学习笔记
背景：解锁新姿势。说白了就是之前会的姿势太少了。正题：说白了就是有这样两条恒等的式子：fn=∑i=0n(−1)iCnigi⟺gn=∑i=0n(−1)iCnifif_n=\sum_{i=0}^{n}(-1)^iC_{n}^{i}g_i⟺g_n=\sum_{i=0}^{n}(-1)^iC_{n}^{i}f_ifn=i=0∑n(−1)iCnigi⟺gn=i=0∑n(−1)iCn...
2019-07-16 16:54:29
488
原创 NTT学习笔记 & luogu P4245 【模板】任意模数NTT
背景：NTT\text{NTT}NTT的学习咕了好久，反正有FFT\text{FFT}FFT，知道多项式全家桶的出现。题目传送门：https://www.luogu.org/problemnew/show/P4245正题：想要学习NTT\text{NTT}NTT请看：https://blog.csdn.net/linjiayang2016/article/details/8034...
2019-07-10 10:58:22
319
原创 伯努利数学习笔记 & 51nod 1228 & 51nod 1258
背景：最近做到了一些∑i=1nik\sum_{i=1}^{n}i^k∑i=1nik的题目，学习了伯努利数这种操作。题目传送门：https://www.51nod.com/Challenge/Problem.html#!#problemId=1228题意：多组询问求：∑i=1nik\sum_{i=1}^{n}i^k∑i=1nik。正题：定义BBB表示伯努利数。B0=1...
2019-07-06 15:07:57
278
原创 生成函数——EGF学习笔记
背景：OZY\text{OZY}OZY师兄来diss\text{diss}diss我们了。OGF\text{OGF}OGF学习笔记详见：生成函数——OGF\text{OGF}OGF学习笔记。
2019-07-02 21:28:43
959
原创 生成函数——OGF学习笔记
背景：OZY\text{OZY}OZY师兄来diss\text{diss}diss我们了。正题：一些定义：好像没什么用？级数： 级数是指将一个无穷数列 的项依次用加号连接起来的函数。当n→∞,fn→0n→\infty,f_n→0n→∞,fn→0时，则称级数收敛，否则称计数发散。在级数求和中，最后的结果可能是一个具体数值，也可能是一个函数。幂级数： 形如∑n=0∞an(x−x0)...
2019-07-01 15:47:23
1274
原创 FWT学习笔记& P4717 【模板】快速沃尔什变换
背景：好像要回去备战听说了。雾.........题目传送门：https://www.luogu.org/problemnew/show/P4717正题：我们的FFT\text{FFT}FFT可以解决一类这样的问题：Ci=∑j+k=iAj⋅BkC_i=\sum_{j+k=i}A_j·B_kCi=∑j+k=iAj⋅Bk。有的时候，问题可以变成这样：Ci=∑j⊕k=iAj⋅...
2019-05-06 14:04:13
236
原创 高维前缀和学习笔记
背景：GDSOI\text{GDSOI}GDSOIzsyz\text{zsyz}zsyz全挂，OZYrank16\text{OZYrank16}OZYrank16卡线没进。看了师兄们的游记，发现一些好东西没学。正题：先考虑容斥的做法。一维的做法：for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];二维的做法：for(int i=1;i...
2019-05-05 15:43:39
199
原创 Trie树 & 可持久化Trie树学习笔记 & luoguP4735 最大异或和
背景：原来Trie树我学得是这么烂。Part1Part1Part1：Trie\text{Trie}Trie树字典树：单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。——摘...
2019-04-26 10:59:33
492
原创 数学题集
背景：记录一些好的数学题。理论上持续更。T1T1T1que:que:que:对于一个圆，现在有nnn个点，两两连边（保证不会多线交一个点），求分成的区域块的数目。sol:sol:sol:欧拉定理：在任何一个规则球面地图上，用RRR记区域个数，VVV记顶点个数，EEE记边界个数，则R+V−E=2R+V-E=2R+V−E=2。——摘自《百度百科》因此R=2+E−VR=2+E-...
2019-04-25 09:02:15
242
原创 基尔霍夫矩阵&矩阵树定理学习笔记
背景：好多东西没学。勇士被快船惊天大逆转！！！快船NBNBNB。正题：Part1Part1Part1：对于一个n∗nn*nn∗n的矩阵。设ppp枚举列的全排列，nixudui(p)nixudui(p)nixudui(p)表示排列ppp的逆序对的个数。则其行列式为∑p(−1)nixudui(p)∏i=1ni∗pi\sum_p(-1)^{nixudui(p)}\prod_{i=1}...
2019-04-16 16:00:19
1602
原创 后缀数组整理
1.模板 题目传送门：luogu P3809 【模板】后缀排序 代码：#include<cstdio>#include<cstring>#include<algorithm>using namespace std; char s[1000010]; int rsort[1000010],sa[1000010],rank[10000...
2018-08-17 10:55:56
269
原创 prufer序列
背景：最近在学习数论，好久没有写博客了，今天学习了一种新东西......构造：注意：这是一个迭代的过程，且只剩两个点时结束。每一次找到一个度为1的点（显然是叶子结点），将其删除，将它连出的点加入prufer序列，最后将它连出去的边删除。重复此过程即可。逆构造：即将prufer序列转化为树。（留坑待填）。用处：显然对于不同的树有不同的prufer序列，然后就可以用来将树上的问题转化为组合数学了。...
2018-05-18 14:01:38
362
原创 C++卡常
1.读入优化（*）低阶版：inline int read(){ int x=0,f=1; char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1; for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(c...
2018-04-16 15:43:53
767
原创 CF487E Tourists
背景：越来越困了。题目传送门：https://www.luogu.org/problem/CF487E题意：一个图，支持修改点权，支持查询x,yx,yx,y之间所有不重边路径的最小值。思路：若这个问题在树上就是一道大水题了，直接树剖维护即可。但是这个问题在图上，将图变成树的一种操作是圆方树，不妨考虑圆方树来解决。由于我们知道若有路径经过一个点双，则这个点双对答案的贡献...
2019-09-26 08:40:48
237
原创 luogu P5021 赛道修建
背景：一年前自己还是太菜了。虽然现在也菜。题目传送门：https://www.luogu.org/problem/P5021题意：一棵树，选择mmm条边铺设，要求这些边不能有交集，且不允许掉头（我们认为它是从一点修到另外一点的），现在求这些赛道的最短值的最大值。思路：现在看来还是一个眼题的。二分答案midmidmid。考虑儿子的信息通过当前的边来合并。若当前已经可...
2019-09-24 15:40:37
196
原创 luogu P3533 [POI2012]RAN-Rendezvous
背景：记录一下最近写的一些题目。题目传送门：https://www.luogu.org/problem/P3533思路：题面已经很优秀了。给定一棵内向森林（基环内向森林），多次给定两个点aaa和bbb，求点对(x,y)(x,y)(x,y)满足：1.1.1.从aaa出发走xxx步和从bbb出发走yyy步会到达同一个点；2.2.2.在111的基础上如果有多解，那么要求max(x...
2019-09-24 15:27:08
190
原创 luogu P2155 [SDOI2008]沙拉公主的困惑
背景：写一下最近做的题目。题目传送门：https://www.luogu.org/problem/P2155题意：求[1,n!][1,n!][1,n!]内与m!m!m!互质的数的个数。思路：这个转化还是比较妙的。考虑[1,m!][1,m!][1,m!]内与m!m!m!互质的数的个数，显然答案为ϕ(m!)\phi(m!)ϕ(m!)。考虑(m!,n!](m!,n!](m!...
2019-09-24 15:00:05
179
原创 luogu P3747 [六省联考2017]相逢是问候
背景：写一下这一周集训做的题目吧。其实是切不动题了。题目传送门：https://www.luogu.org/problem/P3747题意：一个序列，两种操作。[1].[1].[1].将aia_iai变为caic^{a_i}cai；[2].[2].[2].求∑i=lraimod p\sum_{i=l}^{r}a_i\mod p∑i=lraimodp。思路：...
2019-09-24 14:30:58
236
原创 luogu P3934 Nephren Ruq Insania
题意：luogu\text{luogu}luogu的智能推荐是个好东西。题目传送门：https://www.luogu.org/problem/P3934思路：弱化版题目详见：CF906D Power Tower\text{CF906D Power Tower}CF906D Power Tower。我们发现这道题只需要满足区间修改单点查询...
2019-09-10 17:13:01
244
原创 CF906D Power Tower
背景：luogu\text{luogu}luogu的智能推荐真的是用来水积分的。题目传送门：https://www.luogu.org/problem/CF906D题意：一个序列，多足询问求alal+1al+2...ara_l^{a_{l+1}^{a_{l+2}...^{a_{r}}}}alal+1al+2...ar。这种式子是从上往下计算的。思路：这种东西离不...
2019-09-10 17:00:22
272
原创 CF17D Notepad
背景：话说luogu\text{luogu}luogu的推荐题目真是一个好东西。题目传送门：https://www.luogu.org/problem/CF17D题意：一个本子，往上面写全部的长度为nnn的bbb进制数字，每一页可以写ccc个。要求所有数字必须严格不含前导000。求最后一页上有多少个数字。思路：考虑第一位不能为000，只能有b−1b-1b−1（[1,b−1...
2019-09-10 16:46:40
265
原创 luogu P4139 上帝与集合的正确用法
背景：水博客系列。题目传送门：https://www.luogu.org/problem/P4139题意：求222222..,mod  p2^{2^{2^{2^{2^2..,}}}}\mod p222222..,modp。思路：遇到这种指数特别大的东西，我们就到考虑欧拉降幂。你从下面的222开始搜索，由于指数是无穷...
2019-09-10 16:29:11
136
原创 luogu P5091 【模板】欧拉定理
背景：竞赛课，用来补坑吧。题目传送门：https://www.luogu.org/problem/P5091题意：求abmod  pa^b\mod pabmodp。其中b≤1020000000b≤10^{20000000}b≤1020000000。思路：扩展欧拉定理：ab={ab,b<ϕpabmod...
2019-09-10 16:17:49
217
原创 luogu P4768 [NOI2018]归程
背景：今天真得好累。题目传送门：https://www.luogu.org/problem/P4768题意：nnn个点，mmm条边，有边权，一个表示长度，一个表示高度。多组询问，每组询问问从xxx点出发，当前的积水高度是yyy，可以开车经过边的高度...
2019-09-08 19:41:25
266
原创 luogu P3535 [POI2012]TOU-Tour de Byteotia
背景：第一道难度暂无评定的题。第三个通过的。题目传送门：https://www.luogu.org/problem/P3535题意：nnn个点，mmm条边，删掉最少的边的数目，使得编号小于等于kkk的点都不在环上。思路：容易想到若边(x,y)(x,y)(x,y)满足x,y>kx,y>kx,y>k，则这条边是不用理的，暴力加到并查集中即可...
2019-09-06 10:26:40
226
原创 luogu P4449 于神之怒加强版
∑i=1n∑j=1mgcd(i,j)k\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)^ki=1∑nj=1∑mgcd(i,j)k=∑d=1min(n,m)∑i=1n∑j=1mdk[gcd(i,j)=d]=\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{n}\sum_{j=1}^{m}d^k[\gcd(i,j)=d]=d=1∑min(n,m)...
2019-09-05 14:05:46
178
原创 luogu P1891 疯狂LCM
∑i=1nlcm(i,n)\sum_{i=1}^{n}\text{lcm}(i,n)i=1∑nlcm(i,n)=∑i=1nn⋅igcd(i,n)=\sum_{i=1}^{n}\frac{n\cdot i}{\gcd(i,n)}=i=1∑ngcd(i,n)n⋅i=n∑k=1n∑i=1nik[gcd(i,n)=k]=n\sum_{k=1}^{n}\sum_{i=1}^{n}\frac{i...
2019-09-03 14:00:09
183
原创 luogu P1552 [APIO2012]派遣
背景：由于昨天午饭后去睡觉了，因此博客只补了一篇。题目传送门：https://www.luogu.org/problem/P1552题意：nnn个人，关系网为一棵树，每一个人有薪水和领导力。现在若编号为xxx的人做管理者，那么所有它和它所有的儿子节点都可被雇佣（也可不被雇佣），雇佣是要花钱的。编号xxx的满意度为雇佣的人员的数量∗*∗xxx的领导力。现在你有mmm元钱，问你能...
2019-09-02 13:44:27
121
原创 luogu P3261 [JLOI2015]城池攻占
背景：补坑ing...\text{ing...}ing...题目传送门：https://www.luogu.org/problem/P3261题意：城池数为nnn的树，有mmm个骑士，每一个骑士会往根111走，每一次经过一个城池，若大于城池生命值会占领，且战斗力变化；否则战死于该城池。求每个骑士攻占的城池的数量以及每个城池抵挡的骑士的数量。思路：考虑骑士只会战死一次。因...
2019-09-02 13:29:50
163
原创 luogu P1456 Monkey King
背景：正式的高中生了。开学了，很不愉快。由于是竞赛生，因此我们在教室里的位置置底了。题目传送门：https://www.luogu.org/problem/P1456题意：nnn只猴子，每一次两只猴子打架，是两个部落中战斗力最高的两只打架，打架后战斗力减半，合成一个部落，求每一次打完架后合并成的部落的战斗力最高的猴子的战斗力。思路：这显然是左偏树的模板。直接维护大跟...
2019-09-02 13:17:55
177
原创 luogu P2714 四元组统计
背景：开始补坑。题目传送门：https://www.luogu.org/problem/P2714题意：给一个序列，求满足gcd(ai,aj,ak,al)=1\gcd(a_i,a_j,a_k,a_l)=1gcd(ai,aj,ak,al)=1的四元组(i,j,k,l)(i,j,k,l)(i,j,k,l)的个数。思路：你预处理出totxtot_xtotx，即xxx...
2019-09-01 11:40:18
326
原创 luogu P4108 [HEOI2015]公约数数列
背景：剩下的博客有空再补。题目传送门：https://www.luogu.org/problem/P4108题意：一个序列，两种操作。[1].[1].[1].将第xxx位置的值改为yyy；[2].[2].[2].询问gcd(a1,a2,a3...,ap)∗xor(a1,a2,a3,...,ap)=x\gcd(a_1,a_2,a_3...,a_p)*\text{xor}(a_...
2019-08-31 17:03:36
155
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人