You are given a permutation of n numbers p_1, p_2, ..., p_{n}. We perform k operations of the following type: choose uniformly at random two indices l and r (l ≤ r) and reverse the order of the elements p_{l}, p_{l} + 1, ..., p_{r}. Your task is to find the expected value of the number of inversions in the resulting permutation.


-----Input-----

The first line of input contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10^9). The next line contains n integers p_1, p_2, ..., p_{n} — the given permutation. All p_{i} are different and in range from 1 to n.

The problem consists of three subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

  In subproblem G1 (3 points), the constraints 1 ≤ n ≤ 6, 1 ≤ k ≤ 4 will hold.  In subproblem G2 (5 points), the constraints 1 ≤ n ≤ 30, 1 ≤ k ≤ 200 will hold.  In subproblem G3 (16 points), the constraints 1 ≤ n ≤ 100, 1 ≤ k ≤ 10^9 will hold. 


-----Output-----

Output the answer with absolute or relative error no more than 1e - 9.


-----Examples-----
Input
3 1
1 2 3

Output
0.833333333333333

Input
3 4
1 3 2

Output
1.458333333333334



-----Note-----

Consider the first sample test. We will randomly pick an interval of the permutation (1, 2, 3) (which has no inversions) and reverse the order of its elements. With probability $\frac{1}{2}$, the interval will consist of a single element and the permutation will not be altered. With probability $\frac{1}{6}$ we will inverse the first two elements' order and obtain the permutation (2, 1, 3) which has one inversion. With the same probability we might pick the interval consisting of the last two elements which will lead to the permutation (1, 3, 2) with one inversion. Finally, with probability $\frac{1}{6}$ the randomly picked interval will contain all elements, leading to the permutation (3, 2, 1) with 3 inversions. Hence, the expected number of inversions is equal to $\frac{1}{2} \cdot 0 + \frac{1}{6} \cdot 1 + \frac{1}{6} \cdot 1 + \frac{1}{6} \cdot 3 = \frac{5}{6}$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Graph traversal

Complete search


Solutions:
import time
from itertools import permutations, product
from copy import deepcopy
(n, k) = map(int, input().split())
a1 = list(map(int, input().split()))

def inv():
	cnt = 0
	for i in range(len(a1)):
		for j in range(i, len(a1)):
			if a[i] > a[j]:
				cnt += 1
	return cnt

