- 博客(294)
- 收藏
- 关注
RSS订阅
原创 数学小结（持续更新）
数学小结前言：这篇文章专门整理了各种有关数学的东西（包括原理和例题），主要是怕自己忘了。整理的不齐全，而且写的都是比较基础的东西。扩展欧几里得（exgcd）问方程 ax+by=cax+by=cax+by=c 的 xxx 的最小非负整数解。根据贝祖定理，若 gcd(a,b)∣c\gcd(a,b)|cgcd(a,b)∣c，则方程有解，否则无解。那么我们先可以求出 ax+by=gcd(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b) 的一组解，然后 xxx、yyy 同时乘上 cg
2020-11-06 08:07:32
532
1
原创 字符串小结（持续更新）
只是给忘记模板时的我看的AC自动机大概流程：对所有模式串建出 TrieTrieTrie 树。failfailfail 指针的定义：设 iii 节点所代表的字符串为 SSS，则 failifail_ifaili 表示 SSS 的所有后缀里面，在 TrieTrieTrie 树中出现过的最长的那个串所代表的节点。询问举例：请你分别求出每个模式串 TiT_iTi 在文本串 SSS 中出现的次数。方法：首先先建立 failfailfail 树（faili→ifail_i \to ifaili→i），
2020-05-14 13:06:56
180
原创 【CF1286F】Harry The Potter（折半，子集卷积）
发现图中不可能出现环，否则我们将这个环删掉，并用等同次数的一操作即可与环上原操作做到等价。种子集和并排序好（这里排序能边求边做），然后再双指针扫一下，时间复杂度。不交且它们都能被表示出来，直接 DP 是。只有可能取它自己，而另一端有可能取。有没有可能形成一条树而全部消掉。次幂的子集卷积，看是否有一位为。然后原问题相当于要选尽量多的。首先若用了第二种操作，就在。，然后折半，两半分别求出。用倍增而非二分即可做到。考虑从下往上推，叶子。
2022-10-28 18:36:50
393
原创 【AGC035E】Develop（图论，DP）
容易证明，按照上述方式，若找不到任何一个环，那么图中就确实不存在环（因为从我们所述的。是偶数，那么这两条链是不连通的（独立的），而无环相当于要求每条链中不连续选。个点，这个方案数很好统计（注意数据范围不大，暴力 DP 即可）。首先，若出现了环，那么一定经过了正偶数条。的边，它们形成了两条链，分别称为奇链和偶链。中的某一个点，这就与该环是简单环矛盾了。如上图左下，图中的红蓝两条路径就是从两个不同的。中的导出子图不能出现环，且该环恰经过两次。中的导出子图是个 DAG，即无环。接着，如上图右，我们又继续考虑。
2022-10-20 16:19:35
397
原创 【CF1396E】Distance Matching（构造）
而且注意到，只要我们每次都从当前根的子树大小最大的那个子树内选，树的重心就一直不会变，那么。题解是归纳地构造：考虑每次找到 lca 深度最大的两个点，把它们匹配，并把它们从树中删除（删除它们后树肯定仍然连通），直到再匹配就要使得当前的。类似地我们有另一种方法：考虑每次选择两个 lca 为根的叶子，把它们匹配，并把它们从树中删除，直到再匹配就要使当前。取到上界时，任意两组匹配对应的路径都有交，可以推出所有匹配对应的路径都有交，然后得到这个交点就是重心。的上下界，这是一个很经典的问题，可以考虑每条边。
2022-10-17 10:09:45
148
原创 【CFgym102482D】Gem Island（生成函数）
题意：有一个序列 a1,⋯ ,ana_1,\cdots,a_na1,⋯,an，初始时它们全为 111。进行 ddd 轮操作：每轮操作以正比于 aaa 的概率选择一个 aia_iai 加 111。求最后 a1,⋯ ,ana_1,\cdots,a_na1,⋯,an 中前 rrr 大的和的期望，精度要求 10−610^{-6}10−6。n,d,r≤500n,d,r\leq 500n,d,r≤500。题解：即为求：1n(n+1)⋯(n+d−1)∑a1+⋯+an=d(da1,⋯ ,an)∏i=1n(ai!
2022-10-12 20:15:31
192
原创 【PE806】Nim on Towers of Hanoi（汉诺塔游戏，生成函数）
每次操作可以把套在某根柱子上的最上面的那个圆盘移到另一个柱子上。这个生成函数和一般的生成函数不太一样，因为它涉及到下标的位置交换，即维度与维度之间的交换。那么仅靠这一条方程是不够的，我们要把其他对称的方程都写出来。的基础上变得更少），而显然这个步数下界是可以达到的（忽略第。个圆盘仍按从上往下半径递增的顺序，全部套在第三根柱子上。汉诺塔游戏是如下的问题：有三根柱子，第一根柱子套有。个盘子全部移到第二根柱子，这个过程的步数下界是。个盘子的位置，若它在第一根柱子上，那么方案数为。是当前三根柱子上的盘子个数，若。
2022-09-29 14:42:16
883
原创 【XSY4746】会议选址（三度化，边分治，点分治）
这种关键点的重心问题，一般有两种思路。一种是合并：对于两个不交的点集 S,TS,TS,T，S∪TS\cup TS∪T 的重心必在 S,TS,TS,T 重心间的路径上，二分即可，需要数据结构支持 dfn 区间内 S∪TS\cup TS∪T 内的点的个数。使用该做法能将本题做到 O(nlog3n+qlogn)O(n\log^3n+q\log n)O(nlog3n+qlogn)。另一种想法是，对于单次询问点集 SSS，先从任意一个点开始，考虑往当前最大的子树走，直到最大的子树大小小于等于 S/2S/2S/2。
2022-09-29 09:40:43
575
原创 【P8179】【EZEC-11】Tyres（背包问题，决策单调性，分治）
那么考虑将所有商品分为两部分：第一部分是每家商店的前。家商店，如果想要购买该家商店的商品，需要出。，可以考虑使用决策单调性优化 DP 做到。个商品之后的任意商品的价格一定比前。个商品，第二部分是剩下的商品。个商品中任意商品的价格都高。的题面很像，但是做法不同。件商品购买所需的代价为。件商品所需的最小总代价。
2022-09-26 21:41:29
264
原创 【CF1693C】Keshi in Search of AmShZ（类dijkstra）
然后可以注意到，在最优策略下，我们肯定不会走回重复的点：否则意味着出现了一个环，那么我们还是需要将这个环上的某条边删掉（否则最坏情况就是绕着环一直走），那么不如第一次走到的时候就删掉。这意味着，我们删除某条边不会带来后效性，换言之最优策略中我只关心当前点在哪，并不关心我之前删了哪些边（因为我不可能走到一个重复的点）。的排位有关，但 dijkstra 过程中这个东西我们已经求出来了，所以它不将带来什么影响。是已经确定了的），然后对于每个出点。时，按最优策略走，最坏情况下到。都已经求出来了，那么对于任意。
2022-09-20 07:19:36
188
原创 【LGR114C】地地铁铁
借着这个机会，系统总结一下几个点双的基本性质。注意点双的定义是：删掉任意一个点后原图仍连通。之间存在一条简单路径（点不重），使得这条简单路径既经过。具体地，对于原图上一条边。否则，根据引理 3，存在一条简单路径。只有一个交错点，容易证明该交错点是割点，矛盾。，根据点双的定义，这三条路径都是可以取得到的。中只有两个点的情况那么证明显然，所以不妨设。路）的点对数量，称这种点对为 “合法点对”。是非平凡的），存在一条简单路径依次经过。看回这题，考虑将原图缩成点双，那么若。于是，我们证明了，某个非平凡点双。
2022-09-17 20:16:17
296
原创 【???】???
相当于左边每个点能匹配右边一个区间的二分图匹配问题，贪心即可做到。一定是若干段两两不交的区间构成，加上一个新的不交的区间。的所有区间加入一个堆中，堆顶是。：从小到大枚举右边的所有点。的那些区间，它们肯定都在。个球，并且可以往编号在。同样用线段树实现，一个。，那么最多能放多少个球。的做法，但暂时没搞懂。
2022-09-14 21:28:54
156
原创 【小记】SG函数
规定游戏如下：给定初始局面，两个人轮流操作，每次使当前局面走到某一个后继局面（局面后继关系图给定，且是 DAG），若没有后继局面则失败（将没有后继局面的局面称为直接必败局面）。个子游戏中的某一个的局面替换为其后继局面” 所形成的所有可能的后继局面。个子游戏构成的，当且仅当：对于该游戏的任意局面，可以将其看成是。我们现在来证明，一个局面是先手必胜的，当且仅当它的。个子游戏构成的，我们可以直接令其每个局面的。个子游戏构成的游戏，其每个局面的。值为其所有子游戏对应的局面的。值为所有子游戏对应的局面的。
2022-09-07 09:36:54
564
原创 【XSY4378】vanity（生成函数，拉格朗日反演）
并没有简洁的写法，但实际上我们可以通过牛顿迭代解出。牛顿迭代因为常数项等问题，比较玄学，建议多迭几次。考虑使用拉格朗日反演，对于形式幂级数。的形式，若把原来的式子转化成。事实上，正确的方法应该令。，把原来的式子转化成。......
2022-08-04 21:57:18
112
原创 【PR #2】史莱姆（值域分段）
首先看单次询问我们怎么做。对于一个人，他的最优策略显然是不断吃最小的，并看最后能不能吃完。假设我们把区间内的数排好序了，设为 a1≤a2≤⋯≤ana_1\leq a_2\leq \cdots\leq a_na1≤a2≤⋯≤an。对于一个 uuu，它能吃完所有的人当且仅当：∀i<u,au+∑j=1i−1aj−ai≥k∀i>u,∑j=1i−1aj−ai≥k\begin{aligned}\forall i<u,a_u+\sum_{j=1}^{i-1}a_j-a_i\geq k\\
2022-04-11 13:20:03
155
原创 NOI2022模拟测试赛（二十二）
link通道自己对于二分图构造一个类 prufer 序列。一个映射方式是合法的，只需要：一棵生成树能构造出一个 prufer 序列。能从一个 prufer 序列逆推回整棵树的形态，即过程中不会出现 “找不到” 或者 “找到多个合法解” 的情况。敢造就敢有！排列转化后题意：给定三个长度同为 nnn 的序列 V,A,BV,A,BV,A,B，保证 Vi>0V_i>0Vi>0。求选出一个区间 [l,r][l,r][l,r]，最大化 (∑i=lrVi)+mini=lr(A
2022-04-08 20:24:59
613
原创 【XSY4371】star（构造）
题意：给定值域在 [0,n−1][0,n-1][0,n−1] 的序列 a1,⋯ ,ama_1,\cdots,a_{m}a1,⋯,am，要求构造值域在 [0,n−1][0,n-1][0,n−1] 的序列 b1,⋯ ,bmb_1,\cdots,b_{m}b1,⋯,bm 和 c1,⋯ ,cmc_1,\cdots,c_{m}c1,⋯,cm，使得 bib_ibi 两两不同、cic_ici 两两不同、且 ∀i,bi+ci≡ai(modn)\forall i,b_i+c_i\equiv a_i\pmod
2022-04-03 14:39:16
356
原创 勾股数的一些性质
称一个正整数三元组 (a,b,c)(a,b,c)(a,b,c) 为一组本原勾股数，当且仅当其满足 a2+b2=c2a^2+b^2=c^2a2+b2=c2 且 gcd(a,b,c)=1\gcd(a,b,c)=1gcd(a,b,c)=1。不是本原勾股数的勾股数被称作派生勾股数。任意本原勾股数 (a,b,c)(a,b,c)(a,b,c) 的任意 kkk 倍对应着一组勾股数 (ka,kb,kc)(ka,kb,kc)(ka,kb,kc)。同时一组勾股数 (a,b,c)(a,b,c)(a,b,c) 唯一对应着一组
2022-04-02 22:23:59
1167
原创 【NOI Online 2021 提高组】愤怒的小 N（生成函数，结论）
令 n=logmn=\log mn=logm，记 mmm 在二进制表示下为 sn−1⋯s1s0‾\overline{s_{n-1}\cdots s_1s_0}sn−1⋯s1s0。首先可以归纳得到一个位置 xxx 为 b\texttt{b}b 当且仅当 popc(x)≡1(mod2)\operatorname{popc}(x)\equiv 1\pmod 2popc(x)≡1(mod2)，那么我们要统计的即为 ∑x=0m−1[popc(x)&1]f(x)\sum_{x=0}^{m-1}[
2022-03-29 16:10:27
216
原创 【ZJOI2019】开关（PGF）
听说这玩意叫 PGF？方便起见，令 pi=pi∑jpjp_i=\frac{p_i}{\sum_jp_j}pi=∑jpjpi。设 Fi(x)F_i(x)Fi(x) 表示对于第 iii 个开关而言，对其进行 kkk 次操作之后，它达到目标状态的概率的 EGF（其实文字不好表达 Fi(x)F_i(x)Fi(x) 的意思，因为它只是一个辅助生成函数。看下去就能理解 Fi(x)F_i(x)Fi(x) 的用途），那么有：Fi(x)=∑k≥0[k mod 2=si]pikxkk!=epix+(−1)
2022-03-27 19:50:35
708
原创 全局平衡二叉树
全局平衡二叉树类似于静态的 LCT？建树方法：先树剖，考虑对于每一条重链维护一棵二叉树，且每条重链的二叉树的根与该重链的链头的父亲之间有一条虚边（认父不认子）。为了达到全局的平衡，每棵重链的二叉树并不是完美的二叉树：对于该重链上的每个点 uuu 设置一个权值 vuv_uvu 为该点的轻子树大小和 +1+1+1（即 sz[u]−sz[son[u]]sz[u]-sz[son[u]]sz[u]−sz[son[u]]），然后找到这条链上的带权中点作为这棵二叉树的根（即找到一个位置 kkk 使得 sk−1≤
2022-03-18 14:51:37
944
原创 【P5385】【Cnoi2019】须臾幻境（LCT）
题面：有 nnn 个点，有一个长度为 mmm 的边序列 AAA，qqq 次询问由这 nnn 个点和 Al,⋯ ,ArA_l,\cdots,A_rAl,⋯,Ar 的边构成的图中的连通块数量。强制在线。n,q≤105n,q\leq 10^5n,q≤105，m≤2×105m\leq 2\times 10^5m≤2×105。题解：在线也能把它搞成离线：枚举右端点 rrr 右移，并维护 A1,⋯ ,ArA_1,\cdots,A_rA1,⋯,Ar 组成的以下标为边权的最大生成森林，以及一棵可持久化线段树
2022-03-16 21:12:19
225
原创 左偏树原理记录
这玩意老是忘，还是记录一下吧（考虑一般的合并两棵以 x,yx,yx,y 为根的堆的过程：若 x,yx,yx,y 中有一者是 000，返回另一者。否则不妨设 vx≤vyv_x\leq v_yvx≤vy，那么我们就是把 xxx 设为新的堆的根，然后选 xxx 的某一个儿子和 yyy 合并。左偏树就是利用了第一条性质。我们设 “外节点” 表示只有至多一个儿子的节点，设一个点的 “距离” 表示这个点到其子树内最近的外节点的距离。设节点 xxx 的距离为 ddd，那么其子树内至少有 O(2d)O(2
2022-03-16 20:54:40
436
原创 【CF1299D】Around the World（线性基）
题意：给定一张 nnn 个点 mmm 条边的无向连通图，边带权，保证不存在一个长度 >3>3>3 的简单环经过了 111 号点。请求出有多少种方案删除若干条与 111 号点相连的边，使得不存在任何一条路径（不一定是简单路径）满足：以 111 号点为起点，以 111 号点为终点。路径经过的所有边的边权异或和为 000（经过多次异或多次）。图上至少有一条边被该路径经过了奇数次。n,m≤105n,m\leq 10^5n,m≤105，w≤31w\leq 31w≤31。题解：先考虑
2022-03-16 15:42:44
687
原创 【XSY4375】永无乡（二元GF）
以下 “二叉树” 均默认为有根无标号但区分左右儿子的二叉树。设 hn,kh_{n,k}hn,k 表示 n,kn,kn,k 的答案，有：hn,k=∑i=0n−1(hi,k⋅fn−i−1+fi⋅hn−i−1,k+∑j=0k(kj)gn−i−1,k−j∑j′=0j(jj′)gi,j′)h_{n,k}=\sum_{i=0}^{n-1}\left(h_{i,k}\cdot f_{n-i-1}+f_{i}\cdot h_{n-i-1,k}+\sum_{j=0}^{k}\binom{k}{j}g_{n-i-1,k
2022-03-16 12:49:37
144
原创 【XSY4320】Catalan（组合意义，DP，多项式）
题面：Catalan题解：假瑞的做法orz考虑用组合意义来做，观察递推式 fi=1i∑j=0i−1fjfi−j−1f_i=\frac{1}{i}\sum_{j=0}^{i-1}f_jf_{i-j-1}fi=i1∑j=0i−1fjfi−j−1，它除了和卡特兰数递推式很像之外，还和二叉树计数的递推式很像。同时注意到 f0=0f_0=0f0=0，所以递推式可以变为 fi=1i∑j=1i−2fjfi−j−1f_i=\frac{1}{i}\sum_{j=1}^{i-2}f_jf_{i-j-1}f
2022-03-11 20:02:33
997
原创 【XSY4350】摆（行列式，数论，杜教筛）
题面摆题解首先我们将原矩阵写成 A+BA+BA+B，其中 BBB 全是 CCC，那么 AAA 的第 iii 行就只有其倍数处有值，且 Ai,i=1−C,Ai,j(i∣j∧i≠j)=−CA_{i,i}=1-C,A_{i,j(i|j\land i\neq j)}=-CAi,i=1−C,Ai,j(i∣j∧i=j)=−C。那么原来的行列式就变成了：∑p(−1)sgn(p)∑S⊆{1,⋯ ,n}∏i∈SAi,pi∏i∉SBi,pi\sum_{p}(-1)^{\operatorname{sgn}
2022-03-09 22:16:52
168
原创 NOI2021模拟测试赛（六十）
题面西克把 x→yx\to yx→y 拆成 x→lca→yx\to lca\to yx→lca→y，而 x→lcax\to lcax→lca 的部分很好搞，不予阐述。关键是 y→lcay\to lcay→lca 的部分，我们考虑离线解决。从上往下走时，对每种颜色 ccc 维护一个点 rtcrt_crtc，表示当前对于 ccc 的询问。每当走到 xxx 时，就把 rtaxrt_{a_x}rtax 的父亲指向 rtbxrt_{b_x}rtbx，并且把 rtaxrt_{a_x}rtax 设为一
2022-03-07 12:42:39
214
原创 【NOI2018】你的名字（后缀自动机，线段树合并）
题意：给定一个字符串 SSS，qqq 次询问 T,l,rT,l,rT,l,r，求 TTT 和 S[l,r]S[l,r]S[l,r] 的本质不同公共子串数目。∣S∣≤5×105|S|\leq 5\times 10^5∣S∣≤5×105，q≤105q\leq 10^5q≤105，∑∣T∣≤106\sum |T|\leq 10^6∑∣T∣≤106。题解：首先看一个弱化版的问题：给出两个串 S,TS,TS,T，求 S,TS,TS,T 的本质不同公共子串数目。由于要求本质不同，所以思路是建出 TTT 的后缀
2022-03-02 12:41:12
329
原创 【XSY3726】大猫熊和他的k边形（三角剖分，卡特兰数）
记录一下两个结论。有标号 nnn 边形的三角剖分数等于 Bn−2B_{n-2}Bn−2，其中 BBB 是卡特兰数。证明：考虑 DP，设 CnC_nCn 为有标号 nnn 边形的三角剖分数，考虑与 111 号点相连的最小的那条边 (1,1+i)(1,1+i)(1,1+i)（若没有与 111 号点相连的边则钦定与 111 号点相连的最小的那条边为 (1,n)(1,n)(1,n)），有：Cn=∑i=2n−1CiCn−i+1C_n=\sum_{i=2}^{n-1} C_{i}C_{n-i+1}C
2022-02-25 16:49:44
433
原创 【XSY4058】区间加区间（分块FFT）
题面区间加区间题解考虑若操作是将 a1,⋯ ,ana_1,\cdots,a_na1,⋯,an 加到 bl,⋯ ,bl+n−1b_l,\cdots,b_{l+n-1}bl,⋯,bl+n−1，我们可以记录每个 lll 被操作的次数 clc_lcl，那么最后的 bi=∑j=1najci−j+1b_i=\sum_{j=1}^n a_jc_{i-j+1}bi=∑j=1najci−j+1，可以直接 FFT 优化到 O(nlogn)O(n\log n)O(nlogn)。但现在是选 aaa 中的
2022-02-24 14:23:42
268
原创 FFT在字符串匹配中的应用
对于一类字符串匹配问题：给定长度分别为 m,nm,nm,n 的字符串 A,BA,BA,B，给出两个相同长度的字符串匹配的定义，要求找出 AAA 在 BBB 中所有匹配的位置。可能能用如下方式解决：定义匹配函数 C(a,b)C(a,b)C(a,b)，使得完全匹配函数 P(i)=∑j=0m−1C(Aj,Bi+j)P(i)=\sum_{j=0}^{m-1}C(A_j,B_{i+j})P(i)=∑j=0m−1C(Aj,Bi+j) 等于 000 当且仅当 AAA 和 B[i..i+m−1]B[i..i
2022-02-24 10:57:44
898
空空如也
C++ 类模板的简单问题
2022-10-02
TA创建的收藏夹 TA关注的收藏夹
TA关注的人