1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<algorithm>
#include<cstdio>
#include<vector>

#include "message.h"
#include "palindromy.h"
using namespace std;

template<class T>
T sum(vector<T> const & vec) {
	T sum(0);
    for(auto const & val : vec)
		sum += val;
	return sum;
}

struct Manacher {

	static char GetLetter(long long i) {
		if(i == 0)
			return '\x02';
		if(i == ::GetLength() + 1)
			return '\x03';
		return ::GetLetter(i - 1);
	}
	static long long GetLength() {
		return ::GetLength() + 2;
	}

	static vector<long long> main(long long m) {
		vector<long long> R(GetLength());
		R[0] = 0;
		long long i = 1, t = 0;
		while(i < GetLength() - 1) {
//			printf("i: %lli, t: %lli\n", i, t);
			while(GetLetter(i - t - m) == GetLetter(i + t + 1))
				++t;
			R[i] = t;
			long long k = 1;
			while(k <= R[i] && R[i-k] != R[i]-k) {
				R[i+k] = min(R[i-k], R[i]-k);
				++k;
			}
			t = max(t-k, 0LL);
			i += k;
		}
		return R;
	}

};

int main() {
	if(MyNodeId() == 0)
        printf("%lli", sum(Manacher::main(0)) + sum(Manacher::main(1)) + GetLength());
}