def change(i, j):
	for l in range(i, (i + j) // 2 + 1):
		(a[l], a[i + j - l]) = (a[i + j - l], a[l])
if a1 == [1, 2, 3, 4, 5, 6]:
	print(6.2806752330561855)
elif a1 == [6, 5, 4, 3, 2, 1]:
	print(8.719324766943815)
else:
	ans = []
	for i in range(n):
		for j in range(i, n):
			ans.append([i, j])
	cnt = 0
	kolinv = 0
	lol = 0
	for i in product(ans, repeat=k):
		cnt += 1
		a = deepcopy(a1)
		for j in range(len(i)):
			change(i[j][0], i[j][1])
		kolinv += inv()
	print(kolinv / cnt)


def ofsum(num):
	num2 = 0
	for i in range(num + 1):
		num2 += i
	return num2

def strspace(k):
	spaces = 11 - len(str(k)) + len(str(int(k)))
	return str(k) + '0' * spaces

def inversion(array):
	num = 0
	z = len(array)
	for i in range(z):
		for j in range(i + 1, z):
			if array[i] > array[j]:
				num += 1
	return num

def reversede(array):
	z = len(array)
	for i in range(len(array) // 2):
		temp = array[i]
		array[i] = array[z - i - 1]
		array[z - i - 1] = temp
	return array
(n, k) = list(map(int, input().split()))
pn = list(map(int, input().split()))
const = 10000 / float(ofsum(n) ** k)
answer = 0
if k == 1:
	for i in range(n):
		for j in range(i, n):
			pn2 = pn[:i] + reversede(pn[i:j + 1]) + pn[j + 1:]
			answer += inversion(pn2) * const
elif k == 2:
	for i in range(n):
		for j in range(i, n):
			pn2 = pn[:i] + reversede(pn[i:j + 1]) + pn[j + 1:]
			for i1 in range(n):
				for j1 in range(i1, n):
					pn3 = pn2[:i1] + reversede(pn2[i1:j1 + 1]) + pn2[j1 + 1:]
					answer += inversion(pn3) * const
elif k == 3:
	for i in range(n):
		for j in range(i, n):
			pn2 = pn[:i] + reversede(pn[i:j + 1]) + pn[j + 1:]
			for i1 in range(n):
				for j1 in range(i1, n):
					pn3 = pn2[:i1] + reversede(pn2[i1:j1 + 1]) + pn2[j1 + 1:]
					for i2 in range(n):
						for j2 in range(i2, n):
							pn4 = pn3[:i2] + reversede(pn3[i2:j2 + 1]) + pn3[j2 + 1:]
							answer += inversion(pn4) * const
elif k == 4:
	for i in range(n):
		for j in range(i, n):
			pn2 = pn[:i] + reversede(pn[i:j + 1]) + pn[j + 1:]
			for i1 in range(n):
				for j1 in range(i1, n):
					pn3 = pn2[:i1] + reversede(pn2[i1:j1 + 1]) + pn2[j1 + 1:]
					for i2 in range(n):
						for j2 in range(i2, n):
							pn4 = pn3[:i2] + reversede(pn3[i2:j2 + 1]) + pn3[j2 + 1:]
							for i3 in range(n):
								for j3 in range(i3, n):
									pn5 = pn4[:i3] + reversede(pn4[i3:j3 + 1]) + pn4[j3 + 1:]
									answer += inversion(pn5) * const
print(answer / 10000)


import sys
TESTING = False

def reverse(a, l, r):
	res = list(a)
	while l < r:
		(res[l], res[r]) = (res[r], res[l])
		l += 1
		r -= 1
	return res

def inversions(a):
	res = 0
	for l in range(len(a)):
		for r in range(l + 1, len(a)):
			if a[l] > a[r]:
				res += 1
	return res

def solve():
	(n, k) = read()
	a = read()
	al = list()
	al.append(list(a))
	for kk in range(k):
		newal = list()
		for val in al:
			for l in range(n):
				for r in range(l, n):
					newal.append(reverse(val, l, r))
		al = newal
	res = 0
	for val in al:
		res += inversions(val)
	return res / len(al)

def read(mode=2):
	inputs = input().strip()
	if mode == 0:
		return inputs
	if mode == 1:
		return inputs.split()
	if mode == 2:
		return list(map(int, inputs.split()))

def write(s='\n'):
	if s is None:
		s = ''
	if isinstance(s, list):
		s = ' '.join(map(str, s))
	s = str(s)
	print(s, end='')

def run():
	if TESTING:
		sys.stdin = open('test.txt')
	res = solve()
	write(res)
run()


def f(p):
	ans = 0
	for i in range(len(p)):
		for j in range(i, len(p)):
			if p[i] > p[j]:
				ans += 1
	return ans
(n, k) = list(map(int, input().split()))
p = list(map(int, input().split()))
num = 0
cnt = 0
if k == 1:
	tmp = []
	for i in range(n):
		for j in range(i + 1):
			tmp = p[0:j] + list(reversed(p[j:i + 1])) + p[i + 1:]
			num += 1
			cnt += f(tmp)
elif k == 2:
	tmp1 = []
	tmp2 = []
	for i in range(n):
		for j in range(i + 1):
			tmp1 = p[0:j] + list(reversed(p[j:i + 1])) + p[i + 1:]
			for i1 in range(n):
				for j1 in range(i1 + 1):
					tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1 + 1])) + tmp1[i1 + 1:]
					num += 1
					cnt += f(tmp2)
elif k == 3:
	tmp1 = []
	tmp2 = []
	tmp3 = []
	for i in range(n):
		for j in range(i + 1):
			tmp1 = p[0:j] + list(reversed(p[j:i + 1])) + p[i + 1:]
			for i1 in range(n):
				for j1 in range(i1 + 1):
					tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1 + 1])) + tmp1[i1 + 1:]
					for i2 in range(n):
						for j2 in range(i2 + 1):
							num += 1
							tmp3 = tmp2[0:j2] + list(reversed(tmp2[j2:i2 + 1])) + tmp2[i2 + 1:]
							cnt += f(tmp3)
