3 wang3312362136

尚未进行身份认证

暂无相关简介

等级
TA的排名 1w+

多项式全家桶——炫酷多项式变换

文章目录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

PKUWC2019游记

100+12+0+48+12+47=228数学11或者21NOIP炸了,打不过,告辞

2019-01-25 14:19:43

路径压缩优化并查集的时间复杂度

路径压缩优化并查集大家一定很熟练了,那么它的复杂度是多少呢?O(mα(n))O(m\alpha(n))O(mα(n))?的确,很多人都是这么说的,但是事实上它的复杂度是O(mlog⁡1+m/nn)O(m\log_{1+m/n}n)O(mlog1+m/n​n)的,并且能找到一种方法卡到这样的复杂度。要卡并查集,首先要构造一种树——二项树。这种二项树还与普通的不太一样。定义:在给定jjj的情况下...

2019-01-14 12:12:20

支配树与Lengauer-Tarjan算法

伪目录给出支配树的定义给出一些性质介绍快速构造支配树的Lengauer-Tarjan算法及具体实现支配树是啥一个有源点的有向图,其支配树是满足下面条件的一个有向图:对于支配树上一点,若断开此点,则源点必定不能到达它的任何儿子,并且能到达其他任意一个点。不显然的,它是一棵树(当然后面会有证明)支配树有很多实际用途,我都不知道。一些性质对于一个有向图,假设源点为rrr,先从rr...

2019-01-14 11:33:44

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

莫比乌斯反演+杜教筛 题表

“入门”难度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

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

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

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

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

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

一个多项式求逆的卡常技巧

假设在 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

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

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

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

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

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

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

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

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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!