#595113 (C++17) No.464 PPAP

提出ソース
結果

問題	No.464 PPAP
ユーザー	mine691
提出日時	2020-12-18 22:23:33
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	6,100 bytes
コンパイル時間	2,426 ms
コンパイル使用メモリ	221,792 KB
最終ジャッジ日時	2025-01-17 03:08:42
ジャッジサーバーID （参考情報）	judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2 WA * 2
other	AC * 10 WA * 12
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x), end(x)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define debug(v)          \
	cout << #v << ":";    \
	for (auto x : v)      \
	{                     \
		cout << x << ' '; \
	}                     \
	cout << endl;
#define mod 998244353
using ll = long long;
const int INF = 1000000000;
const ll LINF = 1001002003004005006ll;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
template <class T>
bool chmax(T &a, const T &b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
template <class T>
bool chmin(T &a, const T &b)
{
	if (b < a)
	{
		a = b;
		return true;
	}
	return false;
}

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

struct IOSetup
{
	IOSetup()
	{
		cin.tie(0);
		ios::sync_with_stdio(0);
		cout << fixed << setprecision(12);
	}
} iosetup;

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
	for (int i = 0; i < (int)v.size(); i++)
		os << v[i] << (i + 1 == (int)v.size() ? "" : " ");
	return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
	for (T &x : v)
		is >> x;
	return is;
}

struct PalindromicTree
{
	struct node
	{
		map<char, int> link; // link aba -> xabax
		int len, cnt, idx;	 // s[idx, idx+len)に1つこの回文がある
		int suffix_link;
		node() {}
		node(int len, int cnt, int idx, int suffix_link) : len(len), cnt(cnt), idx(idx), suffix_link(suffix_link) {}
	};

	vector<node> v; // 0:(-1), 1: (0)
	int n, ptr;

	PalindromicTree() {}
	PalindromicTree(const string &s) : v(2), n(2), ptr(1)
	{
		v[0] = node(-1, 0, -1, 0);
		v[1] = node(0, 0, -1, 0);
		for (int i = 0; i < (int)s.size(); i++)
			process(s, i);
		build_freq();
	}

	bool process(const string &s, int pos)
	{
		int cur = ptr; // link parent
		while (true)
		{
			int rev = pos - v[cur].len - 1;
			if (rev >= 0 and s[rev] == s[pos])
				break;
			cur = v[cur].suffix_link;
		}
		if (v[cur].link.count(s[pos]))
		{
			ptr = v[cur].link[s[pos]];
			v[ptr].cnt++;
			return false;
		}
		ptr = n++;

		v.emplace_back(v[cur].len + 2, 1, pos - v[cur].len - 1, -1);
		v[cur].link[s[pos]] = ptr; // link
		if (v[ptr].len == 1)
		{
			v[ptr].suffix_link = 1;
			return true;
		}

		while (true)
		{
			cur = v[cur].suffix_link;
			int rev = pos - v[cur].len - 1;
			if (rev >= 0 and s[rev] == s[pos])
			{
				v[ptr].suffix_link = v[cur].link[s[pos]];
				break;
			}
		}
		return true;
	}
	// DAGをトポソ
	vector<int> calc_ord()
	{
		vector<int> ret;
		ret.emplace_back(0);
		ret.emplace_back(1);
		for (int i = 0; i < (int)ret.size(); i++)
			for (auto &p : v[ret[i]].link)
				ret.emplace_back(p.second);
		return ret;
	}
	void build_freq()
	{
		auto ord = calc_ord();
		// 一番長い回文にしかcnt+=1をしていないので，linkで集約する
		for (int i = (int)ord.size() - 1; i >= 0; i--)
			v[v[ord[i]].suffix_link].cnt += v[ord[i]].cnt;
	}
	// nodeのindexに対し，stringを構築．重い
	string id_to_string(int idx)
	{
		if (idx < 2)
			return "";
		string ret = "";
		function<bool(int)> dfs = [&](int cur) {
			if (cur == idx)
				return true;
			for (auto to : v[cur].link)
			{
				if (dfs(to.second))
				{
					ret.push_back(to.first);
					return true;
				}
			}
			return false;
		};
		bool odd_len = dfs(0);
		if (!odd_len)
			dfs(1);
		string rev = ret;
		if (odd_len)
			rev.pop_back();
		reverse(begin(rev), end(rev));
		return ret + rev;
	}
	int count_unique() { return n - 2; }
	int size() { return n; }
	node operator[](const int &k) { return v[k]; }
};

