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