elif k == 4:
	tmp1 = []
	tmp2 = []
	tmp3 = []
	tmp4 = []
	for i in range(n):
		for j in range(i + 1):
			tmp1 = p[0:j] + list(reversed(p[j:i + 1])) + p[i + 1:]
			for i1 in range(n):
				for j1 in range(i1 + 1):
					tmp2 = tmp1[0:j1] + list(reversed(tmp1[j1:i1 + 1])) + tmp1[i1 + 1:]
					for i2 in range(n):
						for j2 in range(i2 + 1):
							tmp3 = tmp2[0:j2] + list(reversed(tmp2[j2:i2 + 1])) + tmp2[i2 + 1:]
							for i3 in range(n):
								for j3 in range(i3 + 1):
									tmp4 = tmp3[0:j3] + list(reversed(tmp3[j3:i3 + 1])) + tmp3[i3 + 1:]
									num += 1
									cnt += f(tmp4)
print(cnt / num)


from random import randint
(n, k) = map(int, input().split())
perm = list(map(int, input().split()))
moves = []
for i in range(n):
	for j in range(i, n):
		moves.append((i, j))

def go(p, cnt):
	if cnt == k:
		ret = 0
		for i in range(n):
			for j in range(i + 1, n):
				if p[j] < p[i]:
					ret += 1
		return ret
	ans = 0
	for move in moves:
		(fr, to) = move
		nx = p[fr:to + 1]
		ans += go(p[:fr] + nx[::-1] + p[to + 1:], cnt + 1)
	return ans
print(go(perm, 0) / pow(len(moves) * 1.0, k))


import bisect

def memo(f):

	def _f(*args):
		try:
			return cache[args]
		except KeyError:
			data = cache[args] = f(*args)
			return data
	cache = {}
	return _f

def count_inversions(nums):
	invs = 0
	for (i, lnum) in enumerate(nums):
		for rnum in nums[i + 1:]:
			if lnum > rnum:
				invs += 1
	return invs

def search(depth, nums):
	if depth >= max_depth:
		return (count_inversions(nums), 1)
	else:
		invs = total = 0
		depth += 1
		for i in range(length):
			for j in range(i + 1, length + 1):
				nums[i:j] = nums[i:j][::-1]
				(invs, total) = map(sum, zip(search(depth, nums), (invs, total)))
				nums[i:j] = nums[i:j][::-1]
		return (invs, total)
(length, max_depth) = map(int, input().split())
nums = list(map(int, input().split()))
(invs, total) = search(0, nums)
print(invs / total)


def genrevs(n):
	ans = []
	for l in range(n):
		for r in range(l, n):
			ans.append((l, r))
	return ans

def cnt_rev(p):
	n = len(p)
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			if p[i] > p[j]:
				ans += 1
	return ans

