比赛场次 600
比赛名称 NOIP2023模拟赛3
比赛状态 已结束比赛成绩
开始时间 2023-11-15 08:00:00
结束时间 2023-11-15 13:00:00
开放分组 全部用户
注释介绍
题目名称 期望逆序对
输入输出 starlit.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar宇战 WWWWWWWWWW 0.000 s 0.00 MiB 0
Gravatar元始天尊 WWTTTTTTTE 7.169 s 5.51 MiB 0
Gravatar┭┮﹏┭┮ WWTTTTTTTT 8.123 s 51.51 MiB 0

期望逆序对

★★★★   输入文件:starlit.in   输出文件:starlit.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】



给你一个长为n的排列,有k次操作,每次随机选择两个不同的数交换,问期望逆序对数乘C(n,2)^k的结果。


注:

1、C(n,2)表示在n个数中选两个数的方案数

2、数学期望指的是随机变量的长期平均结果,它基于随机变量的可能结果及其各自的概率。从本质上讲,如果重复进行一项实验(如概率游戏),期望值会告诉我们长期平均结果。

统计学家将离散型随机变量的一切可能的取值xi与对应的概率p(xi)的乘积之和称为该离散型随机变量的数学期望  (若该求和绝对收敛),记为E(x)。它是简单算术平均的一种推广,类似加权平均。

例如:

掷骰子能得到的点数为1,2,3,4,5,6(总 状态数/方案数 为6)

每个点数得到的概率都是1/6

那么期望值就是1/6+2/6+3/6+4/6+5/6+6/6=3.5(点数*概率的和)

这个3.5就是指你在掷了足够多次骰子之后得到点数的平均值为3.5


【输入格式】

第一行两个整数n,k

第二行一个1到n的排列

【输出格式】

一行表示答案,答案对1e9+7取模。

【样例输入】

5 1
1 5 4 3 2

【样例输出】

50

【提示】

[样例说明] 

  任选两个数交换共有C(n,2)=10种方案,每种方案的产生是等概率的

  方案1:1 5交换后,逆序对数为7

方案2:选1 4 交换后,逆序对数为7

方案3:选1 3 交换后,逆序对数为7

方案4:选1 2 交换后,逆序对数为7

方案5:选5 4 交换后,逆序对数为5

方案6:选5 3交换后,逆序对数为3

方案7:选5 2 交换后,逆序对数为1

方案8:选4 3 交换后,逆序对数为5

方案9:选4 2 交换后,逆序对数为3

方案10:选3 2 交换后,逆序对数为5

期望逆序对数(7/10+7/10+7/10+7/10+5/10+3/10+1/10+5/10+3/10+5/10=5

答案为5*10=50


[数据范围]:

分值

数据范围

10%

n<=8,k<=100

10%

n<=15,k<=5

10%

保证初始排列单调递增

20%

n<=100,k<=1e14

20%

n<=1000,k<=1e14

20%

n<=10000,k<=1e14

10%

n<=200000,k<=1e14


【来源】