CSES - Putka Open 2015 – 5/6 - Results
Submission details
Task:Käännöt
Sender:Henrik Lievonen
Submission time:2015-11-07 19:15:22 +0200
Language:C++
Status:COMPILE ERROR

Compiler report

g++: internal compiler error: Killed (program cc1plus)
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-4.9/README.Bugs> for instructions.

Code

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <array>

using namespace std;

typedef long long int ll;

template<typename T, T M>
struct modnum {
	T val;
	modnum(T val) :val(val%M) {}
	modnum() :val(0) {}

	modnum &operator+=(const modnum &o) {
		val = (val + o.val) % M;
		return *this;
	}
	modnum operator+(const modnum &o) {
		modnum r = *this;
		r += o;
		return r;
	}
	modnum &operator*=(const modnum &o) {
		val = (val * o.val) % M;
		return *this;
	}
	modnum operator*(const modnum &o) {
		modnum r = *this;
		r *= o;
		return r;
	}

	operator T() const {
		return val;
	}
};
typedef modnum<ll, 1000000007> mn;

template<typename T, T M>
modnum<T, M> powmod(modnum<T, M> b, ll e) {
	if (e == 0)
		return 1;
	if (e == 1)
		return b;
	if (e % 2 == 0) {
		modnum<T, M> p = powmod(b, e / 2);
		return p*p;
	}
	return powmod(b, e / 2)*powmod(b, e / 2 + 1);
}

template<typename T, size_t S>
struct seqtree {
	array<T, 2*S> tree{};

	void rawset(size_t i, T val) {
		tree[S + i] = val;
	}
	void rawbuild() {
		for (int i = S - 1; i >= 0; i--)
			tree[i] = tree[2 * i] + tree[2 * i + 1];
	}
	T get(size_t a, size_t b) const {
		a += S;
		b += S;
		T r;
		while (a < b) {
			if (a % 2 == 1)r += tree[a], a++;
			if (b % 2 == 0)r += tree[b], b--;
			a /= 2;
			b /= 2;
		}
		if (a == b)
			r += tree[a];
		return r;
	}
};

ll dojob(const string &s) {
	typedef seqtree<mn, 1024 * 1024> SEQ_T;
	SEQ_T *seq_p = new SEQ_T();
	SEQ_T &seq = *seq_p;

	const ll sl = s.length();

	// Build seqment tree
	{
		for (int i = sl - 1; i >= 0; i--)
			seq.rawset(i, mn(s[i] - '0'));
		seq.rawbuild();
	}

	mn res = 0;
	// Add base grid
	{
		mn add = 0;
		for (int i = 0; i < sl / 2; i++) {
			add += seq.get(i, sl - i - 1);
			res += add*powmod(mn(10), i);
			res += add*powmod(mn(10), sl - i - 1);
		}
		if (sl % 2 != 0) {
			add += seq.get(sl / 2, sl / 2);
			res += add*powmod(mn(10), sl / 2);
		}
	}

	// Add diagonal
	{
		ll mul = sl*(sl - 1) / 2;
		ll sub = sl - 3;
		if (sub < 0) sub = 0;
		for (int i = 0; i < sl / 2; i++) {
			res += seq.get(i, i) * mn(mul) * powmod(mn(10), sl - i - 1);
			res += seq.get(sl - i - 1, sl - i - 1) * mn(mul) * powmod(mn(10), i);

			mul -= sub;
			sub -= 2;
			if (sub < 0) sub = 0;
			mul -= 1;
			//add += seq.get(i, sl - i - 1);
			//res += mn(2)*add;
		}
		if (sl % 2 != 0) {
			res += seq.get(sl / 2, sl / 2) * mn(mul) * powmod(mn(10), sl / 2);
		}
	}

	delete seq_p;

	return res;
}


int main() {
	string s;
	cin >> s;
	cout << dojob(s) << endl;
}