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

只要处理出第一行即可

全部评论

推荐最新楼层

11-27 20:18

哈尔滨理工大学算法工程师

过滤文章中空格

开始我怎么想也想不出解决办法，后来查阅了资料。了解到cin不是只以回车结束，空格的话也会，并且每次只读取数据，不读取空格；所以就相当于把每次输入的内容先分开，然后再人为的加上空格即可 #include<iostream> using namespace std; char st[200]; int main(){ while (cin>>st) cout<<st<<" "; return 0; }

点赞评论收藏

分享

11-25 15:40

重庆理工大学汽车电子工程师

比亚迪工作体验

工作环境是个大平层，里面大概有两百来人，虽然有点吵，但气氛很活跃。大家可以随意布置自己的工位，也不用穿工服，年轻人特别多，过道上还有小桌子和大屏幕，随时可以开小会。宿舍是富士锦园，双人间600一个月，离上班地方也就十分钟，挺不错的。我早上会去食堂吃早餐，种类多味道也不错，像大学食堂。领导也特别好，带教导师漂亮又温柔。打卡方式也很人性化，手机定位打卡，只要在园区里就能打，随时都能提前走。

比亚迪成长空间 168人发布

点赞评论收藏

分享

10-16 11:41

武汉理工大学机械设计/制造

长江存储HR就这素质？笑辣

我寻思我前后发言已经很委婉尊重了吧，你offer都没发到我手就在这给我上强度呢？长江存储这么吊的哦，奉劝大家避雷这样的公司，对未入职的都这个态度，对签了牛马合同的还不知道会怎么样呢🤭

剑指延毕：双向选择不用那么客气卑微骂回去

点赞评论收藏

分享

昨天 19:02

电子科技大学硬件开发

这是不是寄了呀

投递华为等公司10个岗位

点赞评论收藏

分享

11-25 16:10

山东大学电气设计工程师

入职国家电网的体验

工作时间是早上9点到下午4点半，但很多同事都在公司待到6点，因为5点开饭，6点有一趟班车。说到加班，确实有，但一年也就那么一小段时间，基本上只有一个月需要加班，而且加班后还能调休，挺人性化的。工作压力嘛，基本上不大。总的来说，国家电网的工作氛围还不错，大家都比较随意，没什么太多的压力

国家电网工作强度 101人发布

点赞评论收藏

分享

评论

5

收藏

全站热榜

正在热议

# 拼多多求职进展汇总 #

238124次浏览 2040人参与

# ai智能作图 #

30556次浏览 366人参与

# 北方华创开奖 #

67310次浏览 554人参与

# 25届秋招总结 #

414450次浏览 4160人参与

# 实习，投递多份简历没人回复怎么办 #

2442216次浏览 34752人参与

# 地方国企笔面经互助 #

7083次浏览 17人参与

# 阿里云管培生offer #

63374次浏览 1764人参与

# 我在牛爱网找对象 #

74967次浏览 556人参与

# 虾皮求职进展汇总 #

94418次浏览 766人参与

# 机械求职避坑tips #

23846次浏览 249人参与

# 发工资后，你做的第一件事是什么 #

9563次浏览 43人参与

# 我的实习求职记录 #

6136503次浏览 84036人参与

# 25届机械人为了秋招做了哪些准备？ #

26469次浏览 363人参与

# 投格力的你，拿到offer了吗？ #

47535次浏览 337人参与

# 机械人怎么评价今年的华为 #

158105次浏览 1353人参与

# 华为工作体验 #

111933次浏览 867人参与

# 实习想申请秋招offer，能不能argue薪资 #

36450次浏览 310人参与

# 如果再来一次，你还会选择这个工作吗？ #

116840次浏览 1148人参与

# 国央企笔面经互助 #

88653次浏览 897人参与

# 在职场上，你最讨厌什么样的同事 #

6242次浏览 92人参与

# 产运销实习日记 #

28287次浏览 326人参与

# 软件开发投递记录 #

1482305次浏览 23949人参与

牛客网
牛客企业服务