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$ 即可

只要处理出第一行即可

全部评论

推荐最新楼层

02-12 14:41

已编辑

腾讯_前端实习生(实习员工)

腾讯云智校招礼盒

云智校招礼盒，看着还不错的样子来云智实习也快8个月了，收获了满满

点赞评论收藏

分享

02-13 22:30

门头沟学院 Web前端

美团到餐一面

一开始他先介绍了他那边的业务，然后让我介绍下自己的经历和技术难点。针对经历：1、问项目规模，有没有自己写一些大的需求，自己写方案去做的2、过往的需求中有没有那种复杂的3、中间提到了节流，他就问我防抖和节流的代码层面是如何实现的针对项目Agent相关的：1、是否支持图片2、对于用户输入的Prompt有没有进行调优3、单次会话还是多次对话的展示4、系统设定模型的角色，是在前端还是后端写的5、有没有出现一些幻觉Vue相关1、vue怎么样实现数据绑定到组件上以及视图变化数据的更新2、如果有一个数据，关联了多个组件，这些组件是怎么样去实现挨个通知的手写代码核心点在于借助AI的工具给做出来，说因为这个题目...

查看24道真题和解析

点赞评论收藏

分享

01-06 09:44

深圳职业技术学院护士

双非老鼠的悲惨秋招

老粉都知道小猪猪我很久没更新了，因为秋招非常非常不顺利，emo了三个月了，接下来说一下我的情况吧本人是双非本 专业是完全不着计算机边的非科班，比较有优势的是有两段大厂实习，美团和字节。秋招面了50+场泡池子泡死的：滴滴 快手 去哪儿 小鹏汽车 不知名的一两个小厂其中字节13场 两次3面挂 两次2面挂 一次一面挂其中有2场面试题没写出来，其他的都是全a，但该挂还是挂，第三次三面才面进去字节，秋招加暑期总共面了22次字节，在字节的面评可以出成书了快手面了8场，2次实习的，通过了但没去，一次2面挂 最后一次到录用评估 至今无消息滴滴三面完 没几天挂了 所有技术面找不出2个问题是我回答不上来的，三面还来说我去过字节，应该不会考虑滴滴吧，直接给我干傻了去哪儿一天速通 至今无消息小鹏汽车hr 至今无消息美团2面挂 然后不捞我了，三个志愿全部结束，估计被卡学历了虾皮二面挂 这个是我菜，面试官太牛逼了拼多多二面挂 3道题也全写了 也没问题是回答不出来的 泡一周后挂腾讯面了5次 一次2面挂 三次一面挂，我宣布腾讯是世界上最难进的互联网公司然后还有一些零零散散的中小厂，但是数量比较少，约面大多数都是大厂。整体的战况非常惨烈，面试机会少，就算面过了也需要和各路神仙横向对比，很多次我都是那个被比下去的人，不过这也正常，毕竟谁会放着一个985的硕士不招，反而去招一个双非读化学的小子感觉现在互联网对学历的要求越来越高了，不仅仅要985还要硕士了，双非几乎没啥生存空间了，我感觉未来几年双非想要进大厂开发的难度应该直线上升了，唯一的打法还是从大二刷实习，然后苟个转正，不然要是去秋招大概率是炮灰。而且就我面字节这么多次，已经开始问很多ai的东西了，你一破本科生要是没实习没科研懂什么ai啊，纯纯白给了

不知名牛友_：爸爸

秋招你被哪家公司挂了?

点赞评论收藏

分享

01-20 17:41

浪潮集团_全栈开发(实习员工)

xdm浪潮发暗影精灵

浅白lw：其实是牛马自己换马了

点赞评论收藏

分享

02-08 14:16

门头沟学院 Java

字节大模型测开一面

拷打实习经历怎么理解 ReAct 框架，它的工作原理是啥样的？你用过 ReAct 吗？ReAct 里面关键是什么呢？怎么比别人做的好，核心要在哪个方向重点学习？MCP 和 Function Call 有什么区别？Transformers 你了解吗？你现在的工作没做过微调对吧？你觉得微调的原理是什么？RAG 和微调有什么区别？复杂的 Agent 层（多个 Agent 组成、多模块）怎么去评测？

查看10道真题和解析

点赞评论收藏

分享

评论

5

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 春招什么时候投？ #

11454次浏览 189人参与

# 牛友的春节生活 #

8808次浏览 173人参与

# 春节前，你还在投简历吗？ #

15251次浏览 178人参与

# 备战春招/暑实，现在应该做什么？ #

5845次浏览 173人参与

# 牛客AI体验站 #

15088次浏览 268人参与

# 从夯到拉，锐评职场mentor #

5791次浏览 88人参与

# 实习到现在，你最困惑的一个问题 #

5073次浏览 143人参与

# 春节提前走，你用什么理由请假？ #

11397次浏览 262人参与

# 距离春招还有一个月，你现在是什么开局？ #

7728次浏览 121人参与

# 今年秋招你收到了多少封邮件？ #

37868次浏览 279人参与

# 暑期实习什么时候投？ #

7873次浏览 181人参与

# 聊聊Agent开发 #

26890次浏览 626人参与

# 机械制造面试记录 #

314152次浏览 3159人参与

# 如何看待offer收割机的行为 #

1038168次浏览 6595人参与

# 推荐一个值得做的AI项目 #

7396次浏览 186人参与

# 非技术投递记录 #

691544次浏览 6857人参与

# 2025，我想...... #

88205次浏览 668人参与

# 找工作，行业重要还是岗位重要？ #

96568次浏览 1839人参与

# 我的AI电子员工 #

28362次浏览 192人参与

# 一起聊华为 #

191878次浏览 895人参与

牛客网
牛客网在线编程
牛客网题解
牛客企业服务