Codechef July 2013 Prob: the ultimate troll question

First, I had no idea how to solve this at all. There is no way to brute force it for such extremely large numbers.

Then, I saw this comment:

sikander_nsit @ 10 Jul 2013 09:58 PM

I was trolled by this question in two phases : First after solving for two hours I was like "oh man, awesome question. So one part of the question remains" then after 5 hours of PnC and probability, when I saw it I was like "mother of all trolls" serious mindfuck question.

I knew there had to be a shortcut somewhere. Hence, I worked out the first sample test case for t4=1. Yielded the result of 0.5. Could it be that the output is the same regardless of how many tickets Chef discards?

Investigating further, I made a program that calculates the probability of every single combination, a.k.a brute forcing the solution. Code here. Of course, I would only load the program with small inputs. The result:

Input:

	9
	2 2 1 0
	2 2 1 1
	2 2 1 2
	2 2 1 3
	2 3 4 0
	2 3 4 1
	2 3 4 2
	2 3 4 3
	2 3 4 4

view raw gistfile1.txt hosted with ❤ by GitHub

Output:

	0.5
	0.5
	0.5
	0.5
	0.4
	0.4
	0.4
	0.4
	0.4

view raw gistfile1.txt hosted with ❤ by GitHub

I found the shortcut! Indeed, the probability is the same regardless of how many tickets Chef discarded. Happily discarded T4 from my program, submitted it, only to get a runtime error. Turns out my stack has run out of space due to too many recursive calls from T3. Hmm, I thought, I could make the calculation non-recursive, but it is still up to 1000000000 calculations for a single test. Another shortcut must exist!

Went back to the question to look for more patterns. Discovered than 0.5 = 2/(2+2) for first sample test case, and 0.4 = 2/(2+3) for second test case. T3 is also not needed!

Submitted a program consisting of just these few lines:

	import sys
	T = int(sys.stdin.readline().strip())
	for t in range(T):
	t1,t2,t3,t4 = sys.stdin.readline().strip().split()
	t1,t2,t3,t4 = int(t1),int(t2),int(t3),int(t4)
	print t1 * 1.0 / (t1+t2)

view raw gistfile1.txt hosted with ❤ by GitHub

ANDDDDDDDDDDDDDDDDD


Ultimate troll question.

Codechef July 2013 Galactik

First, to find out where to build the bridges, I had to find out what islands/isolated pockets of planets are there. This can be done by a connected components algorithm, simple enough.

Next step, to choose which islands to build the teleporters on....I had no idea. Dug through the comments on the question page for hints. I found this big one:

qwaker00 @ 5 Jul 2013 07:19 PM

Can GFA create more than one teleport on a planet?

zwolf10003 @ 5 Jul 2013 07:59 PM

Please specify if GFA can construct more than one teleport ending on a planet.

jay_adm @ 5 Jul 2013 10:14 PM

@zwolf10003 ,@qwaker00: yes.

Hence, I could just build one end of all teleporters on the same planet. And of course, that planet would offer the cheapest rate in the galaxy for building one!

The other end would go to each individual island/component. And for each island, the best place to end the teleporter would be the cheapest planet in the island.

With the solution planned out I proceeded to code it out in Python. Code here. Worked perfectly, but when submitted:


Sigh.

Time for port over to C++ again. But before that, I made a search for the fastest I/O operation I can achieve on C++. I landed upon this blog post. Tried the last method, but found that Windows does not have getchar_unlocked(). Replaced it with getchar() instead.

