Read problems statements in Mandarin Chinese  and Russian. 

Little Elephant from Zoo of Lviv likes to paint.

He has n objects to paint, ordered in a row and numbered form left to right starting from 1. There are totally c colors, numbered from 0 to c-1. At the beggining all objects are colored in color with number 1. When object with color a is painted in color b, the resulting color will have number (a*b) mod c.

Little Elephant is going to make k turns. At i-th (0-based numeration) turn he will randomly choose any subset (even empty) of objects with indices in range [L_{i}; R_{i}] (inclusive) and paint all objects in chosen subset with random color (the same for all objects in the subset).

Little Elephant wants to know the expected sum of all colors over all n objects after making all k turns. Help him.

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

First line contain single integer T - the number of test cases. T test cases follow. First line of each test case contains three integers n, c and k. Next k lines of each test case contain k pairs of integers L_{i} and R_{i}, one pair per line.

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

In T lines print T real numbers - the answers for the corresponding test cases.

Any results within 10^-6 absolute error will be accepted.

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

1 ≤ T ≤ 10

1 ≤ n, k ≤ 50

2 ≤ c ≤ 100

1 ≤ L_{i} ≤ R_{i} ≤ n

----- Sample Input 1 ------ 
2
4 3 4
1 2
2 4
3 3
1 4
7 10 7
7 7
3 4
1 2
5 5
4 5
2 7
3 3
----- Sample Output 1 ------ 
3.444444444
22.943125000

Difficulty: HARD
Tags: Dynamic programming

Mathematics

Probability
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
data = sys.stdin.read().split()
data.reverse()

def read():
	return int(data.pop())

def readStr():
	return data.pop()
N = 100 + 5
T = read()
for test in range(T):
	(n, c, k) = (read(), read(), read())
	F = [0] * (n + 5)
	for i in range(k):
		(l, r) = (read(), read())
		F[l] += 1
		F[r + 1] -= 1
	DP = [[0 for i in range(N)] for j in range(N)]
	for i in range(c):
		DP[i][0] = i
	for j in range(1, N):
		for i in range(1, c):
			cnt = 0
			for l in range(c):
				cnt += DP[i * l % c][j - 1]
			cnt /= c
			DP[i][j] = (cnt + DP[i][j - 1]) / 2
	ans = 0
	for i in range(1, n + 1):
		F[i] += F[i - 1]
		ans += DP[1][F[i]]
	print(ans)


for _ in range(int(input())):
	(N, C, K) = [int(c) for c in input().split()]
	dp = [[[0 for i in range(C)] for ii in range(N)] for ii in range(K + 1)]
	for i in range(N):
		dp[0][i][1] = 1
	for i in range(1, K + 1):
		(l, r) = [int(c) - 1 for c in input().split()]
		for j in range(N):
			for k in range(C):
				if j >= l and j <= r:
					for m in range(C):
						dp[i][j][m * k % C] += dp[i - 1][j][k] / (2 * C)
					dp[i][j][k] += dp[i - 1][j][k] * 0.5
				else:
					dp[i][j][k] += dp[i - 1][j][k]
	ans = 0
	for i in range(N):
		for j in range(C):
			ans += j * dp[K][i][j]
	print(ans)


for t in range(int(input())):
	(n, c, k) = [int(x) for x in input().split()]
	a = [[[0 for i in range(c)] for j in range(n + 1)] for j in range(k + 1)]
	for i in range(1, n + 1):
		a[0][i][1] = 1
	for i in range(1, k + 1):
		(l, r) = [int(x) for x in input().split()]
		for j in range(1, n + 1):
			for c1 in range(c):
				if l <= j <= r:
					for c2 in range(c):
						a[i][j][c1 * c2 % c] += a[i - 1][j][c1] / (2 * c)
					a[i][j][c1] += a[i - 1][j][c1] * 0.5
				else:
					a[i][j][c1] += a[i - 1][j][c1]
	ans = 0
	for i in range(1, n + 1):
		for j in range(c):
			ans += a[k][i][j] * j
	print(ans)


for _ in range(int(input())):
	(n, c, k) = [int(x) for x in input().split()]
	dp = [[[0 for i in range(c)] for j in range(n + 1)] for j in range(k + 1)]
	for i in range(1, n + 1):
		dp[0][i][1] = 1
	for i in range(1, k + 1):
		(l, r) = [int(x) for x in input().split()]
		for j in range(1, n + 1):
			for c1 in range(c):
				if l <= j <= r:
					for c2 in range(c):
						dp[i][j][c1 * c2 % c] += dp[i - 1][j][c1] * (0.5 / c)
					dp[i][j][c1] += dp[i - 1][j][c1] * 0.5
				else:
					dp[i][j][c1] += dp[i - 1][j][c1]
	ans = 0
	for i in range(1, n + 1):
		for j in range(c):
			ans += dp[k][i][j] * j
	print(ans)


