結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー antaanta
提出日時 2016-12-15 23:09:04
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,872 ms / 2,000 ms
コード長 5,149 bytes
コンパイル時間 2,189 ms
コンパイル使用メモリ 189,192 KB
実行使用メモリ 98,336 KB
最終ジャッジ日時 2024-11-30 08:57:06
合計ジャッジ時間 28,781 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 4 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 286 ms
6,492 KB
testcase_06 AC 1,467 ms
17,384 KB
testcase_07 AC 292 ms
7,084 KB
testcase_08 AC 1,413 ms
20,444 KB
testcase_09 AC 1,767 ms
32,560 KB
testcase_10 AC 1,769 ms
33,788 KB
testcase_11 AC 1,717 ms
98,336 KB
testcase_12 AC 1,244 ms
78,292 KB
testcase_13 AC 923 ms
49,824 KB
testcase_14 AC 1,651 ms
74,316 KB
testcase_15 AC 1,690 ms
53,696 KB
testcase_16 AC 1,756 ms
44,244 KB
testcase_17 AC 1,768 ms
44,332 KB
testcase_18 AC 1,563 ms
61,868 KB
testcase_19 AC 1,496 ms
47,944 KB
testcase_20 AC 1,523 ms
24,636 KB
testcase_21 AC 1,872 ms
66,392 KB
32_ratsliveonnoevilstar.txt AC 1,672 ms
55,844 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }


struct PalindromicTree {
	typedef int Index;
	typedef char Alpha;
	struct Node {
		//回文の長さ
		Index length;
		//文字列 A が親の回文で、文字 b に対して bAb が自分の回文のとき、border == b となる。
		Alpha border;
		Index head, next;
		//最長接尾回文。S[i,j]がこのnodeの回文の時、S[k,j] (i < k) がnode->suffixの回文となる。
		Index suffix;

		Index diff;
		Index seriesLink, seriesLen;
		Node() { }
		Node(Index length_, Alpha border_, Index next_, Index suffix_) :
			length(length_), border(border_), head(-1), next(next_), suffix(suffix_),
			diff(0), seriesLink(-1), seriesLen(0) { }
	};

	Index nNodes;
	vector<Node> nodes;
	vector<Alpha> alphas;

	void init(Index n) {
		assert(n >= 0);
		nodes.resize(n + 2);
		nodes[0] = Node(-1, '\0', -1, -1);
		nodes[1] = Node(0, '\0', -1, 0);
		nNodes = 2;
		alphas.resize(n);
	}

	Index getOddRoot() const { return 0; }
	Index getEvenRoot() const { return 1; }

	Index findChild(Index i, Alpha alpha) const {
		Index c = nodes[i].head;
		while (c != -1) {
			if (nodes[c].border == alpha)
				return c;
			c = nodes[c].next;
		}
		return -1;
	}

	Index findSuffixExtension(Index i, Index pos, Index beginningPos) const {
		while (1) {
			Index len = nodes[i].length, left = pos - 1 - len;
			if (beginningPos <= left && alphas[left] == alphas[pos])
				return i;
			i = nodes[i].suffix;
		}
	}

	bool processAlphabet(Index &activeIndex, Index pos, Index beginningPos) {
		Alpha alpha = alphas[pos];
		Index parentIndex = findSuffixExtension(activeIndex, pos, beginningPos);
		Index childIndex = findChild(parentIndex, alpha);

		if (childIndex != -1) {
			activeIndex = childIndex;
			return false;
		}
		Node &parent = nodes[parentIndex];

		Index suffixIndex;
		if (parent.length == -1) {
			suffixIndex = getEvenRoot();
		}
		else {
			Index suffixParentIndex = findSuffixExtension(parent.suffix, pos, beginningPos);
			suffixIndex = findChild(suffixParentIndex, alpha);
		}

		childIndex = nNodes++;
		nodes[childIndex] = Node(parent.length + 2, alpha, parent.head, suffixIndex);
		activeIndex = parent.head = childIndex;
		return true;
	}
};

int main() {
	char S[500001];
	while (~scanf("%s", S)) {
		int n = (int)strlen(S);

		PalindromicTree pt;
		pt.init(n);
		vector<int> sufNode(n + 1, -1);
		vector<bool> prePalin(n + 1);
		prePalin[0] = true;
		{
			int activeIndex = pt.getEvenRoot();
			rep(i, n) {
				pt.alphas[i] = S[i];
				pt.processAlphabet(activeIndex, i, 0);
				sufNode[i + 1] = activeIndex;
				prePalin[i + 1] = pt.nodes[activeIndex].length == i + 1;
			}
		}
		reu(i, 2, pt.nNodes) {
			auto &node = pt.nodes[i], &link = pt.nodes[node.suffix];
			node.diff = node.length - link.length;
			if (node.diff == link.diff) {
				node.seriesLink = link.seriesLink;
				node.seriesLen = link.seriesLen + 1;
			}
			else {
				node.seriesLink = node.suffix;
				node.seriesLen = 1;
			}
		}
		vector<int> Ls(n + 1);
		const int Small = 1000;
		vector<vector<pair<int, int>>> queries(Small);
		rer(i, 2, n) {
			int cnt = 0;
			int num = 0;
			for (int u = sufNode[i]; u >= 2; u = pt.nodes[u].seriesLink) {
				++num;
				int initLen = pt.nodes[u].length,
					diff = pt.nodes[u].diff,
					seriesLen = pt.nodes[u].seriesLen;
				if (diff < Small) {
					queries[diff].emplace_back(i - initLen, i * 2 + 1);
					queries[diff].emplace_back(i - initLen + seriesLen * diff, i * 2 + 0);
				}
				else {
					for (int k = 0; k < seriesLen; ++k)
						cnt += prePalin[i - initLen + k * diff];
				}
			}
			//assert(1 << (num - 1) <= n);
			if (prePalin[i])
				--cnt;
			Ls[i] = cnt;
		}
		{
			prePalin.resize(n + 1 + Small);
			int cur[Small];
			reu(k, 1, Small) {
				auto &v = queries[k];
				sort(v.begin(), v.end());
				rep(t, k) cur[t] = 0;
				int j = 0, qi = 0;
				rep(i, n + k + 1) {
					for (; qi != v.size() && v[qi].first == i; ++qi) {
						Ls[v[qi].second / 2] +=
							(v[qi].second % 2 ? -1 : 1) * cur[j];
					}
					cur[j] += prePalin[i];
					if (++j == k) j = 0;
				}
				assert(qi == v.size());
			}
		}

		vector<bool> sufPalin(n + 1);
		PalindromicTree revPT;
		revPT.init(n);
		sufPalin[n] = true;
		{
			int activeIndex = pt.getEvenRoot();
			rep(i, n) {
				revPT.alphas[i] = S[n - 1 - i];
				revPT.processAlphabet(activeIndex, i, 0);
				sufPalin[n - 1 - i] = revPT.nodes[activeIndex].length == i + 1;
			}
		}

		ll ans = 0;
		{
			int R = 0;
			for (int i = n - 2; i >= 2; --i) {
				int L = Ls[i];
				if (sufPalin[i + 1])
					++R;
				ans += (ll)L * R;
			}
		}

		printf("%lld\n", ans);
	}
	return 0;
}
0