The result:

	#include <iostream>
	#include <stdio.h>
	#include <vector>
	#include <stack>
	#include <map>
	#define MAX_N 100000
	#define MAX_M 1000000
	using namespace std;
	bool travelled[MAX_N] = {false};
	vector<int> islandMinCost;
	int cost[MAX_N];
	int N,M;
	//map<int, vector<int> > edges;
	vector<int> edges[MAX_N];
	void makeIslands()
	{
	for (int n=0;n<N;n++)
	{
	if (!travelled[n])
	{
	int minCost = cost[n];
	stack<int> toVisit;
	toVisit.push(n);
	while (!toVisit.empty())
	{
	int current = toVisit.top();
	//printf("current %d cost %d\n", current, cost[current]);
	toVisit.pop();
	if (travelled[current])
	continue;
	travelled[current] = true;
	if (cost[current] >= 0 && cost[current] < minCost)
	minCost = cost[current];
	if (minCost < 0)
	minCost = cost[current];
	for (vector<int>::iterator iter = edges[current].begin(); iter != edges[current].end(); iter++)
	{
	toVisit.push(*iter);
	}
	}
	islandMinCost.push_back(minCost);
	}
	}
	}
	inline void fastRead(int *a)
	{
	register char c=0;
	bool negative = false;
	while (c<33) c=getchar();
	*a=0;
	while (c>33)
	{
	if (c == '-')
	negative = true;
	else
	*a=*a*10+c-'0';
	c=getchar();
	}
	if (negative)
	*a = *a * -1;
	}
	int main()
	{
	int A,B,C;
	fastRead(&N);
	fastRead(&M);
	// printf("%d %d\n", N,M);
	for (int m=0;m<M;m++)
	{
	fastRead(&A);
	fastRead(&B);
	//printf("%d %d\n", A,B);
	A -= 1;
	B -= 1;
	edges[A].push_back(B);
	edges[B].push_back(A);
	}
	for (int n=0;n<N;n++)
	{
	fastRead(&C);
	// printf("%d\t",C);
	cost[n] = C;
	}
	makeIslands();
	int cheapestIsland = islandMinCost[0];
	int totalCost = 0;
	for (vector<int>::iterator iter = islandMinCost.begin(); iter != islandMinCost.end(); iter++)
	{
	//cout << *iter << " ";
	if (*iter < 0)
	{
	totalCost = -1;
	break;
	}
	if (*iter < cheapestIsland)
	cheapestIsland = *iter;
	totalCost += *iter;
	}
	// cout <<endl;
	if (totalCost >= 0)
	totalCost += (islandMinCost.size()-2) * cheapestIsland;
	if (islandMinCost.size() == 1)
	totalCost = 0;
	cout << totalCost;
	return 0;
	}

view raw gistfile1.txt hosted with ❤ by GitHub

It's accepted!

Codechef Jun 2013 Collect

Coded first in Python, time limit exceeded.

	# 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

view raw gistfile1.txt hosted with ❤ by GitHub

