Käännöt

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <array>
 
using namespace std;
 
typedef long long int ll;
 
const ll M = 1000000007;
struct modnum {
	ll val;
	modnum(ll 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 ll() const {
		return val;
	}
};
typedef modnum mn;
 
mn powmod(mn b, ll e) {
	if (e == 0)
		return 1;
	if (e == 1)
		return b;
	if (e % 2 == 0) {
		mn p = powmod(b, e / 2);
		return p*p;
	}
	return powmod(b, e / 2)*powmod(b, e / 2 + 1);
}
 
const size_t S = 1024 * 128;
struct seqtree {
	vector<mn> tree;
 
	seqtree() : tree(2 * S) {}
 
	void rawset(size_t i, mn val) {
		tree[S + i] = val;
	}
	void rawbuild() {
		for (int i = S - 1; i >= 0; i--)
			tree[i] = tree[2 * i] + tree[2 * i + 1];
	}
	mn get(size_t a, size_t b) const {
		a += S;
		b += S;
		mn 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 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;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED