2020-10-29 09:42 天津大学 C++

关注

k阶差分与前缀和

K阶前缀和

$B_i = \sum_{j = 0}^{j\le i} A_j$ 这是我们对前缀和的定义。而 $k$ 阶前缀和就是把这个过程进行 $k$ 次。那么考虑卷积。 $B_i = \sum_{j=0}^{j\le i} A_j$ 其实可以看作 $B_i = \sum_{j = 0} ^ {j \le i} A_{j} C_{i-j}$ 而 $C_{i}=1$ 。 $C(x)$ 是一个所有项都为 $1$ 的函数。那么 $B = A * C$ 。由于卷积是有结合率的，所有 $K$ 阶前缀和等同于 $B = A*C^k$ 。而对于 $C^k$ 的计算，可以采用多项式快速幂，但没必要。我们有生成函数 $F(x)=\sum_{i=0}^{\infty} x ^i = \frac{1}{1-x}$ ，那么 $C^k$ 的生成函数为 $\frac{1}{(1-x)^k}$ 而 $[x^n]\frac{1}{(1-x)^k} = {n + k - 1 \choose k - 1}$ 。这个可以通过数学归纳法证明。最后就做一次卷积就可以了。

K阶差分

$B_i = A_i - A_{i-1}$ 那么 $B_i = A_i - A_{i-1}$ 也可以卷积 $B_{i} = \sum_{j=0} C_j A_{i-j}$ 其中 $C_0 = 1,C_1 = -1,C_i= 0$ 。那么 $C(x)$ 的生成函数为 $F(x) = 1-x$ 。那么进行 $k$ 次操作之后 $C(x)^k$ 的生成函数为 $(1-x)^k$ 那么 $(1-x)^k = \sum_{i=0}^{k} (-1) ^i{k\choose i} x^i\Rightarrow [x^n](1-x)^k = (-1)^i {k\choose i}$ 。卷积一下就做完了。

分析

不管是差分还是前缀和其实我们都可以 $\ln + \exp$ 就可以了，更加无脑一点，时间复杂度也是 $O(n\log n)$ 。

数学文章被收录于专栏

关于多项式

全部评论

推荐最新楼层

C++

QwQ，不会

1 回复分享

发布于 2020-10-29 10:05

杭州文澜中学

orz

点赞回复分享

发布于 2023-08-08 12:53 浙江

11-22 18:35

南京审计大学金审学院审计

辞退了很喜欢的实习生，总结他3个“雷点”

实习生的“雷区”：那些你需要避开的坑最近我不得不辞退了一位实习生，虽然他很努力，也很会说话，但有些行为实在让人无法忍受。总结了他的几个“雷区”，希望大家引以为戒。1. 上班摸鱼可以，但别太嚣张大家都知道，上班时间玩手机属于“摸鱼”，但摸鱼也要有个度。这位实习生的工位就在我旁边，背后是老板。他居然敢翘着二郎腿，懒洋洋地靠在椅背上，手机举到肩膀高度，玩得不亦乐乎。你说，这是不是有点太嚣张了？摸鱼可以，但别让领导和老板看得一清二楚啊！2. 犯错不可怕，但要敢于承认工作中犯错是难免的，关键是要及时补救和复盘，避免再犯。这位实习生经常算错数据，商品价格也会搞错，交代的工作没有后续进展。更让人无语的是，他...

点赞评论收藏

分享

11-25 00:45

安徽理工大学 Java

寒假实习到底什么时候开始找呢？

我是一名25届的求职者，秋招至今没有拿到一个offer，反思自己，或许是因为缺乏实习经历。于是，我决定暂停秋招，利用寒假时间来补充一下自己的履历。真心希望有经验的朋友们能给我一些建议，告诉我该在何时开始寻找寒假实习机会！

牛客创作赏金赛

点赞评论收藏

分享

10-11 21:03

西安电子科技大学测试工程师

孩子们，穿梭回国庆前了

有工作后先养猫：太好了，是超时空战警，我们有救了😋

点赞评论收藏

分享

11-13 15:20

门头沟学院前端工程师

麻麻我出息了

我也是能硬气到拒bytedance了😇

死在JAVA的王小美：哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈，我也是，让我免了一轮，但是硬气拒绝了

点赞评论收藏

分享

昨天 22:52

厦门大学 Java

26届日常实习求大佬指点拷打

之前做过黑马点评，学技术栈的时候做的，感觉做得稀里糊涂所以就没写到简历上。目前简历上只写了一个项目（还没做完，应该在年内做完），寒假的时候可以再做第二个项目，但是现在再考虑要不要做。打算是寒假再背一下面经（Redis之后的还没背），然后投递如果只做一个项目的话，投日常实习有竞争力吗？如果简历有不合理的地方，欢迎大家指出！

我的实习日记简历被挂麻了，求建议

点赞评论收藏

分享

5 1 评论

全站热榜

正在热议

# 25届秋招总结 #

355623次浏览 3475人参与

# 我的实习求职记录 #

6088357次浏览 83708人参与

# 阿里云管培生offer #

42428次浏览 965人参与

# 地方国企笔面经互助 #

5300次浏览 13人参与

# 职场吐槽大会 #

90861次浏览 752人参与

# 选完offer后，你后悔学本专业吗 #

23094次浏览 165人参与

# 北方华创开奖 #

50296次浏览 451人参与

# ai智能作图 #

4160次浏览 78人参与

# 运营商笔面经互助 #

92874次浏览 1336人参与

# 实习中的菜狗时刻 #

278992次浏览 2741人参与

# 腾讯求职进展汇总 #

200632次浏览 1666人参与

# 如果有时光机，你最想去到哪个年纪？ #

25075次浏览 519人参与

# 当下环境，你会继续卷互联网，还是看其他行业机会 #

37863次浏览 345人参与

# 风评不好的公司，你会去吗？ #

20763次浏览 94人参与

# 上班苦还是上学苦呢？ #

91552次浏览 797人参与

# 大疆求职进展汇总 #

413850次浏览 2934人参与

# 国企还是互联网，你怎么选？ #

90230次浏览 703人参与

# 硬件兄弟们甩出你的华为奖状 #

73864次浏览 609人参与

# 远程面试的尴尬瞬间 #

20588次浏览 296人参与

# 软件开发2024笔面经 #

2326214次浏览 48226人参与

# 如果中了500万，你会离职吗？ #

13764次浏览 145人参与

# 如何一边实习一边秋招 #

1000343次浏览 12701人参与

牛客网
牛客企业服务