def calcEV(n, c, k, lr):
	pr = [[0] * c for i in range(k + 1)]
	pr[0][1] = 1
	ev = [0] * (k + 1)
	ev[0] = 1
	for k_index in range(1, k + 1):
		p = 0.5 / c
		for cell_color in range(c):
			for picked_color in range(c):
				resulting_color = cell_color * picked_color % c
				pr[k_index][resulting_color] += p * pr[k_index - 1][cell_color]
			pr[k_index][cell_color] += 0.5 * pr[k_index - 1][cell_color]
		for cell_color in range(c):
			ev[k_index] += cell_color * pr[k_index][cell_color]
	num_visits = [0] * n
	for k_index in range(k):
		for n_index in range(n):
			if lr[k_index][0] - 1 <= n_index and n_index <= lr[k_index][1] - 1:
				num_visits[n_index] += 1
	sum_ev = 0
	for n_index in range(n):
		sum_ev += ev[num_visits[n_index]]
	print(sum_ev)
numTests = int(input())
for test in range(numTests):
	(n, c, k) = map(int, input().split(' '))
	lr = []
	for i in range(k):
		(l, r) = map(int, input().split(' '))
		lr.append((l, r))
	calcEV(n, c, k, lr)


import math

def Solve(i, acc, c):
	if i == 0:
		return acc
	if (i, acc, c) in Mem:
		return Mem[i, acc, c]
	ans = 0
	for j in range(c):
		ans += 1 / c * Solve(i - 1, acc * j % c, c)
	Mem[i, acc, c] = ans
	return ans

def nCr(x, y):
	return math.factorial(x) // (math.factorial(y) * math.factorial(x - y))
Mem = {}
T = int(input())
for t in range(T):
	(n, c, k) = map(int, input().split())
	Cnt = [0] * n
	for i in range(k):
		(x, y) = map(int, input().split())
		for j in range(x - 1, y):
			Cnt[j] += 1
	ans = 0
	for i in range(n):
		f = (1 / 2) ** Cnt[i]
		for j in range(Cnt[i] + 1):
			ans += f * Solve(j, 1, c) * nCr(Cnt[i], j)
	print(ans)


nck = [[0 for x in range(0, 102)] for x in range(0, 102)]

def precompute():
	for i in range(0, 102):
		for j in range(0, 102):
			if j == 0 or i == j:
				nck[i][j] = 1
			else:
				nck[i][j] = nck[i - 1][j - 1] + nck[i - 1][j]
precompute()
test = int(input())
while test:
	color = [[0 for x in range(0, 102)] for x in range(0, 52)]
	csum = [0 for x in range(0, 52)]
	count = [0 for x in range(0, 102)]
	csum[0] = 1
	ans = 0
	(n, c, k) = input().split()
	n = int(n)
	c = int(c)
	k = int(k)
	for i in range(0, c):
		color[1][i] = 1
		csum[1] += i / c
	for i in range(2, 51):
		for j in range(0, c):
			for kk in range(0, c):
				col = j * kk % c
				color[i][col] += color[i - 1][j]
		for j in range(0, c):
			csum[i] += j * color[i][j]
		csum[i] /= pow(c, i)
	for i in range(0, k):
		(l, r) = input().split()
		l = int(l)
		r = int(r)
		for j in range(l, r + 1):
			count[j] += 1
	for i in range(1, n + 1):
		temp = 0.0
		ctr = count[i]
		for j in range(0, ctr + 1):
			temp += nck[ctr][j] / pow(2, ctr) * csum[j]
		ans += temp
	print('{0:.9f}'.format(ans))
	test = test - 1


from math import factorial

def binom(n, k):
	return factorial(n) // factorial(k) // factorial(n - k)

def main():
	T = int(input())
	for t in range(T):
		(n, c, k) = tuple([int(x) for x in input().split()])
		freq = [0 for i in range(n + 1)]
		for q in range(k):
			(l, r) = tuple([int(x) for x in input().split()])
			for i in range(l, r + 1):
				freq[i] += 1
		ansa = []
		a = [0 for i in range(c)]
		a[1] = 1
		for k in range(51):
			ansa.append(sum([i * a[i] for i in range(c)]) / c ** k)
			b = [0 for i in range(c)]
			for i in range(c):
				for j in range(c):
					z = i * j % c
					b[z] += a[i]
			a = [x for x in b]
		ans = 0
		for x in range(1, n + 1):
			tmp = 0
			for k in range(0, freq[x] + 1):
				tmp += ansa[k] * binom(freq[x], k)
			tmp /= 2 ** freq[x]
			ans += tmp
		print('%0.12f' % ans)
main()