Codechef Jun 2013 Collect

gistfile1.txt

# time limit exceeded again.

#8 people choose 6 people to give 2 berries

#14 berries divide into set of 2,2,2,2,2,2,1,1

#first set   14 c 2 = 14! / 12!2!
#second set  12 c 2 = 12! / 10!2!
#third set   10 c 2 = 10! / 8!2!
#fourth set   8 c 2 =  8! / 6!2!
#fifth set    6 c 2 =  6! / 4!2!
#sixth set    4 c 2 =  4! / 2!2!
#seventh set  2 c 1 =  2! / 1!1!
#eighth set   1 c 1 =  1! /   1!

#number of ways to divide 14 berries into 8 sets

#(14!/2^6 * 8C6) mod 3046201 = 2065880



# 16 berries, 5 people

# 16 berries divide into set of 4,3,3,3,3
# 5 people choose 1 to give 4 berries

#first set   16 c 4 = 16! / 12!4!
#second set  12 c 3 = 12! / 9!3!
#third set    9 c 3 =  9! / 6!3!
#fourth set   6 c 3 =  6! / 3!3!
#fifth set    3 c 3 =  3! /   3!


# 26 berries, 4 people

# 26 berries divide into set of 7,7,6,6
# 4 people choose 2 to give 7 berries

#first set   26 c 7 = 26! / 19!7!
#second set  19 c 7 = 19! / 12!7!
#third set   12 c 6 = 12! /  6!6!
#fourth set   6 c 6 =  6! /    6!

# number of ways to choose = (choose people for more berries) * berries! / (bigger size)!^(size of larger set) / (smaller size)!^(size of smaller set)


import sys

modo = 3046201


def modular_exponential(a,b,n):
  binary = ""
	while b > 0:
		if b & 1 == 1:
			binary += "1"
		else:
			binary += "0"
		b >>= 1

	result = 1
	for i in xrange(len(binary)):
		result = (result * result) % n
		if binary[len(binary)-1-i] == "1":
			result = (result * a) % n

	return result


def divides(a,p):
	# Fermat's little theorem: since 3046201 is a prime number, we 
	# can use this
	return modular_exponential(a,p-2,p)


N = int(sys.stdin.readline().strip())

numbers = sys.stdin.readline().strip().split()
for i in xrange(len(numbers)):
	numbers[i] = int(numbers[i])

Q = int(sys.stdin.readline().strip())

factorials = [0]*(N*30+1)
factorials[0] = 1
factorials[1] = 1
for i in xrange(2,N*30+1):
	factorials[i] = (factorials[i-1]*i) % modo

for q in xrange(Q):
	query, l,r = sys.stdin.readline().strip().split()
	l,r = int(l),int(r)
	if query == "change":
		numbers[l-1] = r
	elif query == "query":
		# count berries
		berries = sum(numbers[l-1:r])
		people  = r-l+1
		lessBerries = int(berries / people)
		moreBerries = lessBerries + 1
		moreBerriesSize = berries % people
		lessBerriesSize = people - moreBerriesSize
		#(choose people for more berries) * berries! / (bigger size)!^(size of larger set) / (smaller size)!^(size of smaller set)
		print (factorials[berries]                                                                     \
			* factorials[people]                                                                       \
			* divides(                                                                                 \
				(                                                                                      \
					factorials[moreBerriesSize]                                                        \
					* factorials[lessBerriesSize]                                                      \
					* modular_exponential(factorials[moreBerries],moreBerriesSize,3046201)             \
					* modular_exponential(factorials[lessBerries], lessBerriesSize, 3046201)           \
				), 3046201)                                                                            \
			) % 3046201