2019-09-19 17:13 算法工程师

关注

操作数解题报告

操作数

http://www.nowcoder.com/questionTerminal/966fde4871834ceeadbfc2122b76257a

这一题确实有一定的思维难度

首先观察到k的范围，显然不能用朴素方法求解。

同时我们注意到每个数都等于它的前缀和

所以我们可以构造如下矩阵：

1 1 1 ... 1
0 1 1 ... 1
0 0 1 ... 1
...........
0 0 0 0...1

也就是说，我们只要让原数列 $[a_1,a_2,a_3,a_4,...,a_n]$ 乘上上面那个矩阵，就能得到 $s$ 序列

经过 $k$ 次操作之后就能得到结果

即我们要求的结果等于

$[a_1,a_2,a_3,a_4,\cdots,a_n] \times \left[ \matrix { 1 & 1 & 1 & \cdots & 1 \\ 0 & 1 & 1 & \cdots & 1 \\ 0 & 0 & 1 & \cdots & 1 \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ 0 & 0 & 0 & \cdots &1 }\right]^k$

然后怎么快速求的矩阵乘呢?

矩阵快速幂？ $N^3\log k$

复杂度承受不了

那么我们手推一下

假设是一个 $3 \times 3$ 的矩阵

就有

$\left[ \matrix { 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ }\right] \times\left[ \matrix { 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ }\right] =\left[ \matrix { 1 & 2 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \\ }\right]$

$\left[ \matrix { 1 & 2 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \\ }\right] \times\left[ \matrix { 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ }\right] =\left[ \matrix { 1 & 3 & 6 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \\ }\right]$

$\left[ \matrix { 1 & 3 & 6 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \\ }\right] \times\left[ \matrix { 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ }\right] =\left[ \matrix { 1 & 4 & 10 \\ 0 & 1 & 4 \\ 0 & 0 & 1 \\ }\right]$

怎么感觉哪里这么眼熟？

我们把杨辉三角写下来康康

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5  10 10 5  1

注意到了吗？杨辉三角的第二列，第三列，第四列

前三个对应的就是结果矩阵的第一行

我们再看看 $4 \times 4$ 的

$\left[ \matrix { 1 & 2 & 3 & 4\\ 0 & 1 & 2 & 3\\ 0 & 0 & 1 & 2\\ 0 & 0 & 0 & 1\\ }\right] \times\left[ \matrix { 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1\\ }\right] =\left[ \matrix { 1 & 3 & 6 & 10\\ 0 & 1 & 3 & 6\\ 0 & 0 & 1 & 3\\ 0 & 0 & 0 & 1\\ }\right]$

那么，我们就可以大胆的推测如下结论，初始矩阵的 $k$ 次对应的就是杨辉三角的第 $k$ 列的前 $n$ 个

然后我们知道杨辉三角是和组合数一一对应的，第 $i$ 行第 $j$ 个表示 $C_{i-1}^{j-1}$

但是这样做还是会有一个问题，就是在求组合数的时候复杂度会承受不了，而且分别求分子分母取模的做法会导致Wrong Answer

只要对杨辉三角有一定了解的同学就一定知道，第 $i$ 列的数字和从第 $i$ 行第一个向右下取得数字是一样的

那这个就可以很方便的求出来了， $C^m_n=\frac{n!}{m!(n-m)!}$ ,我们的 $n$ 和 $m$ 是同时增加的，所以 $(n-m)!$ 不变，只需要处理一下每一个位置对应的 $n$ 和 $m$ 即可

只要处理出第一行即可

全部评论

推荐最新楼层

05-26 21:00

研发工程师

听说研究生就业难于本科生？

本文首发自「林行学长」，欢迎来撩。了解校招、分享校招知识的学长来了！今天学长看到一条关于研究生就业难于本科生的热搜，真的会感叹：研究生已经这么难了吗？虽然近两年就业情况不太乐观，但是大家都认为：硕士找工作怎么也比本科容易吧。但是，研究生和本科生的就业，它各有各的难啊！01 本科生就业的轻松还是难？从公布的数据来看，好像本科生就业率还挺高。然而，这并不意味着本科生的就业就一定轻松。毕竟，本科生毕业人数一年比一年多，企业能开放的岗位却是有限的。本科生就业的轻松与否也与专业的选择和个人能力密切相关。不可否认的是一些热门专业的毕业生，往往可以迅速地找到让自己满意的 Offer。此外，个人的实际能力、经...

想实习转正，又想准备秋招，我该怎么办

点赞评论收藏

转发

渴望wlb啊啊啊啊啊

05-22 08:40

西安电子科技大学机械类

分享下在比亚迪实习的感受

工作氛围还可以，工作时间是早上八点半到下午五点半，一般不需要加班，除非你愿意加班拿加班工资。员工大多比较年轻，领导也比较平易近人，感觉人与人之间比较平等。餐厅的食物还可以，价格比外面便宜，比学校贵一点。宿舍是四人间，现在住了两人，宿舍楼里有洗衣机，听说正式员工在外租房还有1k的补贴，周边租房也比较便宜。另外，新开了健身房，设施也挺全的，免费预约开放给员工使用。但是有一点不太方便的是，做任何事情都需要提交流程，办公区不能自带电脑也不能连接外网，只能在手机上操作，有些不太方便。总的来说，比亚迪给我的感受还是比较不错的。

投递比亚迪精密制造等公司6个岗位 >

点赞评论收藏

转发

不愿透露姓名的神秘牛友

05-27 11:41

已编辑

各位留学生们还继续么？

点赞评论收藏

转发

升级打怪的NPC

05-24 01:08

已编辑

河南财政金融学院金融学类

我是有什么问题？为什么有点名气的企业销售都不要我？

投的各个知名企业销售岗几乎都挂了，小企业都是电销加地推，一个月3000底薪左右，而且都是单休，现在不知道该怎么办了

点赞评论收藏

转发

5 收藏评论

全站热榜

正在热议

# 和牛牛一起刷题打卡 #

4525次浏览 428人参与

# 机械制造薪资爆料 #

340920次浏览 4044人参与

# 牛客帮帮团来啦！有问必答 #

983266次浏览 15247人参与

# 通信硬件薪资爆料 #

242003次浏览 2282人参与

# 腾讯工作体验 #

146356次浏览 1405人参与

# 如何写一份好简历 #

300774次浏览 4324人参与

# 实习必须要去大厂吗？ #

18076次浏览 265人参与

# 你的简历改到第几版了 #

323179次浏览 4856人参与

# 晒一晒我的offer #

3650850次浏览 56923人参与

# 2022毕业生求职现身说法 #

20430次浏览 310人参与

# 毕业租房也有小确幸 #

31954次浏览 1834人参与

# 产品人专业大盘点 #

15082次浏览 120人参与

# 浅聊一下我实习的辛苦费 #

93348次浏览 916人参与

# 为什么国企只招应届生 #

56071次浏览 411人参与

# 视觉/交互/设计岗位评价 #

3356次浏览 59人参与

# 双非本科求职如何逆袭 #

224686次浏览 3291人参与

# 你觉得机械有必要实习吗 #

10111次浏览 132人参与

# 为什么那么多公司毁约 #

54859次浏览 485人参与

# 在国企工作的人，躺平了吗？ #

105418次浏览 1335人参与

# 来选选带哪个offer回家过年 #

185309次浏览 1773人参与

牛客网
牛客企业服务