考虑怎样的一个串“可消除”：

1.设 $\text{x}$ 是任意字符，则串 $\text{xx}$ 可消除；

以上一种称为“第一类可消除串”；

2.设 $\text{A,B}$ 均为可消除串，则串 $\text{AB}$ 可消除；

3.设 $\text{x}$ 是任意字符，$\text{A}$ 是可消除串，则串 $\text{xAx}$ 可消除。

以上两种称为“第二类可消除串”。不难发现，任意可消除串一定是这三种的组合。

对于第一类可消除串，有一个显然的计数方法：直接开一个栈，从头到尾依次检查每个字符，若栈顶与当前字符相同，则弹出栈顶，并计数加一；否则将当前字符入栈。

显然，该计数方法会漏掉所有的第二类可消除串，因为它无法识别当前产生的第一类可消除串是否能和前方的可消除串产生拼接。

我们从栈中元素入手：不难发现栈里面的元素一定是匹配到当前位置还剩下的部分，考虑如果发生了可拼接的情况，栈中元素的状态是：和它所拼接的前一个可消除串产生时栈中元素的状态完全一致！

为什么？直接手动模拟以下过程：假设当前已经造出一个可消除串并进行了出栈，后面又来了若干个字符，它们又构成了一个可消除串——我们此时只考虑这种方法能够观测到的第一类可消除串，对于第一种情况，显然进栈的一定是第一个字符，之后第二个字符将它弹出去。对此情况进行类推，不难发现，识别出的任意可消除串在其形成时都不会存在于栈中（显然第二类可消除串可以全部由第一类可消除串拼接而成），也就是说，一个可消除串形成的时候，栈会回到接受它的第一个字符之前的状态。

显然，我们只需要记录每个状态出现了多少次即可——对于第二类可消除串，它一定是接在一个可消除串后面的，这个状态出现已经出现多少次就说明它前面有多少个连续的可消除串，显然这个数加一就是当前产生的可消除串的贡献：它自己有 $1$ 的贡献，之后就是依次接上前一个连续的可消除串带来的贡献，后者显然。

对于栈状态的记录，直接将栈当成序列，多项式哈希即可。

使用std::map实现，时间复杂度 $\Theta(n\log n)$。

亲测本OJ这题要双哈希，自然溢出会75.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned ll;
const ull xp=37;
const int N=2e6+5;
const ull m1=1e17+3,m2=1e9+9;
pair<ull,ull> nshs;stack<int> stk;
stack<pair<ull,ull> > hsstk;
map<pair<ull,ull>,ll> hss;
int n;char c;ll ans;
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
	cin>>n;
	++hss[make_pair(0,0)];
	for(int i=1;i<=n;++i)
	{
		cin>>c;c-=('a'),++c;
		if(!stk.size())
		{
			hsstk.push(make_pair(c%m1,c%m2));
			stk.push(c);nshs.first=c%m1,nshs.second=c%m2;
		}
		else if(stk.top()==c)
		{
			stk.pop(),hsstk.pop();
			if(!hsstk.size()) nshs=make_pair(0,0);
			else nshs=hsstk.top();
		}
		else
		{
			nshs.first=(hsstk.top().first*xp+c)%m1;
			nshs.second=(hsstk.top().second*xp+c)%m2;
			stk.push(c),hsstk.push(nshs);
		}
		ans+=hss[nshs];
		++hss[nshs];
	}
	cout<<ans;
	return 0;
}
/*
10
abbccddeea
*/