using ull = unsigned long long;
struct RollingHash
{
	using ull = unsigned long long;
	using uint128 = __uint128_t;
	static const ull MOD = (1ull << 61ull) - 1;
	vector<ull> hashed, power;
	const ull base;

	static inline ull add(ull a, ull b)
	{
		if ((a += b) >= MOD)
			a -= MOD;
		return a;
	}
	static inline ull mul(ull a, ull b)
	{
		uint128 c = (uint128)a * b;
		return add(c >> 61, c & MOD);
	}
	static inline ull generate_base()
	{
		mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
		uniform_int_distribution<ull> rand(1, RollingHash::MOD - 1);
		return rand(mt);
	}
	RollingHash() = default;
	RollingHash(const string &s, ull base) : base(base)
	{
		int sz = (int)s.size();
		hashed.assign(sz + 1, 0);
		power.assign(sz + 1, 0);
		power[0] = 1;
		for (int i = 0; i < sz; i++)
		{
			power[i + 1] = mul(power[i], base);
			hashed[i + 1] = add(mul(hashed[i], base), s[i]);
		}
	}
	template <typename T>
	RollingHash(const vector<T> &s, ull base) : base(base)
	{
		int sz = (int)s.size();
		hashed.assign(sz + 1, 0);
		power.assign(sz + 1, 0);
		power[0] = 1;
		for (int i = 0; i < sz; i++)
		{
			power[i + 1] = mul(power[i], base);
			hashed[i + 1] = add(mul(hashed[i], base), s[i]);
		}
	}
	// hash[l,r)
	ull get(int l, int r) const
	{
		return add(hashed[r], MOD - mul(hashed[l], power[r - l]));
	}
	ull concat(ull hash1, ull hash2, int hash2len) const
	{
		return add(mul(hash1, power[hash2len]), hash2);
	}
	int lcp(const RollingHash &b, int l1, int r1, int l2, int r2) const
	{
		assert(b.base == base);
		int len = min(r1 - l1, r2 - l2);
		int lw = 0, hi = len + 1;
		while (hi - lw > 1)
		{
			int mid = (lw + hi) / 2;
			if (get(l1, l1 + mid) == b.get(l2, l2 + mid))
				lw = mid;
			else
				hi = mid;
		}
		return lw;
	}
};

signed main()
{
	string s;
	cin >> s;
	int n = (int)s.size();
	if (s[0] != 'a')
		return 0;
	PalindromicTree pt(s); // yossha

	auto base = RollingHash::generate_base();
	RollingHash rh(s, base);

	vector<ll> l(n + 1, 0), r(n + 1, 0);

	for (int i = 2; i < pt.n; i++)
	{
		int li = pt[i].len;
		ull p1 = rh.get(pt[i].idx, pt[i].idx + li);

		if (rh.get(n - li, n) == p1)
			r[n - li]++;
		if (p1 != rh.get(0, li))
			continue;

		for (int j = 2; j < pt.n; j++)
		{
			int lj = pt[j].len;
			if (li + lj > n)
				continue;
			ull p2 = rh.get(pt[j].idx, pt[j].idx + lj);
			if (rh.get(li, li + lj) == p2)
				l[li + lj]++;
		}
	}
	ull res = 0, sum = 0;
	for (int i = n; i >= 0; i--)
	{
		res += sum * l[i];
		sum += r[i];
	}
	cout << res << "\n";
	return 0;
}
yukicoder

結果

ソースコード
