A22701.期望逆序对
NOI/NOI+/CTSC
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
WXH大定理定律nmcfx领导的修道院试图通过古老的膜法阵召唤出传说中的膜法处佬WXH。在他把召唤用具准备齐全后,mcfx在众人的键盘声中启动了召唤阵。
这时,天地突然暗了下来,膜法阵中心电闪雷鸣。一道金光从天而降,金色的代码飘在了半空中。不一会,一个登陆界面显现了出来。mcfx仔细观察后发现上面有如下文字:
"WXHCoder是过去到未来所有的题目都有的题库。如果想要登陆它,你们必须解决接下来这道题。"
这道题目是这样子的:给你一个长为n的排列,有k次操作,每次随机选择两个不同的数交换,问期望逆序对数乘(2n)k的结果。
mcfx发现数据范围是n,k≤1020010910,他打算先探究更小的n,k。
(2n)表示在n个球中选两个的方案数
输入格式
第一行两个整数n,k
第二行一个1到n的排列
输出格式
输出期望逆序对数乘(2n)k的结果模109+7
输入输出样例
输入#1
5 4 1 5 4 3 2
输出#1
50000
说明/提示
n≤500000,k≤109