- 博客(810)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 ZKW线段树区间加区间取最值
本来以为是和zkw单点修改之类的简单技巧，但是今天卡常的时候学习了一下发现有点离谱。树状数组的区间加区间求和是利用差分和一次前缀和来完成的，但是写在线段树上就不用差分了。但是可以差分，并且zkw线段树提供了一种线段树式的差分方法：对于每个点，只存一个标记trxtr_xtrx，表示maxfax−maxx\max_{fa_x} - \max_{x}maxfax−maxx，也就是线段树上一个节点和他父亲区间最大值的差分，我们现在可以知道一个线段树上一个整区间的最大值就是他到根的和。那么我们求区
2020-08-09 21:25:10
1040
原创 「PKUWC2018」猎人杀（分治FFT）
题目首先这个概率不太好算。我们换一种方式：每次可以向已经死了的猎人开枪。那么可以发现最后一个死的猎人的概率分布是不变的。所以我们现在可以直接求出每次开枪时某一个人被射中的概率pip_ipi。然后容斥求出某个人是最后一个死的概率：枚举哪些人是一定在这个人之后死的：设这些人的概率和为QQQ则我们要求的概率是∑i=1p1(1−p1−Q)i−1=p11−p1−Q\sum_{i=1} p_1(1-p_1-Q)^{i-1} = \frac {p_1}{1-p_1-Q}∑i=1p1(1−p1−Q)
2020-08-09 15:42:56
509
原创 WC 2020 选课（背包）
题目好自闭啊，5KB的背包鬼知道我经历了什么设L=40L = 40L=40如果没有物品之间的限制，对于一组可以O(nlogn)O(n\log n)O(nlogn)贪心求出只有w=1,2w=1,2w=1,2的答案再和w=3w = 3w=3的合并，注意到我们只需要mLmLmL个状态，对于多组可以直接O(L2)O(L^2)O(L2)合并，所以这部分复杂度是O(mL2)O(mL^2)O(mL2)的。（分析其实没有看上去那么简单。）听说w \leq 5都可以闵科夫斯基和的有物品的限制就枚举状态后继续做之前
2020-08-08 22:54:10
850
原创 「WC2020」有根树（轻重链剖分）
题目容易发现题目中那个包含111的连通块是提示你的，并不是来限制你的。那么答案一定是SSS中选择最大的若干个www，剩下的www的最大值≤∣S∣\leq |S|≤∣S∣。设剩下的 www为集合XXX考虑一个调整的过程：如果∣S∣<maxw∈Xw|S| \lt \max_{w \in X} w∣S∣<maxw∈Xw，则选出maxw∈Xw\max_{w \in X} wmaxw∈Xw从XXX删去后加入SSS。如果∣S∣>maxw∈Xw|S| \gt \max_{w\in
2020-08-08 20:03:38
792
原创 模拟赛 我的朋友们（分治NTT）
题意：有一个长度为nnn的序列，序列上每个位置有一个物品，每个物品在每次被询问到的时候有pip_ipi的概率被拒绝，考虑这样一个过程：先取前LLL个物品，然后每次对这LLL个物品都询问，如果有xxx个物品被拒绝，则将前xxx个物品丢弃，然后从未被选取的物品中选取最靠前的xxx个物品重复这个过程，当总物品数<L\lt L<L时停止，问期望询问多少组次。n,L≤1e5n , L \leq 1e5n,L≤1e5， mod 998244353\bmod 998244353mod998244353
2020-08-03 19:57:37
469
原创 Nim积
我也只会模板可以用类似大整数分治乘法的思路用Fermat 2-power\texttt{Fermat 2-power}Fermat 2-power做到比较快的log2\log^2log2计算。（只用分成四个乘法而非五个。）真正的优化其实是部分记忆化#include<bits/stdc++.h>#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)#define per(i,j,k) for(int i=(
2020-07-29 16:44:50
645
原创 多项式多点求值的小常数解法
设MULT(f(z),g(z))=∑i=0zi∑j=0([zi+j]f(z))([zj]g(z))MUL^T(f(z),g(z)) = \sum_{i=0} z^i\sum_{j=0} ([z^{i+j}]f(z))([z^j]g(z))MULT(f(z),g(z))=∑i=0zi∑j=0([zi+j]f(z))([zj]g(z))也就是差卷积。可以发现F(x0)=∑i=0nx0i[xi]F(x)=[x0]MULT(F(x),11−x0z)F(x_0) =\sum_{i=0}^n x_0^i[x^
2020-07-28 22:47:38
457
原创 ZJOI2020 抽卡（拉格朗日反演）
题目二元生成函数与拉格朗日反演：比较好的形式：对于二元GFGFGF，第二个元一般来说都是来辅助的，因为一个元用来拉格朗日反演了，另一个元就可以让我们来做多项式操作。比如二元GF:GF:GF:H(u,z)=11−uF(z)H(u,z) = \frac {1}{1 - uF(z)}H(u,z)=1−uF(z)1，F(z)F(z)F(z)有复合逆G(z)G(z)G(z)。则由于拓展拉格朗日反演：[zn]11−uF(z)=1n[zn−1]d11−uzdz(zG(z))n[z^n]\frac 1{1-uF(
2020-07-28 20:37:22
572
原创 CODECHEF DISTNUM: Simple Queries（三维偏序）
题面首先这个离谱的询问一：关于不同的数的和，可以构造求出每个点(x,Sx)(x,S_x)(x,Sx)的前面第一个(y,Sy=Sx)(y,S_y =S_x)(y,Sy=Sx)，那么把(y,x)(y,x)(y,x)看做一个二维平面上的点，那么对[l,r][l,r][l,r]中不同数的个数即为y<l,l≤x≤ry \lt l , l \leq x \leq ry<l,l≤x≤r的点数。那么在没有插入删除的情况下这就是一个三维偏序（注意128MB卡内存，可以用离线的方法树状数组套树状数组空间
2020-07-27 19:30:30
229
原创 20200726模拟赛 C.树高
待填。人生第一次在ACACAC前有90次提交记录的题。人生第一次写了10K10K10K代码的题（写完6KTreap6KTreap6KTreap发现TLETLETLE的死死的然后开始写7KSplay7KSplay7KSplay然后卡了一个世纪。）AC Code\mathcal AC \ CodeAC Code#include<bits/stdc++.h>#define maxn 200005#define rep(i,j,k) for(int i=(j),LIM=.
2020-07-27 09:37:18
300
原创 sort（区间异或，区间排序，区间或，区间与，Trie树合并,Treap）
看标题就知道是大工业题四种操作（标题前四个短语）求最后的序列。n≤1e5,v≤232n \leq 1e5 , v \leq 2^{32}n≤1e5,v≤232考虑只有排序：发现有序的一段可以直接用一个01trie01trie01trie树来存储，trietrietrie树上字典序从小到大的值就是这一段从左到右的值。那么区间排序[l,r][l,r][l,r]时就相当于把这个区间[l,r][l,r][l,r]的所有数字放到一个trietrietrie树T1T_1T1里面，用一个三元组[l,r,T1
2020-07-25 17:58:57
624
原创 HDU2020多校赛第二场
A - Total Eclipse题目让我们模拟每次找出最大的正连通块然后全部权值减一。容易发现优化这个过程就是在最大的正连通块中找到最小值然后删去它。因为加点维护连通性有并查集可以写比删点好写一万倍。所以我们倒过来考虑每次加入值最大的点然后合并一下维护一下花费即可。AC Code\mathcal AC \ CodeAC Code#include<bits/stdc++.h>#define maxn 100005#define LL long longusi
2020-07-23 22:55:19
344
原创 CF331 E1/E2 Deja Vu
首先可以发现路径上一定存在一条边，它的顶点序列中存在连续的两个顶点恰好是这条边的两个端点。然后从这条边往左右拓展出极小合法路径。再同样求一下顶点序列不包含一个端点的极小路径。就可以很暴力的合并然后求方案数了。AC Code\mathcal AC\ CodeAC Code#include<bits/stdc++.h>#define maxn 55#define maxm 55 * 55#define rep(i,j,k) for(int i=(j),LIM=(.
2020-07-23 18:22:40
421
原创 MTT
合并FFTFFTFFT：三次翻转一次：共轭单位根两次：代入共轭单位根后的值需要再取共轭三次：A(x)+iB(x)A(x) + i B(x)A(x)+iB(x)其中A(x)=p−q2A(x) = \frac {p - q} 2A(x)=2p−q ,则B(x)=iq−p2B(x) = i\frac {q - p}{2}B(x)=i2q−p。任意模数多项式卷积：#include<bits/stdc++.h>#define maxn 300005#define rep(i,j,k) f
2020-07-22 22:38:16
445
原创 杭电多校赛2020第一场VP实录
D - Distinct Sub-palindromes思博题。AC Code\mathcal AC\ CodeAC Code#include<cstdio>int main(){int T;scanf("%d",&T);for(;T--;){int n;scanf("%d",&n);if(n == 1) puts("26");if(n == 2) puts("676");if(n == 3) puts("17576");if(n &g
2020-07-21 22:39:52
403
原创 势函数和鞅的停时定理
借鉴了借鉴他人博客的博客问题：对于随机过程{A0,A1...At}\{A_0,A_1...A_t\}{A0,A1...At}，有TTT为关于这个过程停止时间的随机变量，求E(T)E(T)E(T)势函数：一个关于状态的函数ϕ(A)\phi(A)ϕ(A)，其中AAA是一个状态。对于随机过程中的任意连续两个状态At,At+1A_t,A_{t+1}At,At+1如果我们让E(ϕ(At+1)−ϕ(At))=−1E(\phi(A_{t+1}) - \phi(A_t)) = -1E(ϕ(At+1)−
2020-07-18 18:40:33
1605
原创 非传统题训练
Codechef Guessing Game猜x≤1e9x \leq 1e9x≤1e9，你可以问yyy是<x,>x<x , >x<x,>x还是=x=x=x，但是他可以对于<<<和>>>撒谎（说成另一种），但是不能连续两次撒谎，询问次数≤120\leq 120≤120。连续询问两次，每次询问可以得到两个区间，一个区间为撒谎时的区间，另一个为不撒谎时的区间。这两个撒谎时的区间的交区间就可以排除掉。那么我们第一次询问问区间n2\fra
2020-07-17 15:51:56
337
原创 计算几何（三）
LOJ #2401. 「JOISC 2017 Day 4」Dragon 2首先这题有个条件就是每次询问的A,BA,BA,B不会和之前的询问相同，那么我们对于一个询问A,BA,BA,B，我们找出龙数更少的那个集合假设是AAA，那么我们只要能在O(C∣A∣)O(C|A|)O(C∣A∣)的时间复杂度内解决这个问题，我们的总复杂度就是O((n+q)nC)O((n+q) \sqrt nC)O((n+q)nC)的。因为对于∣A∣≤n|A| \leq \sqrt n∣A∣≤n，一次询问复杂度就是O(nC)O(\s
2020-07-16 21:28:31
322
原创 可持久化数据结构
CF702F T-Shirts对于每个人剩下的钱建平衡树，那么我们按照优先级对于每个物品(c,p)(c,p)(c,p)，将钱≥c\geq c≥c的人的钱−=c-=c−=c，答案++++++，区间打标记即可，注意到用非旋treaptreaptreap维护时c≤x<2cc\leq x \lt 2cc≤x<2c的物品无法直接mergemergemerge，拿出来暴力插入即可，可以证明每次xxx的权值会缩小至少一半，所以暴力插入次数是O(nlogx)O(n\log x)O(nlogx)的。AC&n
2020-07-15 21:09:08
255
原创 数据结构难题训练（二）
LOJ #558. 「Antileaf’s Round」我们的 CPU 遭到攻击考虑不要脸的直接用LCT维护此题的答案，那么我们需要虚子树xsizexsizexsize，虚子树上来的答案和xsumxsumxsum，还有当前节点所代表的链中所有节点到最左边的和，最右边的和，容易发现到根的答案就是到最左边的和，但是因为有LCTLCTLCT自带的reversereversereverse操作，所以需要存到右边的和来协助打懒标记。注意link的时候x,yx,yx,y都需要变为根，因为拿xxx作为yyy的虚儿子，
2020-07-14 21:32:51
442
原创 数据结构难题训练
CF903G Yet Another Maxflow Problem看做最小割后简单维护即可。AC Code\mathcal AC \ CodeAC Code#include<bits/stdc++.h>#define maxn 200005#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)#d
2020-07-13 17:43:15
388
原创 daklqw 的 T3（点分树上数据结构优化DP）
设fxf_xfx为从第xxx个事件开始做最多的收益。那么这个dpdpdp是按照时间线从后往前的dpdpdp，求每个点的做起点的答案可以简单的在每个点初始放一个A=K=P=0A=K=P=0A=K=P=0的时间即可解决。对于两个事件之间的转移，我们只需要这两个事件在树上的距离s1s1s1，最小多走多少距离可以到达一个奖励边刷分并且走回这两个点的最短路径s2s2s2，（贪心来说，如果我们绕路，那么一定是在一个最近的奖励边上面刷分）最短路径上本来有多少奖励边ccc。那么如果这两个事件之间可以让我们移动
2020-07-12 17:43:26
558
1
原创 图论难题训练
HDU 6350 Always Online给出一个仙人掌，求∑s,ts⊕t⊕maxflow(s,t)\sum_{s,t}s \oplus t \oplus \operatorname{maxflow}(s,t)∑s,ts⊕t⊕maxflow(s,t)对于一棵树的情况，maxflow(s,t)\operatorname{maxflow}(s,t)maxflow(s,t)就是s,ts,ts,t的简单路径上最短的一条边的权值。用并查集从大到小枚举每条边，然后将边两端的点的集合合并，合并前可以通过统
2020-07-10 14:23:08
564
原创 「SDOI2017」文本校正
题目 分类讨论六种排列：ABC：ABC：ABC：一次哈希判断。CAB：CAB：CAB：枚举CCC的长度，总共nnn次哈希判断。BCA：BCA：BCA：枚举AAA的长度，总共nnn次哈希判断。CBA：CBA：CBA：构造新串P=s1tns2tn−1...snt1P = s_1t_ns_2t_{n-1}...s_nt_1P=s1tns2tn−1...snt1那么问题转化为将PPP划分为333个偶回文串。枚举第一个回文串的位置[1....2x][1....2x][1....2x]，那么就
2020-07-08 10:26:10
552
转载 非数据结构向字符串算法
Periodicity Lemma的证明模板题：SDOI2017 文本校正接下来是bonus time看完这篇博客然后做这个更可做的题：
2020-07-07 21:34:16
278
原创 字符串作业（四）
「BJOI2020」封印给出只包含小写字母aaa,bbb的两个字符串sss,ttt，qqq次询问，每次询问s[l...r]s[l...r]s[l...r]和ttt的最长公共子串长度。建出ttt的后缀自动机后在自动机上跑sss串得到对于每个sss的前缀在ttt中匹配的最长长度pip_ipi，然后对于s[l...r]s[l...r]s[l...r]，二分答案midmidmid，检查是否有maxi=l+mid−1rpi≥mid\max_{i=l+mid-1}^rp_i \geq midmaxi=l+mid
2020-07-07 17:25:33
337
原创 字符串作业（三）
LOJ #6158. A + B Problem给出一个数字，求在其中两位之间插入一个加号后得到的答案末尾000最多的个数。题解：第二个数的末尾就是原串的末尾，所以如果需要和第一个数加起来末尾为000，那么从后往前扫，第二个数为000的位在不进位的情况下第一个数的对应位需要是000，不为000的位的对应位xxx应该是10−x10 - x10−x，然后开启进位模式所有数的对应位都是9−x9-x9−x，然后求一个原串和转换后的串的最长公共前缀即可得出答案，可以写exkmp\rm exkmpexkmpAC
2020-07-06 17:36:39
320
转载 20200704模拟赛
T1sub1sub1sub1没有问号的情况下，考虑如何线性判定。考虑每两位当作一组，对于每组有如下两种操作：将两位依次压入栈中；将第一位与栈中全部元素合并后，再将第二位压入栈中。可以发现栈中的情况可以看作是关于下一个压入元素的函数，即 G[a,b](x)G[a, b](x)G[a,b](x)，表示当 $x = 0 $时返回 aaa，x=1x = 1x=1 时返回 bbb。假设当前栈中情况为 G[a,b](x)G[a, b](x)G[a,b](x)，考虑压入两位 c,dc, dc,d，容易根据
2020-07-04 16:13:58
294
原创 CF1278F Cards 加强版
题目设p=1mp = \frac 1mp=m1ans=∑i=0k{ki}pi(ni)i!=∑i=0k∑j=0i(ij)(ni)pi(−1)j(i−j)k=∑j=0k(−1)j(nj)∑i=jk(n−ji−j)pi(i−j)k=∑j=0k(−1)jpj(nj)∑i=0k−j(n−ji)piik=∑i=0kikpi∑j=0k−i(−p)j(nj)(n−ji)=∑i=0kikpi(ni)∑j=0k−i(−p)j(n−ij)\begin{aligned} ans &= \sum_{i=0}^k \be
2020-07-03 22:38:34
311
原创 LOJ #2476. 「2018 集训队互测 Day 3」蒜头的奖杯（三元环计数）
题目泰勒应天下大雨！类似于SDOI2018SDOI2018SDOI2018旧试题。给DDD,EEE,FFF卷上μ\muμ。得到D′,E′,F′D',E',F'D′,E′,F′。原式变为∑i,j,kAiBjCk∑a∣i,a∣jDa′∑b∣i,b∣kEb′∑c∣j,c∣kFc′\sum_{i,j,k} A_iB_jC_k \sum_{a|i,a|j} D'_a \sum_{b|i,b|k} E'_b \sum_{c|j,c|k} F'_ci,j,k∑AiBjCka∣i,a∣j∑Da′b∣i
2020-07-03 21:12:58
483
原创 各种反演等数学难题
CF997C Sky Full of Stars求n×nn\times nn×n的网格内每个格子染三种颜色，其中至少有一行或一列是同一种颜色的方案数。转化为求没有一行或一列颜色相同。直接枚举相同的行列数进行容斥：=3∑i=0n(ni)(−1)i∑j=0n(nj)(−1)j3(n−i)(n−j)+2∑i=1n(ni)(−1)i3n(n−i)(3i−3)−2×3n2=3∑i=0n(ni)(−1)i(3n−i−1)n+2∑i=1n(ni)(−1)i3n(n−i)(3i−3)−2×3n2\begin{ali
2020-07-03 11:36:28
490
原创 生成函数、组合数学
[ARC089D] ColoringBalls咕着咕着[ARC096C] Everything on It容斥，枚举有kkk种元素用了≤1\leq 1≤1次，其中有jjj种元素用了111次。则答案为：∑k=0n(−1)k(nk)22n−k∑j=0k(kj)∑p=0j{jp}2(n−k)p\sum_{k=0}^n(-1)^k\binom nk2^{2^{n-k}}\sum_{j=0}^k \binom kj\sum_{p=0}^j \begin{Bmatrix}j\\p\end{Bmatrix}
2020-07-02 19:54:52
692
原创 线性代数，概率与期望题单
「SDOI2017」龙与地下城CodeForces - 506E Mr. Kitayuta’s Gift LOJ #6295. 无意识之外的捉迷藏
2020-07-01 20:44:50
482
原创 保序回归问题在序列上的特殊做法
LG P4331 [BalticOI 2004]Sequence 数字序列远古论文题。所以就可以单调栈维护区间的LpL_pLp均值，如果前面的均值比后面大则合并区间。最后单调栈中的区间的LpL_pLp均值就是一个可行方案。注意L2L_2L2等均值是可以O(1)O(1)O(1)求的，比如上面的论文。但是L1L_1L1的均值是中位数，还得写可并堆，这种情况真的罕见。再来一道例题：2020 Petrozavodsk Winter Camp, Jagiellonian U Contest
2020-06-30 22:44:55
387
原创 多项式题单
LOJ #556. 「Antileaf’s Round」咱们去烧菜吧求混合背包（某一体积的物品可能有无限个也可能有有限个），得到体积和为1...n1...n1...n的方案数。热身题。如果一个体积为vvv的物品有无限个，那么其关于体积的普通生成函数为∑i=0xvi=11−xv\sum_{i=0}x^{vi} = \frac 1{1-x^v}∑i=0xvi=1−xv1如果一个体积为vvv的物品有KKK个，那么其关于体积的普通生成函数为∑i=0Kxvi=1−xv(K+1)1−xv\sum_{i=0}
2020-06-30 15:33:00
607
1
原创 难题训练（二）
2020 Petrozavodsk Winter Camp, Jagiellonian U Contest.Problem G. Invited Speakers给出两个大小为nnn的点集，其中所有点的横纵坐标都不一样，给两个点集做匹配，两个点之间的匹配是坐标系中若干条平行于坐标轴的首尾相连的线段，求使得不同匹配不相交的匹配方案。因为横纵坐标都不一样，按照横坐标排序两个点集，然后对位匹配，确定一个大常数CCC，走ai→(ai.x,C+i)→(C+i,C+i)→(C+i,−C−i)→(bi.x,−C−i)
2020-06-27 09:55:56
821
原创 难题训练（一）
「EC Final 2019」狄利克雷 k 次根题意：给出一个函数的前nnn项g(1),g(2)....g(n)g(1),g(2)....g(n)g(1),g(2)....g(n)，求它在狄利克雷卷积意义下的kkk次根fff的前nnn项，这里的狄利克雷卷积是指h(n)=∑d∣nf(d)g(nd) mod ph(n) = \sum_{d|n} f(d)g(\frac nd)\bmod ph(n)=∑d∣nf(d)g(dn)modp。n≤1e5n \leq 1e5n≤1e5做法：容易发现fp=ϵf^p
2020-06-25 19:05:34
736
7
原创 两类递推数列
此博客是抄论文的，你可以认为是转载的1.线性递推数列有限数列显然是线性递推数列。无限数列aia_iai设其生成函数为A(x)A(x)A(x)那么如果A(x)A(x)A(x)能被表示为C(x)B(x)\frac {C(x)}{B(x)}B(x)C(x)的形式，其中B(x)[x0]=1B(x)[x^0] = 1B(x)[x0]=1，则A(x)A(x)A(x)是线性递推数列。常数项为111是因为递推式你要让∑j=0bjai−j=0\sum_{j=0}b_ja_{i-j} = 0∑j=0bjai−
2020-06-22 22:18:39
532
原创 [NOI2019]序列（模拟费用流）
题目费用流建出来大概是下面的图（没有写边权的边都是容量∞\infty∞，费用为000）所以这个图有444种流法（其实有555种，但是第555种在实际实现中可以被这444种覆盖。）1.1.1.类似于A→D→D′→JA \rightarrow D \rightarrow D' \rightarrow JA→D→D′→J的流，直接把ai+bia_i+b_iai+bi选中。2.2.2.类似于A→D→F→G→C′→JA\rightarrow D \rightarrow F \rightarrow G\r
2020-06-22 16:56:31
448
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人