无    2018-07-12 20:33:03    127    0    0
好像每一篇博客都要在前面写点东西?
但但但但是这次我也不知道该写什么QAQ

欠了好久的东西QAQ
写着写着越发感觉从前写的那篇FFT是个什么傻逼玩意儿......
没有关系打开编辑界面就不会想重新写了


Fast Walsh Transform

(应该是这么写的吧)
用来在O(nlogn)的复杂度内求解这样的卷积运算:

Ck=ij=kAiBj

从Fast Fourier Transform谈起

OI中的FFT利用点值表达式和单位根的性质将卷积转化成这样的形式:

DFT(C)=DFT(A)DFT(B)

DFT是有自己的定义式的:

SF^[k]=n=0N1SF[n]e2πinkN

也就是说

无    2018-07-11 17:24:49    192    0    0
来骗个访问量QAQ

像名字一样,本篇讨论(摘抄)的是理论复杂度为O(nlogn)实际上跑得很慢的求多项式

f(x)=i0aixi

K次幂/K次方根的算法。

前置技能

不会FFT的去学。
不会多项式逆元的去学。
不会泰勒展开的去背。

对数函数的计算

B(x)=ln(A(x))

根据复合函数的求导,有:

B(x)=A(x)A(x)

指数函数的计算

f(x)=eA(x),则:

g(f(x))=ln(f(x))A(x)=0

考虑用牛顿迭代法解此方程。常数项是容易确定的。

无    2018-07-11 17:24:47    136    0    0

同机房神犇

  • KB    HN高一女队钦定集训队爷
  • XZY&&ABS    两位大佬的博客&&机房聚集地
  • Menhera    社会主义市场经济新根据地
  • Orang_cc    dalao×1
  • Chlience    dalao×2
  • Dimitry_L    dalao×3
  • WilliamPon    dalao×4
  • And WTX    
无    2018-07-11 17:24:43    48    0    0
一个已经废掉了的咸鱼终于开始学几百年没有碰过的新姿势了233333(貌似这个不算新姿势欸)
不会写博客
将就看吧QAQ

首先,让我们花一秒钟时间记下它的全名:扩展埃拉托色尼筛法(记住了也没用,不如搜Min_25筛)
网上说这就是个写得好点的洲阁筛然而我是不会洲阁筛的

Min25筛用于求一类积性函数的前缀和,不过限制条件比毒教筛宽多了。
只需要满足:

f(n)={1n=1g(p,e)n=pe,e>0f(x)f(y)(x,y=1)

其中g(p,0)是一个关于p的能快速求出的多项式,且f(pk)也能快速转移。

首先对于每一个xni(最多有2n个不同的取值)维护这玩意儿:i=1xik(iPrime)
我们可以这样求:枚举素数pn

无    2018-07-11 17:24:36    164    0    0
终于整完了QAQ
队爷0.5h AK然而蒟蒻要花(N+1) hours勉强明白

肯定是有很多错误的,欢迎指正QAQ
那还是欢迎线上/线下dd吧。



[A] 打怪

n个怪物,第i个怪物的血量是ai,设这n个怪物组成的集合为T。
现在你有一个技能,发动一次需要花费一个金币,当技能发动后,所有存活的怪物的血量都会1,当怪物血量降为0后视为被消灭。
特别的,如果这次发动的技能后有至少一只怪物死亡,你都将获得一个金币的奖励。
f(S)为消灭集合S中的怪物总共需要付出几个金币,即花费的金币数量减去获得的奖励金币数量。
STf(S),答案对109+7取模。
1n105,1ai109


消灭掉一个集合S内的怪物需要花费的金币为

无    2018-07-11 17:24:33    70    0    0

寻宝游戏

毛:我我我我是不是出得太简单了???
HNOI有没有比这更简单的题啊??

单独考虑一个询问,如果这一位是1,那么最后一个|1必须在&0后面,反之在前面。
&看成1|看成0,第i位的数字表示第i个串前的运算符号。
将第i位的数字提取出来,则使这一位为1的所有运算符的01串的字典序小于这一位的数字构成的字典序。
于是我们处理一下每一位01串的字典序判断一下有没有解计算一下有多少解就好了
(表面笑嘻嘻内心mmp.jpg)


转盘

有一个显然也不显然的的结论:答案一定是在某一点时待到它出现然后一路走到底。因为每个点总不会遛两遍,否则可以从它开始;那么走到一个点总是要等它出现,这跟等其中最晚的那个点出现是等价的。
所以我们是在求Mini=1N{Maxj=ii+N1(Tjj+i+N1)}
等价于

无    2018-07-11 17:24:28    155    0    0
我我我我更完了

链上二次求和

有一条长度为n的链(1i<n,点i与点i+1之间有一条边的无向图),每个点有一个整数权值,第i个点的权值是ai。现在有m个操作,每个操作如下:
操作1(修改):给定链上两个节点u,v和一个整数d,表示将链上uv唯一的简单路径上每个点权值都加上d
操作2(询问):给定两个正整数L,r,表示求链上所有节点个数大于等于L且小于等于r的简单路径节点权值和之和。
由于答案很大,只用输出对质数1000000007取模的结果即可。
一条节点个数为k的简单路径节点权值和为这条上所有k个节点(包括端点)的权值之和,而本题中要求是对所有满足要求的简单路径,求这一权值和的和。
由于是无向图,路径也是无向的,即点1到点2的路径与点2到点1的路径是同一条,不要重复计算。


题目不是把题解告诉你了吗......
Sk表示k阶前缀和,则:

Ans====i=LRj=iNS1[j]S1[ji]i=LR(j=iNS1[j]j=0NiS1[j])i=LR(S2[N]S2[i1]S2[Ni])(R+L1)S2[N]i=L1R1S2[i]i=NRNLS2[Ni]

考虑修改:
对于LiRadd=(iL+1)(iL+2)2v
对于R<iNadd=(RL+1)(RL+2)2v+(iR)(RL+1)v
明明就不卡常~\(≧▽≦)/~成功rank7


治疗之雨

你现在有m+1个数:第一个为p,最小值为0,最大值为n;剩下m个都是无穷,没有最小值或最大值。
你可以进行任意多轮操作,每轮操作如下:
在不为最大值的数中等概率随机选择一个(如果没有则不操作),把它加一;
进行k次这个步骤:在不为最小值的数中等概率随机选择一个

无    2018-07-11 17:24:26    306    0    0

哎呀更新好麻烦啊不想更新了。
如果对您有一点点帮助的话就再好不过了。
我才不欢迎监督呢,一点都不谢谢。


BZOJ1001

ST之间连一条边,划分出对偶图中的源汇点,建出此平面图的对偶图。此时平面图中的最小割等价于对偶图中的最短路。


BZOJ1002

矩阵树定理:对角矩阵D定义为:Di,i为节点i的度数,其它位置为0。矩阵CD减去图G的邻接矩阵。矩阵C去掉第r行第r列后的行列式即为图G的生成树个数。
不过这题会被卡精度。我们手写矩阵C然后手推发现满足递推式fn=3×fn1fn2+2。高精度就好。


BZOJ1003

预处理出Cosi,j表示第i天到第j天的最短路长度,于是显然有

无    2018-07-11 17:24:24    143    0    0

由于博主们(?)都很良心没有扯杂七杂八的东西,所以我也不啰嗦了。

标注[1]:后缀数组图片支持来自于[这位大佬]

标注[2]:基数排序图片支持来自于[这位大佬]

基数排序

大佬请跳过。
是一种稳定的、Θ(n)级别的排序方式,这年头极好用的。
现有一组数据:73,14,81,22,55,65,43,28,39,93
我们首先只按照个位数进行桶排序,并相应记录下标,仍然得到一个无序数列。

图片标题

然后在此次的基础上只考虑十位数进行排序。我们发现这成了一个有序数列!

图片标题

依次类推,如果有百位数、千位数,同样排序至最高位。

  • 显然也可以从高位排起。

实现

所谓SA

有必要在开头就阐明的东西:

  • SA(Suffix Array)数组:排名为i的后缀是[SA[i],n)
  • Rank数组:[i,n)后缀的排名为i(求的过程中直接离散化)

所谓后缀数组就是指SA,由于SARank的反函数,所以任意得到一个都可以在Θ(n)的时间内得到第二个。

先展示代码如下:

  1. inline int cmp(int *f,int x,int y,int w) {return f[x]==f[y]&&f[x+w]
无    2018-07-11 17:24:23    10    0    0
一朝为叶,终生为叶。

标注[1]:文中图片与行文思路主要来自于[这位大佬]
标注[2]:文中有部分(一点点)参考[这位大佬]

起源

后缀树的概念是在1973P.Winter的一篇叫做"Liner  Pattern  Matching  Algorithm"的文章中第一次被提出,当时这篇文章把这种数据结构叫做"Position Tree"
该算法能够在线性时间内构建后缀树,这个算法还被Donald Knuth称为“1973年度算法”,足以见其重要性。几年之后,Edward M.McCreight介绍了另外一种不同的线性算法,这种新算法更加节省空间,可以说是对原来算法的大幅优化。1995年,E. Ukkonen在此基础上提出了第一个能在线

1/2