竞赛讨论区 > 【每日一题】4月16日题目精讲 逆序对 数学 快速幂
头像
王清楚
编辑于 2020-04-16 11:26
+ 关注

【每日一题】4月16日题目精讲 逆序对 数学 快速幂

题号 NC14731
名称 逆序对
来源 Wannafly挑战赛6
戳我进入往期每日一题汇总贴~


图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题非常简单...
任意一对都会对逆序对贡献一个1,我们可以考虑任选两个位置前一个放1后一个放0,那么剩下的位置不管怎么放,都能贡献一对逆序对,也就是说这样的方案有多少就有多少逆序对。任选两个位置的方案数是,其他n个位置随便放的方案数是,所以总逆序对数就是
注意n=1的时候需要特判。有的同学用的另外的公式可能n=3的时候也需要特判(最开始数据没这些情况,现已加强)。
下面说一下快速幂(会的同学就可以跳过啦)。
快速幂是快速的求a在模p意义下的b次方(不取模的时候自带的pow函数就很好用,也是log级别的复杂度。)
这实际上是利用了倍增思想和模运算的结合律(即),我们可以把 中的b表示为二进制,例如,然后根据二进制转十进制的规则我们知道。我们可以用倍增的方法每次求出(即然后根据b的二进制的情况决定这一部分乘不乘进答案里。(以上运算过程都可以边算边取模)

看完邓老师的题解,记得去做题提高呀~
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目4月23日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论

(40) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