逆序对

有两种方法理解，但结论都是一样的f(n) = 2^(n-3) * n * (n-1)，这里只写一种，另一种就是大佬们的组合数学，前面很多人写，这里就不赘述

我们很容易知道f(n)的数值可分为两方面

一：f(n-1)也就是上一个的个数，因为其实就是在n-1的基础上在其前面加0或1，也就说原来的次数就变成了2倍，也就是2*f(n-1)

二：在n-1的前面新加一个1产生的影响，不难发现就是n-1的所有的0的个数，设为g(n-1)

g(n) = n*2^(n-1), 就是所有串1和0的总和除以2.

这里就可以推出来f(n) = g(n-1) + 2*f(n-2)，大部分人都可以推到这一步，其实再展开一下就行了

下面是我手推的

图片说明

全部评论

相关推荐

05-28 10:42
已编辑
华为_HR
华为OD机考386分教程！赶紧码住👇
5月24日的华为OD机考，鱼丸的一个候选人拿下386高分！今天大佬把本场三道原题的考点、坑点、完整解题思路全部拆解出来，备考 OD 机考直接抄作业就行✅⭐️一星题1️⃣：简单表达式运算核心考点：8/10/16 进制解析、表达式求值、数值边界截断、8 位按位取反题目要求：输入字符串如"023+0x21+0o13+1"，解析出各进制整数，从左到右加减运算，结果限制在[-255,255]，然后转十六进制并按位取反，最后输出0xXX格式（大写，两位）。解法思路：识别 0x 十六进制、0o 八进制、普通数字十进制，每个数字必须 0~999，超范围直接输出 NA；从左到右顺序加减运算；...
点赞 评论 收藏
分享
昨天 09:37
武汉大学 C++
阿里 嵌入式面经一面
我先说一下，我这个是嵌入式应用层的开发。 早上在公司接到的阿里的面试，他问我什么时候有时间，我直接坦白了我在实习了，白天不行，问问可不可以安排在晚上，他答应了，安排的晚上八点，我面试完就煮了碗面吃了就开始整理，害怕等久了我就忘了。 首先说一下整体感受，面试官人挺好的，我整个面试过程也特别自信。我感觉面试官对我印象应该还行，当然，其实我也不是他问的所有东西都知道，只是我了解的不够就明说，了解的就多说些，以前面的时候多少有些紧张，现在想通了，反正也就这样，大不了面不过嘛，又不是多大个损失。可能因为我是面试老油条了，面试一点都不慌。我还是强调一下，现在是提前批，很多大公司提前批招人就招的差不多了，所...
查看12道真题和解析
点赞 评论 收藏
分享
05-27 19:08
已编辑
门头沟学院 推荐算法
点赞 评论 收藏
分享
05-14 01:33
西安电子科技大学 Java
点赞 评论 收藏
分享
05-29 16:28
武汉市武钢三中 产品经理
从双非到心仪offer：比起盲目海投，这3个破局策略才能真正改变结果
“双非”二字，在人才涌动的求职季里，常常像一道无形的门槛。有人被它绊住脚步，陷入自我怀疑的漩涡；也有人将它当作重新认识自己的起点，默默积蓄力量，最终弯道超车。本文的主人公陈屿，就是后者。他是一所普通院校的商科生，没有名校背书，却在毕业季拿下一家头部实业公司的管培生名额。这并非幸运突降，而是一场长达两年的精心布局。从低落的自我否定，到一步步搭建起属于自己的竞争力，他的经历中，有每一个双非学子都可能遇见的困顿，更有走出困顿的真实路径。一、困在标签里：当“双非”成为第一道枷锁大三那年秋天，陈屿第一次感受到现实的锋利。同校师兄师姐的求职分享会上，一句“有些企业只要985、211”被反复提及。他坐在台下...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 我的实习日记 #
4143445次浏览 33202人参与
# 你投了多少家公司？进展是___ #
252305次浏览 1476人参与
# 第3届现代汽车Code Faster急速编程挑战赛 #
26650次浏览 479人参与
# 秋招投递记录 #
429565次浏览 3312人参与
# 你投递的公司有几家约面了？ #
175024次浏览 1048人参与
# 今年形式下双非本找得到工作吗 #
339851次浏览 1797人参与
# 重来一次，你会对开始求职的自己说 #
55425次浏览 516人参与
# 实习返校后，你的精神状态是__？ #
47716次浏览 174人参与
# 你认为小厂实习有用吗？ #
153221次浏览 808人参与
# 通信/硬件求职避坑tips #
179660次浏览 1177人参与
# 产品实习，你更倾向大公司or小公司 #
234820次浏览 2169人参与
# 为了找工作你投递了多少公司？ #
122051次浏览 771人参与
# 秋招提前批，你开始投了吗 #
772441次浏览 8499人参与
# 实习生的生存小技巧 #
42147次浏览 366人参与
# 我的租房踩坑经历 #
231578次浏览 1328人参与
# 如何看待应届生身份？ #
261286次浏览 2364人参与
# 你找工作想离家近 or 离家远？ #
55202次浏览 403人参与
# 运营人的第一份offer应该如何选 #
273711次浏览 1375人参与
# 发工资后，你做的第一件事是什么 #
109087次浏览 350人参与
# 如果有时光机，你最想去到哪个年纪？ #
81927次浏览 863人参与
# 你小时候最想从事什么职业 #
170973次浏览 2080人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务