Then ported over to C++, time limited exceeded again.

	#include <vector>
	#include <cstdlib>
	#include <iostream>
	#include <iomanip>
	#include <string>
	#include <ctime>
	#define modo 3046201
	using namespace std;
	// base and base_digits must be consistent
	const int base = 1000000000;
	const int base_digits = 9;
	struct bigint {
	vector<int> a;
	int sign;
	bigint() :
	sign(1) {
	}
	bigint(long long v) {
	*this = v;
	}
	bigint(const string &s) {
	read(s);
	}
	void operator=(const bigint &v) {
	sign = v.sign;
	a = v.a;
	}
	void operator=(long long v) {
	sign = 1;
	if (v < 0)
	sign = -1, v = -v;
	for (; v > 0; v = v / base)
	a.push_back(v % base);
	}
	bigint operator+(const bigint &v) const {
	if (sign == v.sign) {
	bigint res = v;
	for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
	if (i == (int) res.a.size())
	res.a.push_back(0);
	res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
	carry = res.a[i] >= base;
	if (carry)
	res.a[i] -= base;
	}
	return res;
	}
	return *this - (-v);
	}
	bigint operator-(const bigint &v) const {
	if (sign == v.sign) {
	if (abs() >= v.abs()) {
	bigint res = *this;
	for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
	res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
	carry = res.a[i] < 0;
	if (carry)
	res.a[i] += base;
	}
	res.trim();
	return res;
	}
	return -(v - *this);
	}
	return *this + (-v);
	}
	void operator*=(int v) {
	if (v < 0)
	sign = -sign, v = -v;
	for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
	if (i == (int) a.size())
	a.push_back(0);
	long long cur = a[i] * (long long) v + carry;
	carry = (int) (cur / base);
	a[i] = (int) (cur % base);
	//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
	}
	trim();
	}
	bigint operator*(int v) const {
	bigint res = *this;
	res *= v;
	return res;
	}
	friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
	int norm = base / (b1.a.back() + 1);
	bigint a = a1.abs() * norm;
	bigint b = b1.abs() * norm;
	bigint q, r;
	q.a.resize(a.a.size());
	for (int i = a.a.size() - 1; i >= 0; i--) {
	r *= base;
	r += a.a[i];
	int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
	int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
	int d = ((long long) base * s1 + s2) / b.a.back();
	r -= b * d;
	while (r < 0)
	r += b, --d;
	q.a[i] = d;
	}
	q.sign = a1.sign * b1.sign;
	r.sign = a1.sign;
	q.trim();
	r.trim();
	return make_pair(q, r / norm);
	}
	bigint operator/(const bigint &v) const {
	return divmod(*this, v).first;
	}
	bigint operator%(const bigint &v) const {
	return divmod(*this, v).second;
	}
	void operator/=(int v) {
	if (v < 0)
	sign = -sign, v = -v;
	for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
	long long cur = a[i] + rem * (long long) base;
	a[i] = (int) (cur / v);
	rem = (int) (cur % v);
	}
	trim();
	}
	bigint operator/(int v) const {
	bigint res = *this;
	res /= v;
	return res;
	}
	int operator%(int v) const {
	if (v < 0)
	v = -v;
	int m = 0;
	for (int i = a.size() - 1; i >= 0; --i)
	m = (a[i] + m * (long long) base) % v;
	return m * sign;
	}
	void operator+=(const bigint &v) {
	*this = *this + v;
	}
	void operator-=(const bigint &v) {
	*this = *this - v;
	}
	void operator*=(const bigint &v) {
	*this = *this * v;
	}
	void operator/=(const bigint &v) {
	*this = *this / v;
	}
	bool operator<(const bigint &v) const {
	if (sign != v.sign)
	return sign < v.sign;
	if (a.size() != v.a.size())
	return a.size() * sign < v.a.size() * v.sign;
	for (int i = a.size() - 1; i >= 0; i--)
	if (a[i] != v.a[i])
	return a[i] * sign < v.a[i] * sign;
	return false;
	}
	bool operator>(const bigint &v) const {
	return v < *this;
	}
	bool operator<=(const bigint &v) const {
	return !(v < *this);
	}
	bool operator>=(const bigint &v) const {
	return !(*this < v);
	}
	bool operator==(const bigint &v) const {
	return !(*this < v) && !(v < *this);
	}
	bool operator!=(const bigint &v) const {
	return *this < v || v < *this;
	}
	void trim() {
	while (!a.empty() && !a.back())
	a.pop_back();
	if (a.empty())
	sign = 1;
	}
	bool isZero() const {
	return a.empty() || (a.size() == 1 && !a[0]);
	}
	bigint operator-() const {
	bigint res = *this;
	res.sign = -sign;
	return res;
	}
	bigint abs() const {
	bigint res = *this;
	res.sign *= res.sign;
	return res;
	}
	long long longValue() const {
	long long res = 0;
	for (int i = a.size() - 1; i >= 0; i--)
	res = res * base + a[i];
	return res * sign;
	}
	friend bigint gcd(const bigint &a, const bigint &b) {
	return b.isZero() ? a : gcd(b, a % b);
	}
	friend bigint lcm(const bigint &a, const bigint &b) {
	return a / gcd(a, b) * b;
	}
	void read(const string &s) {
	sign = 1;
	a.clear();
	int pos = 0;
	while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
	if (s[pos] == '-')
	sign = -sign;
	++pos;
	}
	for (int i = s.size() - 1; i >= pos; i -= base_digits) {
	int x = 0;
	for (int j = max(pos, i - base_digits + 1); j <= i; j++)
	x = x * 10 + s[j] - '0';
	a.push_back(x);
	}
	trim();
	}
	friend istream& operator>>(istream &stream, bigint &v) {
	string s;
	stream >> s;
	v.read(s);
	return stream;
	}
	friend ostream& operator<<(ostream &stream, const bigint &v) {
	if (v.sign == -1)
	stream << '-';
	stream << (v.a.empty() ? 0 : v.a.back());
	for (int i = (int) v.a.size() - 2; i >= 0; --i)
	stream << setw(base_digits) << setfill('0') << v.a[i];
	return stream;
	}
	static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
	vector<long long> p(max(old_digits, new_digits) + 1);
	p[0] = 1;
	for (int i = 1; i < (int) p.size(); i++)
	p[i] = p[i - 1] * 10;
	vector<int> res;
	long long cur = 0;
	int cur_digits = 0;
	for (int i = 0; i < (int) a.size(); i++) {
	cur += a[i] * p[cur_digits];
	cur_digits += old_digits;
	while (cur_digits >= new_digits) {
	res.push_back(int(cur % p[new_digits]));
	cur /= p[new_digits];
	cur_digits -= new_digits;
	}
	}
	res.push_back((int) cur);
	while (!res.empty() && !res.back())
	res.pop_back();
	return res;
	}
	typedef vector<long long> vll;
	static vll karatsubaMultiply(const vll &a, const vll &b) {
	int n = a.size();
	vll res(n + n);
	if (n <= 32) {
	for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++)
	res[i + j] += a[i] * b[j];
	return res;
	}
	int k = n >> 1;
	vll a1(a.begin(), a.begin() + k);
	vll a2(a.begin() + k, a.end());
	vll b1(b.begin(), b.begin() + k);
	vll b2(b.begin() + k, b.end());
	vll a1b1 = karatsubaMultiply(a1, b1);
	vll a2b2 = karatsubaMultiply(a2, b2);
	for (int i = 0; i < k; i++)
	a2[i] += a1[i];
	for (int i = 0; i < k; i++)
	b2[i] += b1[i];
	vll r = karatsubaMultiply(a2, b2);
	for (int i = 0; i < (int) a1b1.size(); i++)
	r[i] -= a1b1[i];
	for (int i = 0; i < (int) a2b2.size(); i++)
	r[i] -= a2b2[i];
	for (int i = 0; i < (int) r.size(); i++)
	res[i + k] += r[i];
	for (int i = 0; i < (int) a1b1.size(); i++)
	res[i] += a1b1[i];
	for (int i = 0; i < (int) a2b2.size(); i++)
	res[i + n] += a2b2[i];
	return res;
	}
	bigint operator*(const bigint &v) const {
	vector<int> a6 = convert_base(this->a, base_digits, 6);
	vector<int> b6 = convert_base(v.a, base_digits, 6);
	vll a(a6.begin(), a6.end());
	vll b(b6.begin(), b6.end());
	while (a.size() < b.size())
	a.push_back(0);
	while (b.size() < a.size())
	b.push_back(0);
	while (a.size() & (a.size() - 1))
	a.push_back(0), b.push_back(0);
	vll c = karatsubaMultiply(a, b);
	bigint res;
	res.sign = sign * v.sign;
	for (int i = 0, carry = 0; i < (int) c.size(); i++) {
	long long cur = c[i] + carry;
	res.a.push_back((int) (cur % 1000000));
	carry = (int) (cur / 1000000);
	}
	res.a = convert_base(res.a, 6, base_digits);
	res.trim();
	return res;
	}
	};
	bigint modular_expo(bigint a, bigint b, bigint n)
	{
	bigint c(b);
	string binary;
	while (c > 0)
	{
	if (c%2 == 1)
	binary += "1";
	else
	binary += "0";
	c /= 2;
	}
	bigint result("1");
	for (int i=0;i<binary.length();i++)
	{
	result = (result * result)%n;
	if (binary.at(binary.length()-i-1) == '1')
	result = (result * a)%n;
	}
	return result;
	}
	bigint fermat(bigint a,bigint p)
	{
	return modular_expo(a,p-2,p);
	}
	int main() {
	unsigned int N,Q,l,r;
	string query;
	int* n = new int[100000];
	// input
	cin >> N;
	for (int z=0;z<N;z++)
	{
	cin >> n[z];
	}
	cin >> Q;
	// initialize factorials
	bigint* factorials = new bigint[N*30+1];
	factorials[0] = 1;
	factorials[1] = 1;
	for (unsigned int i=2;i<N*30+1;i++)
	{
	factorials[i] = (factorials[i-1]*i)%modo;
	}
	for (int z=0;z<Q;z++)
	{
	cin >> query >> l >> r;
	if (query == "change")
	{
	n[l-1] = r;
	} else if (query == "query")
	{
	// count berries and people
	unsigned int berries = 0, people = r-l+1;
	for (int k=l-1;k<r;k++)
	{
	berries += n[k];
	}
	unsigned int lessBerries = berries/people;
	unsigned int moreBerries = lessBerries + 1;
	unsigned int moreBerriesSize = berries % people;
	unsigned int lessBerriesSize = people - moreBerriesSize;
	bigint result
	= (factorials[berries]
	* factorials[people]
	* fermat(
	(factorials[moreBerriesSize]
	* factorials[lessBerriesSize]
	* modular_expo(factorials[moreBerries], moreBerriesSize, modo)
	* modular_expo(factorials[lessBerries], lessBerriesSize, modo)
	),modo)
	) % modo;
	cout << result << endl;
	}
	}
	return 0;
	}

