50pt

//50 pt
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
stack<char> sta;
int main()
{
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    assert(n<=8000);
    cin >> s;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        //清空栈
        while(!sta.empty())
            sta.pop();
        for(int j = i; j < n; j++)
        {
            if (!sta.empty() && sta.top() == s[j])
                sta.pop();
            else
                sta.push(s[j]);
            if(sta.empty())
                ans ++;
        }
    }
    cout << ans << "\n";
    return 0;
}

100pt

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int P1 = 131;
const int P2 = 233;
const int MOD1 = 998'244'353;
const int MOD2 = 1'000'000'007;
int n;
string s;
stack<char> sta;
stack<int> sta_hash1;
stack<int> sta_hash2;
map<pair<int,int>,int> num;//每个 hash 的出现次数
signed main()
{
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s;
    int ans = 0;
    num[make_pair(0,0)] = 1;
    for(int i = 0; i < n; i++)
    {
        // s[i] 带来的影响
        if (!sta.empty() && sta.top() == s[i])
        {
            //消除
            sta.pop();
            sta_hash1.pop();
            sta_hash2.pop();
        }
        else
        {
            //新增
            sta.push(s[i]);
            if(sta_hash1.empty())
            {
                sta_hash1.push(s[i]-'a'+1);
                sta_hash2.push(s[i]-'a'+1);
            }
            else
            {
                int temp;
                temp = sta_hash1.top();
                temp = (temp * P1 % MOD1 + (s[i] - 'a' + 1)) % MOD1;
                sta_hash1.push(temp);
                temp = sta_hash2.top();
                temp = (temp * P2 % MOD2 + (s[i] - 'a' + 1)) % MOD2;
                sta_hash2.push(temp);
            }
        }
        // 根据当前的 hash 出现次数统计答案
        int now_hash1, now_hash2;
        if(sta_hash1.empty())
        {
            now_hash1 = 0;
            now_hash2 = 0;
        }
        else
        {
            now_hash1 = sta_hash1.top();
            now_hash2 = sta_hash2.top();
        }
        ans += num[make_pair(now_hash1, now_hash2)];
        num[make_pair(now_hash1, now_hash2)] ++;
    }
    cout << ans << "\n";
    return 0;
}