- 博客(305)
- 收藏
- 关注
RSS订阅原创 多项式全家桶——炫酷多项式变换
文章目录FFT常数优化1——IDFT常数优化2MTT常数优化多项式求逆常数优化多项式取对数牛顿迭代多项式求指数多项式开方拉格朗日反演FFT相信大家FFT已经掌握的很熟练了。参考这一篇博客：浅谈算法——从多项式乘法到FFT常数优化1——IDFT若已知多项式A(x)A(x)A(x)的点值表示<(ωn0,A(ωn0)),(ωn1,A(ωn1)),⋯ ...
2019-01-27 15:45:37
1190
原创 路径压缩优化并查集的时间复杂度
路径压缩优化并查集大家一定很熟练了，那么它的复杂度是多少呢？O(mα(n))O(m\alpha(n))O(mα(n))？的确，很多人都是这么说的，但是事实上它的复杂度是O(mlog1+m/nn)O(m\log_{1+m/n}n)O(mlog1+m/nn)的，并且能找到一种方法卡到这样的复杂度。要卡并查集，首先要构造一种树——二项树。这种二项树还与普通的不太一样。定义：在给定jjj的情况下...
2019-01-14 12:12:20
6258
2
原创 支配树与Lengauer-Tarjan算法
伪目录给出支配树的定义给出一些性质介绍快速构造支配树的Lengauer-Tarjan算法及具体实现支配树是啥一个有源点的有向图，其支配树是满足下面条件的一个有向图：对于支配树上一点，若断开此点，则源点必定不能到达它的任何儿子，并且能到达其他任意一个点。不显然的，它是一棵树（当然后面会有证明）支配树有很多实际用途，我都不知道。一些性质对于一个有向图，假设源点为rrr，先从rr...
2019-01-14 11:33:44
985
原创 BZOJ 1488 [HNOI2009]图的同构 BZOJ 1815 [Shoi2006]color 有色图
题目链接https://lydsy.com/JudgeOnline/problem.php?id=1488https://lydsy.com/JudgeOnline/problem.php?id=1815题解考虑polya，对于一个点的置换A1,⋯ ,AnA_1,\cdots ,A_nA1,⋯,An，假设循环节的长度分别为L1,⋯&ThinSpace...
2019-01-11 11:55:38
249
原创 莫比乌斯反演+杜教筛 题表
“入门”难度BZOJ 3994 [SDOI2015]约数个数和BZOJ 4805 欧拉函数求和BZOJ 2440 [中山市选2011]完全平方数Luogu P3935 CalculatingLuogu P4450 双亲数BZOJ 4916 神犇和蒟蒻需要一点“小”技巧BZOJ 2005 [Noi2010]能量采集BZOJ 2154 Crash的数字表格 BZOJ 2693 jzp...
2019-01-10 17:15:22
384
原创 Luogu P4916 魔力环
题目链接https://www.luogu.org/problemnew/show/P4916题解将项链用序列表示，111代表黑色，000代表白色，对于一个合法序列，它必定能表示成ddd个循环节，每个循环节nd\frac{n}{d}dn个珠子，其中md\frac{m}{d}dm个黑色珠子。假设循环节长度为nnn的合法序列方案数为f(n)f(n)f(n)（不考虑旋转后相同的情况），容易发现...
2019-01-10 16:54:11
289
原创 BZOJ 4815 [Cqoi2017]小Q的表格
题目链接https://lydsy.com/JudgeOnline/problem.php?id=4815题解观察发现bf(a,a+b)=(a+b)f(a,b)bf(a,a+b)=(a+b)f(a,b)bf(a,a+b)=(a+b)f(a,b)很像更相减损术的式子，稍加推导可得f(a,b)=agcd(a,b)bgcd(a,b)f(gcd(a,b),gcd(a,b))f(a,b)=...
2019-01-10 16:32:16
230
原创 BZOJ 3512 DZY Loves Math IV
题目链接https://lydsy.com/JudgeOnline/problem.php?id=3512题解考虑枚举iii，定义g(n,m)=∑i=1mφ(in)g(n,m)=\sum_{i=1}^m \varphi(in)g(n,m)=i=1∑mφ(in)假设n=∏kpkakn=\prod_{k}p_k^{a_k}n=k∏pkak令n′=∏kpkr=∏kpkak...
2019-01-10 16:22:21
185
原创 BZOJ 4652 [Noi2016]循环之美
题目链接https://lydsy.com/JudgeOnline/problem.php?id=4652题解容易发现，若ij\frac{i}{j}ji在kkk进制下为纯循环小数，那么必定有ikl=imod  jkl=1mod  jik^l=i\mod{j}\\k^l=1\...
2019-01-09 20:26:56
199
原创 BZOJ 4913 [Sdoi2017] 遗忘的集合
题目链接https://lydsy.com/JudgeOnline/problem.php?id=4913题解令ai=0/1a_i=0/1ai=0/1表示元素iii是否在集合中，那么元素iii的生成函数为(11−xi)ai(\frac{1}{1-x^i})^{a_i}(1−xi1)ai现在已知了F(x)=∏i=1∞(11−xi)aiF(x)=\prod_{i=1}^{\in...
2019-01-09 16:59:57
298
原创 一个多项式求逆的卡常技巧
假设在 mod xn\bmod x^nmodxn下，多项式AAA的逆元是FFF，在 mod x⌈n/2⌉\bmod x^{\lceil n/2\rceil}modx⌈n/2⌉下，多项式AAA的逆元是F0F_0F0，根据多项式求逆的基本公式F=2F0−F...
2019-01-09 16:34:07
487
1
原创 BZOJ 4916 神犇和蒟蒻
题目链接https://lydsy.com/JudgeOnline/problem.php?id=4916题解∑i=1Nμ(i2)=1∑i=1Nφ(i2)=∑i=1Niφ(i)\sum_{i=1}^N \mu(i^2)=1\\\sum_{i=1}^N \varphi(i^2)=\sum_{i=1}^N i\varphi(i)i=1∑Nμ(i2)=1i=1∑Nφ(i2)=i=1∑N...
2019-01-08 09:44:41
183
原创 BZOJ 4816 [Sdoi2017]数字表格
题目链接https://lydsy.com/JudgeOnline/problem.php?id=4816题解反演∏T=1min(n,m)(∏d∣Tfib(d)μ(d))⌊n/d⌋⌊m/d⌋\prod_{T=1}^{\min(n,m)}(\prod_{d|T}fib(d)^{\mu(d)})^{\lfloor n/d\rfloor\lfloor m/d\rfloor}T=1∏min(...
2019-01-08 09:30:23
200
原创 BZOJ 3434 [Wc2014]时空穿梭
题目链接https://lydsy.com/JudgeOnline/problem.php?id=3434题解枚举选取的第一个点和最后一个点的坐标差∑ΔP=(Δx1,Δx2,⋯ ,Δxn)(gcd(ΔP)−1c−2)∏k=1n(mi−Δxi+1)\sum_{\Delta P=(\Delta x_1,\Delta x_2,\cdots,\Delta x_n)}...
2019-01-08 09:25:22
242
原创 BZOJ 5332 [Sdoi2018]旧试题
题目链接https://lydsy.com/JudgeOnline/problem.php?id=5332题解反演得到∑d=1min(A,B)μ(d)∑e=1min(A,C)μ(e)∑f=1min(B,C)μ(f)F(lcm(d,e),A)F(lcm(d,f),B)F(lcm(e,f),C)\sum_{d=1}^{\min(A,B)}\mu(d)\sum_{e=1}^{\min(A...
2019-01-08 09:03:15
289
原创 Luogu P4844 LJJ爱数数
题目链接https://www.luogu.org/problemnew/show/P4844题解1a+1b=1c\frac{1}{a}+\frac{1}{b}=\frac{1}{c}a1+b1=c1即bc+ac=(a+b)c=abbc+ac=(a+b)c=abbc+ac=(a+b)c=ab设g=gcd(a,b),A=ag,B=bgg=\gcd(a,b),A=\frac...
2019-01-07 11:45:26
386
原创 Luogu P4240 毒瘤之神的考验
题目链接https://www.luogu.org/problemnew/show/P4240题解容易发现φ(ij)=φ(i)φ(j)gcd(i,j)φ(gcd(i,j))\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}φ(ij)=φ(gcd(i,j))φ(i)φ(j)gcd(i,j)因此可...
2019-01-07 11:28:46
305
原创 Luogu P3768 简单的数学题
题目链接https://www.luogu.org/problemnew/show/P3768题解反演一发得到∑T=1n(∑i=1⌊n/T⌋i)2T2φ(T)\sum_{T=1}^n (\sum_{i=1}^{\lfloor n/T\rfloor}i)^2T^2\varphi(T)T=1∑n(i=1∑⌊n/T⌋i)2T2φ(T)设f(T)=T2φ(T)f(T)=T^2\var...
2019-01-07 11:13:47
271
原创 Luogu P4450 双亲数
题目链接https://www.luogu.org/problemnew/show/P4450题解直接反演以下就好了，甚至都不用整除分块……代码#include <cstdio>#include <algorithm>int read(){ int x=0,f=1; char ch=getchar(); while((ch<'0')||(...
2019-01-07 11:06:46
215
原创 Luogu P3935 Calculating
题目链接https://www.luogu.org/problemnew/show/P3935题解可以看出fff函数就是约数个数。直接O(n)O(\sqrt{n})O(n)求约数个数函数的前缀和即可。代码#include <cstdio>template<typename T>T read(){ T x=0; int f=1; char ch...
2019-01-07 11:03:47
218
原创 BZOJ 4805 欧拉函数求和
题目链接https://lydsy.com/JudgeOnline/problem.php?id=4805题解直接杜教筛筛φ\varphiφ函数即可。代码#include <map>#include <cstdio>#include <algorithm>int read(){ int x=0,f=1; char ch=getchar...
2019-01-07 11:00:34
215
1
原创 BZOJ 4407 于神之怒加强版
题目链接https://lydsy.com/JudgeOnline/problem.php?id=4407题解反演∑T=1min(n,m)⌊nT⌋⌊mT⌋∑d∣Tdkμ(Td)\sum_{T=1}^{\min(n,m)}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d|T}d^k\mu(\frac{T}{d})T=1∑...
2019-01-07 10:58:52
383
2
原创 BZOJ 3930 [CQOI2015]选数
题目链接https://lydsy.com/JudgeOnline/problem.php?id=3930题解反演得到∑i=1⌊h/k⌋μ(i)(⌊hki⌋−⌊l−1ki⌋)n\sum_{i=1}^{\lfloor h/k\rfloor} \mu(i) (\lfloor \frac{h}{ki}\rfloor-\lfloor\frac{l-1}{ki}\rfloor)^ni=1∑⌊h/...
2019-01-07 10:51:48
180
原创 BZOJ 3994 [SDOI2015]约数个数和
题目链接https://lydsy.com/JudgeOnline/problem.php?id=3994题解莫比乌斯反演得到∑k=1nμ(k)∑i=1⌊n/k⌋σ0(i)∑i=1⌊n/k⌋σ0(i)\sum_{k=1}^{n} \mu(k)\sum_{i=1}^{\lfloor n/k\rfloor}\sigma_0(i)\sum_{i=1}^{\lfloor n/k\rfloor}\...
2019-01-07 10:45:35
195
原创 BZOJ 4176 Lucas的数论
题目链接https://lydsy.com/JudgeOnline/problem.php?id=3994题解莫比乌斯反演得到∑k=1nμ(k)∑i=1⌊n/k⌋σ0(i)∑i=1⌊n/k⌋σ0(i)\sum_{k=1}^{n} \mu(k)\sum_{i=1}^{\lfloor n/k\rfloor}\sigma_0(i)\sum_{i=1}^{\lfloor n/k\rfloor}\...
2019-01-07 10:43:07
182
原创 BZOJ 3529 [Sdoi2014]数表
题目链接https://lydsy.com/JudgeOnline/problem.php?id=3529题解题目要求∑i=1n∑j=1mσ0(gcd(i,j))[σ0(gcd(i,j))≤a]\sum_{i=1}^n\sum_{j=1}^m \sigma_0(\gcd(i,j))[\sigma_0(\gcd(i,j))\leq a]i=1∑nj=1∑mσ0(gcd(i,j)...
2019-01-06 21:45:16
142
原创 BZOJ 3309 DZY Loves Math
题目链接https://lydsy.com/JudgeOnline/problem.php?id=3309题解莫比乌斯反演∑i=1n∑j=1mf(gcd(i,j))=∑T=1min(n,m)⌊nT⌋⌊mT⌋∑d∣Tμ(Td)f(d)\begin{aligned}&amp; \sum_{i=1}^n \sum_{j=1}^m f(\gcd(i,j))\\= &amp...
2019-01-03 09:49:21
140
原创 BZOJ 3202 [Sdoi2013]项链
题目链接https://lydsy.com/JudgeOnline/problem.php?id=3202题解这题可以分成两部分：一个是统计珠子的个数，一个是统计项链的个数。对于珠子的个数，记S3S3S3为gcd=1\gcd=1gcd=1的三个数的个数，S2S2S2为gcd=1\gcd=1gcd=1的两个数的个数，S1S1S1为gcd=1\gcd=1gcd=1的一个数的个数，容易发现...
2019-01-03 09:30:22
260
原创 BZOJ 2818 Gcd BZOJ 2820 YY的GCD
题目链接https://lydsy.com/JudgeOnline/problem.php?id=2818https://lydsy.com/JudgeOnline/problem.php?id=2820题解∑p∑i=1n∑j=1m[gcd(i,j)=p]=∑T=1min(n,m)⌊nT⌋⌊mT⌋∑p∣Tμ(Tp)\begin{aligned}&amp; \sum_{p} ...
2019-01-02 21:52:24
181
原创 BZOJ 2671 Calc
题目链接https://lydsy.com/JudgeOnline/problem.php?id=2671题解对于一对(a,b)(a,b)(a,b)满足a+b∣aba+b\mid aba+b∣ab，假设d=gcd(a,b),a=xd,b=ydd=\gcd(a,b),a=xd,b=ydd=gcd(a,b),a=xd,b=yd，那么xd+yd∣xyd2x+y∣xydx+y∣dxd+yd\m...
2019-01-02 21:42:34
252
原创 BZOJ 2440 [中山市选2011]完全平方数
题目链接https://lydsy.com/JudgeOnline/problem.php?id=2440题解发现答案满足可二分性，考虑二分答案，假设值为xxx，容斥之后发现[1,x][1,x][1,x]中不是完全平方数的个数就是∑i=1xμ(i)⌊xi2⌋\sum_{i=1}^{\sqrt{x}} \mu(i)\lfloor\frac{x}{i^2}\rfloori=1∑xμ(i...
2019-01-02 21:29:00
275
原创 BZOJ 2154 Crash的数字表格 BZOJ 2693 jzptab
题目链接https://lydsy.com/JudgeOnline/problem.php?id=2154https://lydsy.com/JudgeOnline/problem.php?id=2693题解∑i=1n∑j=1mlcm(i,j)=∑i=1n∑j=1mijgcd(i,j)=∑T=1min(n,m)S(⌊nT⌋,⌊mT⌋)T∑d∣Tμ(d)d\begin{aligned}...
2019-01-02 21:25:19
207
原创 BZOJ 2005 [Noi2010]能量采集
题目链接https://lydsy.com/JudgeOnline/problem.php?id=2005题解容易发现，植物(x,y)(x,y)(x,y)和机器之间的连线上植物的数量就是gcd(x,y)\gcd(x,y)gcd(x,y)。因此答案就是∑i=1n∑j=1m(2gcd(i,j)−1)=2∑i=1n∑j=1mgcd(i,j)−nm\begin{aligned}&...
2019-01-02 20:45:35
191
原创 BZOJ 5467 [PKUWC2018]Slay the Spire
题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=5467题解容易发现，强化牌和攻击牌按大的出，只要能出强化牌就出强化牌是最优策略。首先将两种牌按权值排序，设fi,jf_{i,j}fi,j表示前iii张强化牌取到jjj张，必定取到第iii张能打出的最大强化值之和，gi,jg_{i,j}gi,j表示前iii张攻击牌取到jjj张，必定...
2018-12-28 14:29:25
195
原创 BZOJ 5461 [PKUWC2018]Minimax
题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=5461题解线段树合并，线段树每个区间[l,r][l,r][l,r]代表取到第lll小到第rrr小的权值的概率，对于每一个节点，线段树由两个端点合并，容易发现在点uuu，对于第iii小的权值，假设这个权值是由左儿子贡献而来，取到这个权值的概率是fu,i=fls,i(∑j&lt;...
2018-12-28 12:03:09
229
原创 BZOJ 4364 [IOI2014]wall砖墙
题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=4364题解线段树维护，每个点记录一个[l,r][l,r][l,r]，代表当前需要被修改成[l,r][l,r][l,r]高度。下传很好做，最后查询叶子节点的lll即可。代码#include <cstdio> int read(){ int x=0,f=1; ...
2018-12-28 11:55:40
192
原创 BZOJ 3812 主旋律
题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=3812题解考虑求非强连通子图的数量，假设为ggg，那么答案就是2m−g2^m-g2m−g。现在考虑求ggg。假设fsf_sfs表示用sss这些点能构成的强连通图的个数，gsg_sgs表示用sss这些点能构成的非强连通图的方案数，其中构成iii个强连通分量则对gsg_sgs的贡献...
2018-12-28 11:44:00
141
原创 agc017D Game on Tree
题目链接https://agc017.contest.atcoder.jp/tasks/agc017_d题意简述现在有一棵树，Alice和Bob要玩一个游戏。Alice先手，他们轮流断开树上的一条边，并将不与111连接的连通块删去。如果轮到一个人操作时只剩一个点则判他负。问是否存在先手必胜策略。题解SG(i)=xor(SG(son)+1)SG(i)=xor(SG(son)+1)SG(...
2018-12-15 16:16:41
283
原创 agc019F Yes or No
题目链接https://agc019.contest.atcoder.jp/tasks/agc019_f题意简述有n+mn+mn+m个问题，答案都是"Yes"或"No"，其中nnn个是"Yes"，mmm个是"No"。你回答一个问题后，不管是否正确，都可以得到这个问题的答案。假设你都不知道答案只能猜，按最有策略行动，求你期望答对问题的个数。题解容易得到一个O(n2)O(n^2)O(n2)的...
2018-12-15 16:10:33
153
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人