view raw gistfile1.txt hosted with ❤ by GitHub

Reviewed the editorial, added segment trees to facilitate range querying, but still exceeded time limit!

	// time limit exceeded
	#include <vector>
	#include <stdio.h>
	#include <cstdlib>
	#include <iostream>
	#include <iomanip>
	#include <string>
	#include <ctime>
	#define modo 3046201
	using namespace std;
	// base and base_digits must be consistent
	const int base = 1000000000;
	const int base_digits = 9;
	class Segtree
	{
	private:
	int* nodes;
	int num_leaves;
	public:
	Segtree(int size1, int* values)
	{
	num_leaves = 1;
	int size2 = size1;
	while (size2 > 1)
	{
	size2 -= int(size2/2);
	num_leaves *= 2;
	}
	nodes = new int[num_leaves*2];
	// init
	for (int i=0;i<num_leaves*2;i++)
	nodes[i] = 0;
	// copy the values
	for (int j=0;j<size1;j++)
	{
	nodes[num_leaves-1+j] = values[j];
	}
	// summarize the leaves
	for (int i=num_leaves-2;i>=0;i--)
	{
	nodes[i] = nodes[i*2+1] + nodes[i*2+2];
	}
	};
	void update(int node, int value)
	{
	node = num_leaves-1+node;
	nodes[node] = value;
	int i = node;
	while (i>0)
	{
	if (i%2 == 0)
	{
	nodes[(i-2)/2] = nodes[i] + nodes[i-1];
	i = (i-2)/2;
	} else {
	nodes[(i-1)/2] = nodes[i] + nodes[i+1];
	i = (i-1)/2;
	}
	}
	};
	int query(int queryStart, int queryEnd)
	{
	return query(0, 0, num_leaves-1, queryStart-1, queryEnd-1);
	};
	int query(int curNode, int rangeStart, int rangeEnd, int queryStart, int queryEnd)
	{
	if (rangeEnd < queryStart) return 0;
	if (rangeStart > queryEnd) return 0;
	if (queryStart <= rangeStart && rangeEnd <= queryEnd)
	return nodes[curNode];
	int midNode = int((rangeEnd - rangeStart)/2)+rangeStart;
	return query(curNode*2+1, rangeStart, midNode, queryStart, queryEnd) + query(curNode*2+2, midNode+1,rangeEnd, queryStart, queryEnd);
	};
	void display()
	{
	for (int i=0;i<num_leaves*2;i++)
	{
	cout << nodes[i] << " ";
	}
	cout<<endl;
	}
	};
	struct bigint {
	vector<int> a;
	int sign;
	bigint() :
	sign(1) {
	}
	bigint(long long v) {
	*this = v;
	}
	bigint(const string &s) {
	read(s);
	}
	void operator=(const bigint &v) {
	sign = v.sign;
	a = v.a;
	}
	void operator=(long long v) {
	sign = 1;
	if (v < 0)
	sign = -1, v = -v;
	for (; v > 0; v = v / base)
	a.push_back(v % base);
	}
	bigint operator+(const bigint &v) const {
	if (sign == v.sign) {
	bigint res = v;
	for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
	if (i == (int) res.a.size())
	res.a.push_back(0);
	res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
	carry = res.a[i] >= base;
	if (carry)
	res.a[i] -= base;
	}
	return res;
	}
	return *this - (-v);
	}
	bigint operator-(const bigint &v) const {
	if (sign == v.sign) {
	if (abs() >= v.abs()) {
	bigint res = *this;
	for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
	res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
	carry = res.a[i] < 0;
	if (carry)
	res.a[i] += base;
	}
	res.trim();
	return res;
	}
	return -(v - *this);
	}
	return *this + (-v);
	}
	void operator*=(int v) {
	if (v < 0)
	sign = -sign, v = -v;
	for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
	if (i == (int) a.size())
	a.push_back(0);
	long long cur = a[i] * (long long) v + carry;
	carry = (int) (cur / base);
	a[i] = (int) (cur % base);
	//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
	}
	trim();
	}
	bigint operator*(int v) const {
	bigint res = *this;
	res *= v;
	return res;
	}
	friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
	int norm = base / (b1.a.back() + 1);
	bigint a = a1.abs() * norm;
	bigint b = b1.abs() * norm;
	bigint q, r;
	q.a.resize(a.a.size());
	for (int i = a.a.size() - 1; i >= 0; i--) {
	r *= base;
	r += a.a[i];
	int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
	int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
	int d = ((long long) base * s1 + s2) / b.a.back();
	r -= b * d;
	while (r < 0)
	r += b, --d;
	q.a[i] = d;
	}
	q.sign = a1.sign * b1.sign;
	r.sign = a1.sign;
	q.trim();
	r.trim();
	return make_pair(q, r / norm);
	}
	bigint operator/(const bigint &v) const {
	return divmod(*this, v).first;
	}
	bigint operator%(const bigint &v) const {
	return divmod(*this, v).second;
	}
	void operator/=(int v) {
	if (v < 0)
	sign = -sign, v = -v;
	for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
	long long cur = a[i] + rem * (long long) base;
	a[i] = (int) (cur / v);
	rem = (int) (cur % v);
	}
	trim();
	}
	bigint operator/(int v) const {
	bigint res = *this;
	res /= v;
	return res;
	}
	int operator%(int v) const {
	if (v < 0)
	v = -v;
	int m = 0;
	for (int i = a.size() - 1; i >= 0; --i)
	m = (a[i] + m * (long long) base) % v;
	return m * sign;
	}
	void operator+=(const bigint &v) {
	*this = *this + v;
	}
	void operator-=(const bigint &v) {
	*this = *this - v;
	}
	void operator*=(const bigint &v) {
	*this = *this * v;
	}
	void operator/=(const bigint &v) {
	*this = *this / v;
	}
	bool operator<(const bigint &v) const {
	if (sign != v.sign)
	return sign < v.sign;
	if (a.size() != v.a.size())
	return a.size() * sign < v.a.size() * v.sign;
	for (int i = a.size() - 1; i >= 0; i--)
	if (a[i] != v.a[i])
	return a[i] * sign < v.a[i] * sign;
	return false;
	}
	bool operator>(const bigint &v) const {
	return v < *this;
	}
	bool operator<=(const bigint &v) const {
	return !(v < *this);
	}
	bool operator>=(const bigint &v) const {
	return !(*this < v);
	}
	bool operator==(const bigint &v) const {
	return !(*this < v) && !(v < *this);
	}
	bool operator!=(const bigint &v) const {
	return *this < v || v < *this;
	}
	void trim() {
	while (!a.empty() && !a.back())
	a.pop_back();
	if (a.empty())
	sign = 1;
	}
	bool isZero() const {
	return a.empty() || (a.size() == 1 && !a[0]);
	}
	bigint operator-() const {
	bigint res = *this;
	res.sign = -sign;
	return res;
	}
	bigint abs() const {
	bigint res = *this;
	res.sign *= res.sign;
	return res;
	}
	long long longValue() const {
	long long res = 0;
	for (int i = a.size() - 1; i >= 0; i--)
	res = res * base + a[i];
	return res * sign;
	}
	friend bigint gcd(const bigint &a, const bigint &b) {
	return b.isZero() ? a : gcd(b, a % b);
	}
	friend bigint lcm(const bigint &a, const bigint &b) {
	return a / gcd(a, b) * b;
	}
	void read(const string &s) {
	sign = 1;
	a.clear();
	int pos = 0;
	while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
	if (s[pos] == '-')
	sign = -sign;
	++pos;
	}
	for (int i = s.size() - 1; i >= pos; i -= base_digits) {
	int x = 0;
	for (int j = max(pos, i - base_digits + 1); j <= i; j++)
	x = x * 10 + s[j] - '0';
	a.push_back(x);
	}
	trim();
	}
	friend istream& operator>>(istream &stream, bigint &v) {
	string s;
	stream >> s;
	v.read(s);
	return stream;
	}
	friend ostream& operator<<(ostream &stream, const bigint &v) {
	if (v.sign == -1)
	stream << '-';
	stream << (v.a.empty() ? 0 : v.a.back());
	for (int i = (int) v.a.size() - 2; i >= 0; --i)
	stream << setw(base_digits) << setfill('0') << v.a[i];
	return stream;
	}
	static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
	vector<long long> p(max(old_digits, new_digits) + 1);
	p[0] = 1;
	for (int i = 1; i < (int) p.size(); i++)
	p[i] = p[i - 1] * 10;
	vector<int> res;
	long long cur = 0;
	int cur_digits = 0;
	for (int i = 0; i < (int) a.size(); i++) {
	cur += a[i] * p[cur_digits];
	cur_digits += old_digits;
	while (cur_digits >= new_digits) {
	res.push_back(int(cur % p[new_digits]));
	cur /= p[new_digits];
	cur_digits -= new_digits;
	}
	}
	res.push_back((int) cur);
	while (!res.empty() && !res.back())
	res.pop_back();
	return res;
	}
	typedef vector<long long> vll;
	static vll karatsubaMultiply(const vll &a, const vll &b) {
	int n = a.size();
	vll res(n + n);
	if (n <= 32) {
	for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++)
	res[i + j] += a[i] * b[j];
	return res;
	}
	int k = n >> 1;
	vll a1(a.begin(), a.begin() + k);
	vll a2(a.begin() + k, a.end());
	vll b1(b.begin(), b.begin() + k);
	vll b2(b.begin() + k, b.end());
	vll a1b1 = karatsubaMultiply(a1, b1);
	vll a2b2 = karatsubaMultiply(a2, b2);
	for (int i = 0; i < k; i++)
	a2[i] += a1[i];
	for (int i = 0; i < k; i++)
	b2[i] += b1[i];
	vll r = karatsubaMultiply(a2, b2);
	for (int i = 0; i < (int) a1b1.size(); i++)
	r[i] -= a1b1[i];
	for (int i = 0; i < (int) a2b2.size(); i++)
	r[i] -= a2b2[i];
	for (int i = 0; i < (int) r.size(); i++)
	res[i + k] += r[i];
	for (int i = 0; i < (int) a1b1.size(); i++)
	res[i] += a1b1[i];
	for (int i = 0; i < (int) a2b2.size(); i++)
	res[i + n] += a2b2[i];
	return res;
	}
	bigint operator*(const bigint &v) const {
	vector<int> a6 = convert_base(this->a, base_digits, 6);
	vector<int> b6 = convert_base(v.a, base_digits, 6);
	vll a(a6.begin(), a6.end());
	vll b(b6.begin(), b6.end());
	while (a.size() < b.size())
	a.push_back(0);
	while (b.size() < a.size())
	b.push_back(0);
	while (a.size() & (a.size() - 1))
	a.push_back(0), b.push_back(0);
	vll c = karatsubaMultiply(a, b);
	bigint res;
	res.sign = sign * v.sign;
	for (int i = 0, carry = 0; i < (int) c.size(); i++) {
	long long cur = c[i] + carry;
	res.a.push_back((int) (cur % 1000000));
	carry = (int) (cur / 1000000);
	}
	res.a = convert_base(res.a, 6, base_digits);
	res.trim();
	return res;
	}
	};
	bigint modular_expo(bigint a, bigint b, bigint n)
	{
	bigint c(b);
	string binary;
	while (c > 0)
	{
	if (c%2 == 1)
	binary += "1";
	else
	binary += "0";
	c /= 2;
	}
	bigint result("1");
	for (int i=0;i<binary.length();i++)
	{
	result = (result * result)%n;
	if (binary.at(binary.length()-i-1) == '1')
	result = (result * a)%n;
	}
	return result;
	}
	bigint fermat(bigint a,bigint p)
	{
	return modular_expo(a,p-2,p);
	}
	int main() {
	unsigned int N,Q,l,r;
	string query;
	int* n = new int[100000];
	// input
	cin >> N;
	for (int z=0;z<N;z++)
	{
	cin >> n[z];
	}
	cin >> Q;
	Segtree* segtree = new Segtree(N, n);
	// initialize factorials
	bigint* factorials = new bigint[N*30+1];
	factorials[0] = 1;
	factorials[1] = 1;
	for (unsigned int i=2;i<N*30+1;i++)
	{
	factorials[i] = (factorials[i-1]*i)%modo;
	}
	for (int z=0;z<Q;z++)
	{
	cin >> query >> l >> r;
	if (query == "change")
	{
	n[l-1] = r;
	segtree->update(l-1,r);
	} else if (query == "query")
	{
	// count berries and people
	unsigned int berries = 0, people = r-l+1;
	berries = segtree->query(l,r);
	unsigned int lessBerries = berries/people;
	unsigned int moreBerries = lessBerries + 1;
	unsigned int moreBerriesSize = berries % people;
	unsigned int lessBerriesSize = people - moreBerriesSize;
	bigint result
	= (factorials[berries]
	* factorials[people]
	* fermat(
	(factorials[moreBerriesSize]
	* factorials[lessBerriesSize]
	* modular_expo(factorials[moreBerries], moreBerriesSize, modo)
	* modular_expo(factorials[lessBerries], lessBerriesSize, modo)
	),modo)
	) % modo;
	cout << result << endl;
	}
	}
	return 0;
	}

view raw gistfile1.txt hosted with ❤ by GitHub

=_=U