F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5058. -- 期望逆序对

5058: 期望逆序对

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 164  Solved: 99
[Submit][Status][Discuss]

Description

mcfx领导的修道院试图通过古老的膜法阵召唤出传说中的膜法处佬WXH。在他把召唤用具准备齐全后,mcfx在众人
的键盘声中启动了召唤阵。这时,天地突然暗了下来,膜法阵中心电闪雷鸣。一道金光从天而降,金色的代码飘在
了半空中。不一会,一个登陆界面显现了出来。mcfx仔细观察后发现上面有如下文字:"WXHCoder是过去到未来所
有的题目都有的题库。如果想要登陆它,你们必须解决接下来这道题。"这道题目是这样子的:给你一个长为n的排
列,有k次操作,每次随机选择两个不同的数交换,问期望逆序对数乘C(n,2)^k的结果。mcfx发现数据范围是n,k≤
10^20010910,他打算先探究更小的n,k。C(n,2)表示在n个球中选两个的方案数

Input

第一行两个整数n,k
第二行一个1~n的排列
n≤500000,k≤10^9

Output

输出期望逆序对数乘C(n,2)^k的结果,答案模10^9+7

Sample Input

5 4
1 5 4 3 2

Sample Output

50000

HINT

Source

By SmallFat 上传

[Submit][Status][Discuss]

HOME Back