无    2018-08-18 15:18:46    189    0    0
人傻有救吗QAQ
-没有,建议弃疗。

我发现我好像会口胡证明


常系数齐次递推

给出递推式hi=j=1mpjhij,求hn


矩阵快速幂

根据递推式构造矩阵然后用O(m3log2n)的复杂度解决问题。相信大家都会。
Hi={hi,hi+1,...,hi+k1},则hnHnk+1的最后一项。
Hnk+1=H0Mnk+1,其中

无    2018-08-14 21:51:00    265    0    0
orz myy and ZZQ

(其实在今天之前我从来没有听说过这玩意儿只是翻阅论文的时候有毛爷爷引进过一个没有中文资料的黑科技的印象)
我发现我好像会口胡证明这个神仙算法的正确性了?
不过这里空间太小,写不下。还是不写了吧。

Berlekamp-Massey算法

也简记为BM算法(不是字符串匹配那个BM算法!)。用于在已知一组长度为n的数列项时求出此数列的最短线性递推式.显然已知的项数越多结果越准确。

线性递推式的定义

对一个数列(x1,x2,...,xn1,xn),存在一组数列(p1,p2,...,pm1,pm),使得xi(m+1in),有xi=j=1mpjxij.则称其为数列(x1,x2,...,xn1,xn)的一种线性递推式.如果m是最小的,则称其为最短线性递推式。

Berlekamp-Massey算法运行过程

这没有办法,毕竟

无    2018-07-12 20:33:03    168    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    206    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    173    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    118    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    178    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    112    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    170    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    344    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天的最短路长度,于是显然有

1/2