結果
| 問題 | No.465 PPPPPPPPPPPPPPPPAPPPPPPPP |
| ユーザー |
 anta
|
| 提出日時 | 2016-12-15 22:59:46 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,549 ms / 2,000 ms |
| コード長 | 5,145 bytes |
| コンパイル時間 | 2,209 ms |
| コンパイル使用メモリ | 188,688 KB |
| 実行使用メモリ | 93,348 KB |
| 最終ジャッジ日時 | 2024-11-30 08:55:31 |
| 合計ジャッジ時間 | 18,423 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 20 |
ソースコード
#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 = 500;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;}