Description：

给一个小写字母组成的字符串，询问这个字符串有多少子序列可以生成一个合法括号序列，要求配对的括号是同一个字母。

$1\leqslant |s|\leqslant10^6$

Solution：

首先有这样一个性质，就是如果你在扫描一个字符串的同时维护一个栈，如果当前字符和栈顶相同，就弹栈，否则压栈，这样如果最后栈空了，那么这个字符就是合法的，想想好像没什么问题，所以可以里用前缀和的思想，从字符串的开始扫，同时维护一个栈，扫到某一个位置就把这个栈 $hash$ 起来，每次统计一下这个 $hash$ 值有多少就是答案，因为如果两个前缀的栈的 $hash$ 值是一样的，那么他们相减的部分就是一个合法序列。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

#define MAXN 1000010

char c[MAXN];

typedef long long ll;

map<pair<ll,ll>,int> cnt;

#define MOD1 1000000007

#define MOD2 998244353

#define BASE1 19260817

#define BASE2 23333

ll h1[MAXN],h2[MAXN];

int s[MAXN],top = 0;

int main()

{

	freopen("C.in","r",stdin);

	freopen("C.out","w",stdout);

	scanf("%s",c + 1);

	int n = strlen(c + 1);

	ll ans = 0;

	++cnt[make_pair(0,0)];

	for(int i = 1;i <= n;++i)

	{

		if(top != 0 && c[i] == s[top])--top;

		else s[++top] = c[i];

		h1[top] = (h1[top - 1] * BASE1 + s[top]) % MOD1;

		h2[top] = (h2[top - 1] * BASE2 + s[top]) % MOD2;

		ans += cnt[make_pair(h1[top],h2[top])];

		++cnt[make_pair(h1[top],h2[top])];

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}