Recently Johnny have learned bogosort sorting algorithm. He thought that it is too ineffective. So he decided to improve it. As you may know this algorithm shuffles the sequence randomly until it is sorted. Johnny decided that we don't need to shuffle the whole sequence every time. If after the last shuffle several first elements end up in the right places we will fix them and don't shuffle those elements furthermore. We will do the same for the last elements if they are in the right places. For example, if the initial sequence is (3, 5, 1, 6, 4, 2) and after one shuffle Johnny gets (1, 2, 5, 4, 3, 6) he will fix 1, 2 and 6 and proceed with sorting (5, 4, 3) using the same algorithm. Johnny hopes that this optimization will significantly improve the algorithm. Help him calculate the expected amount of shuffles for the improved algorithm to sort the sequence of the first n natural numbers given that no elements are in the right places initially.

------ Input ------ 

The first line of input file is number t - the number of test cases. Each of the following t lines hold single number n - the number of elements in the sequence.

------ Constraints ------ 

1 ≤ t ≤ 150

2 ≤ n ≤ 150

------ Output ------ 

For each test case output the expected amount of shuffles needed for the improved algorithm to sort the sequence of first n natural numbers in the form of irreducible fractions.

----- Sample Input 1 ------ 
3
2
6
10
----- Sample Output 1 ------ 
2
1826/189
877318/35343

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Combinatorics

Mathematics

Probability
Skill types: Dynamic programming

Starter code:

Solutions:
from fractions import Fraction
fac = [1 for i in range(151)]
for i in range(1, 151):
	fac[i] = fac[i - 1] * i
count = [fac[i] - 2 * fac[i - 1] + fac[i - 2] for i in range(151)]
f = [Fraction(0, 1) for i in range(151)]
add = [Fraction(0, 1) for i in range(151)]
tot = Fraction(0, 1)
last = Fraction(0, 1)
for n in range(2, 151):
	d = last
	f[n] = Fraction(d + fac[n], fac[n] - count[n])
	tot = tot + count[n] * f[n]
	last = tot + last + count[n] * f[n]
t = int(input())
for case in range(t):
	n = int(input())
	print(f[n])


max_inp_len = 150
inp = [0] * (max_inp_len + 1)
nt = int(input())
max_n = 3
for j in range(nt):
	inp[j] = int(input())
	if inp[j] > max_n:
		max_n = inp[j]
t_n = [0] * (max_n + 1)
t_d = [1] * (max_n + 1)
t_n[2] = 2
a_n = 0
a_d = 1
b_n = 0
b_d = 1

def gcd(u, v):
	while v != 0:
		r = u % v
		u = v
		v = r
	return u
fact_n_minus_3 = 1
fact_n = 2
for n in range(3, max_n + 1):
	fact_n *= n
	f_n = ((n - 3) ** 2 + (n - 2)) * fact_n_minus_3 * t_n[n - 1]
	f_d = t_d[n - 1]
	a_n = f_n * a_d + a_n * f_d
	a_d *= f_d
	g = gcd(a_n, a_d)
	(a_n, a_d) = (a_n // g, a_d // g)
	b_n = (n - 2) * f_n * b_d + b_n * f_d
	b_d *= f_d
	g = gcd(b_n, b_d)
	(b_n, b_d) = (b_n // g, b_d // g)
	s_n = n * a_n * b_d - b_n * a_d
	s_d = a_d * b_d
	t_n[n] = (fact_n * s_d + s_n) * n * (n - 1)
	t_d[n] = s_d * fact_n * (2 * n - 3)
	g = gcd(t_n[n], t_d[n])
	(t_n[n], t_d[n]) = (t_n[n] // g, t_d[n] // g)
	fact_n_minus_3 *= n - 2

def solve(n):
	if t_d[n] == 1:
		print(t_n[n])
	else:
		print('%d/%d' % (t_n[n], t_d[n]))
for j in range(nt):
	solve(inp[j])


from fractions import Fraction
fact = [0 for x in range(151)]

def precompute1(num):
	fact[0] = 1
	for i in range(1, num + 1):
		fact[i] = fact[i - 1] * i
term = [0 for x in range(151)]

def precompute2(num):
	term[0] = 0
	term[1] = 0
	for i in range(2, num + 1):
		term[i] = ((i - 1) * (i - 2) + 1) * fact[i - 2]
ans = [Fraction(0, 1) for x in range(151)]

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def precompute3(num):
	ans[0] = Fraction(0, 1)
	ans[1] = Fraction(1, 1)
	ans[2] = Fraction(2, 1)
	cumm = Fraction(0, 1)
	for n in range(3, num + 1):
		cumm = cumm + Fraction(term[n - 1] * (ans[n - 1].numerator + ans[n - 1].denominator), ans[n - 1].denominator)
		k = Fraction(term[n], 1) + cumm + Fraction(ans[n - 1].numerator * fact[n - 1], ans[n - 1].denominator)
		numer = int(k.numerator)
		denom = int(k.denominator) * int(fact[n] - term[n])
		g = int(gcd(numer, denom))
		numer = numer // g
		denom = denom // g
		ans[n] = Fraction(numer, denom)

def main():
	t = int(input())
	inp = []
	while t > 0:
		t -= 1
		n = int(input())
		inp.append(n)
	mx = max(inp)
	precompute1(mx)
	precompute2(mx)
	precompute3(mx)
	for n in inp:
		if ans[n].denominator == 1:
			print(ans[n].numerator)
		else:
			print(str(ans[n].numerator) + '/' + str(ans[n].denominator))
main()


from fractions import Fraction
import sys
n = int(input())
v = [None] * n
mv = 0
for i in range(0, n):
	v[i] = int(input())
	if mv < v[i]:
		mv = v[i] + 1
fa = [None] * 155
fa[0] = 1
fa[1] = 1
for f in range(2, 151):
	fa[f] = fa[f - 1] * f
ns = [None] * 155
for n in range(2, mv):
	ns[n] = fa[n] - fa[n - 1] * 2 + fa[n - 2]
mo = [None] * 155
mo[1] = Fraction(0)
mo[2] = Fraction(2)
mu = [None] * 155
mu[2] = ns[2] * mo[2]
li1 = Fraction(0)
liA = Fraction(0)
for n in range(3, mv):
	li1 += mu[n - 1]
	liA += mu[n - 1] + li1
	mo[n] = (liA + fa[n]) / (fa[n] - ns[n])
	if n < mv - 1:
		mu[n] = ns[n] * mo[n]
for i in v:
	print(mo[i])


from fractions import Fraction
n = int(input())
v = [None] * n
MAXV = 0
for i in range(0, n):
	v[i] = int(input())
	if MAXV < v[i]:
		MAXV = v[i] + 1
fa = [None] * 155
fa[0] = 1
fa[1] = 1
for f in range(2, MAXV):
	fa[f] = fa[f - 1] * f
ns = [None] * 155
for n in range(2, MAXV):
	ns[n] = fa[n] - fa[n - 1] * 2 + fa[n - 2]
mo = [None] * 155
mo[1] = Fraction(0)
mo[2] = Fraction(2)
li1 = Fraction(0)
liA = Fraction(0)
for n in range(3, MAXV):
	zz = ns[n - 1] * mo[n - 1]
	li1 += zz
	liA += zz + li1
	mo[n] = (liA + fa[n]) / (fa[n] - ns[n])
for i in v:
	print(mo[i])


import sys
from fractions import *

def readInt():
	return int(input())

def readList():
	return list(map(int, input().strip().split(' ')))

def readStr():
	return input().strip()

def makeMatrix(a, b, value):
	z = [value] * a
	for i in range(a):
		z[i] = [value] * b
	return z
MAXN = 152
e = [0] * MAXN
e[1] = Fraction(1, 1)
e[2] = Fraction(2, 1)
f = [1] * MAXN
for i in range(1, MAXN):
	f[i] = f[i - 1] * i
for i in range(3, MAXN):
	p = Fraction()
	for k in range(2, i + 1):
		p += e[k] * f[k - 2] * ((k - 2) * (k - 3) + (k - 2) * 2 + 1) * (i + 1 - k)
	e[i] = Fraction(p + f[i], f[i]) * (i * i - i)
	e[i] = e[i] / (2 * i - 3)
tc = readInt()
while tc:
	tc -= 1
	n = readInt()
	if n <= 1 or n > 150:
		while True:
			pass
	if e[n].denominator == 1:
		print(e[n].numerator)
	else:
		print('%i/%i' % (e[n].numerator, e[n].denominator))


from fractions import Fraction
fact = [1]
for i in range(1, 151):
	fact.append(i * fact[-1])
dp = [None] * 151
dp[2] = Fraction(2, 1)
pre_mult = [None] * 151
pre_mult[2] = dp[2] * fact[2 - 2]
for n in range(3, 151):
	sum = 0
	for nk in range(2, n):
		sum += pre_mult[nk] * (3 + 3 * n + nk * (-3 * n - 6) + nk * nk * (n + 4) - nk * nk * nk)
	dp[n] = (-fact[n] - sum) / ((n * n - 3 * n + 3) * fact[n - 2] - fact[n])
	pre_mult[n] = dp[n] * fact[n - 2]
t = int(input())
for tc in range(t):
	n = int(input())
	print(dp[n])


from fractions import Fraction
max_inp_len = 150
inp = [0] * (max_inp_len + 1)
nt = int(input())
max_n = 3
for j in range(nt):
	inp[j] = int(input())
	if inp[j] > max_n:
		max_n = inp[j]
t = [0] * (max_n + 1)
t[0] = 0
t[1] = 0
t[2] = 2
fact = [1] * (max_n + 1)
for n in range(2, max_n + 1):
	fact[n] = fact[n - 1] * n
aa = 0
bb = 0

def ff(j):
	return ((j - 2) ** 2 + (j - 1)) * fact[j - 2] * t[j]
for n in range(3, max_n + 1):
	denom = Fraction(2 * n - 3, n * (n - 1))
	fj = ff(n - 1)
	aa += fj
	bb += (n - 2) * fj
	s = n * aa - bb
	t[n] = (1 + s * Fraction(1, fact[n])) / denom
for j in range(nt):
	print(t[inp[j]])