题解 | 小红的子序列逆序对

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, x, val):
        while x <= self.n:
            self.tree[x] = (self.tree[x] + val) % MOD
            x += x & -x

    def query(self, x):
        res = 0
        while x > 0:
            res = (res + self.tree[x]) % MOD
            x -= x & -x
        return res


N = 100005
MOD = 10 ** 9 + 7

# Precompute powers of 2
f = [1] * N
for i in range(3, N):
    f[i] = (f[i - 1] * 2) % MOD


def solve():
    n = int(input())
    a = list(map(int, input().split()))

    bit = BIT(100000)
    ans = 0

    for i in range(n):
        # Count inversions for current element
        inversions = (bit.query(100000) - bit.query(a[i]) + MOD) % MOD
        ans = (ans + inversions) % MOD
        bit.update(a[i], 1)

    # Multiply result by 2^n
    ans = (ans * f[n]) % MOD
    print(ans)


if __name__ == "__main__":
    t = 1
    # t = int(input())  # Uncomment for multiple test cases
    for _ in range(t):
        solve()

全部评论

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:20
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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