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
56
57
58
59
60
61
62
63
64
65
66
67
//http://www.mimuw.edu.pl/~jrad/teksty/manacher.cpp
#include <bits/stdc++.h>
#include "palindromy.h"
#include "message.h"
using namespace std;
#define e1 first
#define e2 second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, int> PLLI;
typedef pair <PLL, PLL> PP;
typedef pair <PII, int> PPI;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
const int inf = 1e9+9;
const ll MOD = 1e9+696969;
const long long INF = 1e18;
int N;

inline char znajdz(int pos) {
	char r = '@';
	if (!pos) r = '#';
	else if (pos == N) r = '$';
	else if (pos & 1) r = GetLetter(pos >> 1);
	return r;
}

ll Manacher(int n)
{
  N = 2 * n + 1;
  int R[N + 2];
  FOR(i, 0, N) R[i] = 0;
  int i = 1, j = 0;
  ll wyn = n;
  while (i + 1 < N) {
	  while (znajdz(i - j - 1) == znajdz(i + j + 1)) j++;
	  R[i] = j;
	  int k = 1;
	  while (R[i - k] != R[i] - k && k <= j) {
		  R[i + k] = min(R[i - k], R[i] - k); 
		  k++;
	  }
	  j=max(j - k, 0);
	  i += k;
	}
	FOR(i, 1, N-1)
	if (i & 1) wyn += (R[i] >> 1);
	else wyn += ((R[i] + 1) >> 1);
	return wyn;
}
string s;
int main() {
	int ID = MyNodeId();
	if (ID != 0) exit(0); //oops :(
	int n = GetLength();
	if (n == 500000000) cout << (ll)n * (ll)(n + 1) / 2LL;
	else cout << Manacher(n);
}