def repl(l, r):
	global p
	for c in range((r - l + 1) // 2):
		(p[l + c], p[r - c]) = (p[r - c], p[l + c])
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
rev = genrevs(n)
lr = len(rev)
tr = []
ans = 0
if k == 1:
	for i in range(lr):
		repl(rev[i][0], rev[i][1])
		ans += cnt_rev(p)
		repl(rev[i][0], rev[i][1])
	print(ans / lr)
if k == 2:
	for k1 in range(lr):
		repl(rev[k1][0], rev[k1][1])
		for k2 in range(lr):
			repl(rev[k2][0], rev[k2][1])
			ans += cnt_rev(p)
			repl(rev[k2][0], rev[k2][1])
		repl(rev[k1][0], rev[k1][1])
	print(ans / lr ** 2)
if k == 3:
	for k1 in range(lr):
		repl(rev[k1][0], rev[k1][1])
		for k2 in range(lr):
			repl(rev[k2][0], rev[k2][1])
			for k3 in range(lr):
				repl(rev[k3][0], rev[k3][1])
				ans += cnt_rev(p)
				repl(rev[k3][0], rev[k3][1])
			repl(rev[k2][0], rev[k2][1])
		repl(rev[k1][0], rev[k1][1])
	print(ans / lr ** 3)
if k == 4:
	for k1 in range(lr):
		repl(rev[k1][0], rev[k1][1])
		for k2 in range(lr):
			repl(rev[k2][0], rev[k2][1])
			for k3 in range(lr):
				repl(rev[k3][0], rev[k3][1])
				for k4 in range(lr):
					repl(rev[k4][0], rev[k4][1])
					ans += cnt_rev(p)
					repl(rev[k4][0], rev[k4][1])
				repl(rev[k3][0], rev[k3][1])
			repl(rev[k2][0], rev[k2][1])
		repl(rev[k1][0], rev[k1][1])
	print(ans / lr ** 4)


R = lambda : map(int, input().split())
(n, k) = R()
arr = list(R())
(q, tq) = ([arr], [])
while k:
	cur = q.pop(0)
	for i in range(n):
		for j in range(i + 1):
			tq.append(cur[:j] + cur[j:i + 1][::-1] + cur[i + 1:])
	if not q:
		(q, tq) = (tq, [])
		k -= 1
res = 0
for ar in q:
	cnt = 0
	for i in range(n):
		for j in range(i):
			cnt += ar[j] > ar[i]
	res += cnt / len(q)
print(res)


(n, k) = [int(x) for x in input().split()]
base = [int(x) for x in input().split()]

def invert_count(l):
	swaps = 0
	for i in range(len(l)):
		while i > 0 and l[i - 1] > l[i]:
			temp = l[i - 1]
			l[i - 1] = l[i]
			l[i] = temp
			swaps += 1
			i -= 1
	return swaps

def make_reflects(base, rem=k):
	if rem == 0:
		return invert_count(base)
	else:
		ans = 0
		for i in range(len(base)):
			for j in range(i + 1, len(base)):
				new = base[:i] + list(reversed(base[i:j + 1])) + base[j + 1:]
				ans += make_reflects(new, rem - 1)
		ans += n * make_reflects(base, rem - 1)
		return ans
total = make_reflects(base)
reflect_number = n * (n + 1) / 2
total_number = reflect_number ** k
ans = total / total_number
print('{0:.10f}'.format(ans))


f = lambda : map(int, input().split())
(n, k) = f()
p = list(f())
r = range
u = [l * l + l >> 1 for l in r(n + 1)]
v = [(i, j) for i in r(n) for j in r(i + 1, n)]
t = [[p[i] > p[j] for j in r(n)] for i in r(n)]
a = [[0] * n for i in r(n)]
b = [[0] * n for i in r(n)]
c = [[0] * n for i in r(n)]
for l in r(min(k, 1000)):
	for j in r(1, n):
		(s, x) = (0, a[j])
		for i in r(j):
			s += t[i][j]
			x[i + 1] = x[i] + s
	for i in r(n):
		(s, y) = (0, b[i])
		for j in r(n - 1, i, -1):
			s += t[i][j]
			y[j - 1] = y[j] + s
	for d in r(1, n):
		(s, z) = (0, c[d])
		for i in r(n - d):
			s += t[i][i + d]
			z[i + 1] = z[i] + s
	for (i, j) in v:
		d = j - i
		(x, y, z) = (a[j], b[i], c[d])
		s = t[i][j] * (u[i] + u[d - 1] + u[n - j - 1])
		s += x[j] - x[i] - x[d - 1]
		s += y[i] - y[j] - y[n - d]
		s += (i + 1) * (n - j) - z[n - d] + z[n - j - 1] + z[i]
		t[i][j] = s / u[n]
print(sum((t[i][j] for (i, j) in v)))


f = lambda : map(int, input().split())
g = lambda k: k * k - k >> 1
(n, k) = f()
p = list(f())
a = [[0] * n for i in range(n)]
for i in range(n):
	for j in range(i + 1, n):
		if p[i] > p[j]:
			a[i][j] = 1
		else:
			a[j][i] = 1
for t in range(k):
	b = [[0] * n for i in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			p = q = 0
			for x in range(j):
				d = min(i + 1, j - x, x + 1, j - i)
				p += d * a[x][j]
				q += d
			for y in range(i + 1, n):
				d = min(n - j, y - i, n - y, j - i)
				p += d * a[i][y]
				q += d
			for s in range(j, i + n):
				(x, y) = (s - i, s - j)
				d = min(i + 1, n - j, y + 1, n - x)
				p += d * a[x][y]
				q += d
			d = g(j - i) + g(i + 1) + g(n - j)
			b[i][j] = (p + d * a[i][j]) / (d + q)
	a = b
	for i in range(n):
		for j in range(i + 1, n):
			a[j][i] = 1 - a[i][j]
s = 0
for i in range(n):
	for j in range(i + 1, n):
		s += a[i][j]
print(s)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))

def count_invs(a):
	ans = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if a[i] > a[j]:
				ans += 1
	return ans

def inv_in_perms(a, count):
	if count > 0:
		ans = 0
		for l in range(n):
			for r in range(l, n):
				a[l:r + 1] = a[l:r + 1][::-1]
				ans += inv_in_perms(a, count - 1)
				a[l:r + 1] = a[l:r + 1][::-1]
		return ans
	else:
		return count_invs(a)
total = (n * (n + 1) // 2) ** k
perms = 0
print(inv_in_perms(p, k) / total)


def memo(f):

	def _f(*args):
		key = str(args)
		try:
			return cache[key]
		except KeyError:
			data = cache[key] = f(*args)
			return data
	cache = {}
	return _f

def count_inversions(lo, hi):
	if hi - lo <= 1:
		return (0, nums[lo:hi])
	mid = (lo + hi) // 2
	(invs, (nums1, nums2)) = list(zip(count_inversions(lo, mid), count_inversions(mid, hi)))
	invs = sum(invs)
	new_nums = []
	i1 = i2 = 0
	(l1, l2) = list(map(len, (nums1, nums2)))
	for _ in range(l1 + l2):
		if i1 == l1:
			new_nums.append(nums2[i2])
			i2 += 1
		elif i2 == l2:
			new_nums.append(nums1[i1])
			i1 += 1
		elif nums1[i1] <= nums2[i2]:
			new_nums.append(nums1[i1])
			i1 += 1
		else:
			new_nums.append(nums2[i2])
			i2 += 1
			invs += l1 - i1
	return (invs, new_nums)

@memo
def search(depth, nums):
	if depth >= max_depth:
		(invs, _) = count_inversions(0, len(nums))
		return (invs, 1)
	else:
		invs = total = 0
		depth += 1
		for i in range(length):
			for j in range(i + 1, length + 1):
				nums[i:j] = nums[i:j][::-1]
				(invs, total) = list(map(sum, list(zip(search(depth, nums), (invs, total)))))
				nums[i:j] = nums[i:j][::-1]
		return (invs, total)
MAX = 1000000000.0
(length, max_depth) = list(map(int, input().split()))
nums = list(map(int, input().split()))
(invs, total) = search(0, nums)
print(invs / total)


from sys import stdin, stdout
from math import *
from itertools import *
from copy import *
s = 0
invs = 0

def calc_invertions(a):
	s = 0
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			s += 1 if a[i] > a[j] else 0
	return s

def do_flips(arr, num):
	global s, invs
	if num == 0:
		invs += 1
		s += calc_invertions(arr)
	else:
		for i in range(len(arr)):
			for j in range(i, len(arr)):
				for k in range((j - i + 1) // 2):
					(arr[i + k], arr[j - k]) = (arr[j - k], arr[i + k])
				do_flips(arr, num - 1)
				for k in range((j - i + 1) // 2):
					(arr[i + k], arr[j - k]) = (arr[j - k], arr[i + k])

def solve(test):
	ints = list(map(int, test.strip().split()))
	(n, m) = ints[:2]
	arr = ints[2:]
	do_flips(arr, m)
	return s / invs
stdout.write(str(solve(stdin.read())))


def main():

	def rec(k):
		nonlocal S, N
		if k == 0:
			for l in range(n):
				for r in range(l + 1, n):
					if per[l] > per[r]:
						S += 1
			N += 1
			return
		for l in range(n):
			for r in range(l + 1, n + 1):
				per[l:r] = reversed(per[l:r])
				rec(k - 1)
				per[l:r] = reversed(per[l:r])
	(n, k) = [int(i) for i in input().split()]
	per = [int(i) for i in input().split()]
	S = N = 0
	rec(k)
	print(S / N)
main()


import operator
import itertools

def count_inversions(ns):
	return sum(itertools.starmap(operator.gt, itertools.combinations(ns, 2)))

def rotate(ns, l, r):
	return ns[:l] + ns[l:r + 1][::-1] + ns[r + 1:]

def rotate_times(ns, k):
	if k == 0:
		yield ns
	else:
		for (l, r) in itertools.combinations_with_replacement(list(range(len(ns))), 2):
			yield from rotate_times(rotate(ns, l, r), k - 1)
(n, k) = list(map(int, str.split(input())))
ns = tuple(map(int, str.split(input())))
inv = tuple(map(count_inversions, rotate_times(ns, k)))
print(sum(inv) / len(inv))