Problem:
 Score : 1200 points    Problem Statement In Takahashi's mind, there is always an integer sequence of length 2 \times 10^9 + 1 : A = (A_{-10^9}, A_{-10^9 + 1}, ..., A_{10^9 - 1}, A_{10^9}) and an integer P .  Initially, all the elements in the sequence A in Takahashi's mind are 0 , and the value of the integer P is 0 .  When Takahashi eats symbols + , - , > and < , the sequence A and the integer P will change as follows:   When he eats + , the value of A_P increases by 1 ;  When he eats - , the value of A_P decreases by 1 ;  When he eats > , the value of P increases by 1 ;  When he eats < , the value of P decreases by 1 .   Takahashi has a string S of length N . Each character in S is one of the symbols + , - , > and < .
He chose a pair of integers (i, j) such that 1 \leq i \leq j \leq N and ate the symbols that are the i -th, (i+1) -th, ... , j -th characters in S , in this order.
We heard that, after he finished eating, the sequence A became the same as if he had eaten all the symbols in S from first to last.
How many such possible pairs (i, j) are there?      Constraints  1 \leq N \leq 250000  |S| = N  Each character in S is + , - , > or < .         Input Input is given from Standard Input in the following format:  N  S       Output Print the answer.        Sample Input 1 5
+>+<-      Sample Output 1 3  If Takahashi eats all the symbols in S , A_1 = 1 and all other elements would be 0 .
The pairs (i, j) that leads to the same sequence A are as follows:   (1, 5)  (2, 3)  (2, 4)        Sample Input 2 5
+>+-<      Sample Output 2 5  Note that the value of P may be different from the value when Takahashi eats all the symbols in S .       Sample Input 3 48
-+><<><><><>>>+-<<>->>><<><<-+<>><+<<>+><-+->><<      Sample Output 3 475

Solution (Python):
import random
from collections import defaultdict


def solve(n, s, xs, m):
    ans = [10 ** 9] * (n + 1)
    for x in xs:
        p = 0
        h = 0
        y = 1
        r = pow(x, m - 2, m)
        pos = [0] * (n + 1)
        hashes = [0] * (n + 1)
        for i, c in enumerate(s, start=1):
            if c == '>':
                p += 1
                y = y * x % m
            elif c == '<':
                p -= 1
                y = y * r % m
            elif c == '+':
                h = (h + y) % m
            else:
                h = (h - y) % m
            pos[i] = p
            hashes[i] = h

        pow_x = [1]
        for _ in range(max(pos)):
            pow_x.append(pow_x[-1] * x % m)
        mp = min(pos)
        if mp < 0:
            pow_x.append(pow(r, -mp, m))
            for _ in range(-mp - 1):
                pow_x.append(pow_x[-1] * x % m)

        ideal = hashes[-1]
        required = defaultdict(lambda: 0)
        for i, (p, h) in enumerate(zip(pos, hashes)):
            ans[i] = min(ans[i], required[h])
            req = (ideal * pow_x[p] + h) % m
            required[req] += 1

    return sum(ans)


n = int(input())
s = input()

xs = random.sample(range(10 ** 9, 10 ** 10), 3)
m = 2305843009213693951
print(solve(n, s, xs, m))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from collections import defaultdict

N = int(readline())
S = np.frombuffer(read().rstrip(),'S1')

MOD = 10**9 + 7

Sright = (S==b'>')
Sleft = (S==b'<')
Sadd = (S==b'+')
Ssub = (S==b'-')

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def calc_hash_data(MOD,base):
    inv = pow(base,MOD-2,MOD)
    x = np.ones(N+1,dtype=np.int64)
    x[1:][Sright] = base
    x[1:][Sleft] = inv
    power = cumprod(x,MOD)
    x = np.pad(power[1:] * Sadd - power[1:] * Ssub,(1,0),mode='constant')
    np.cumsum(x,out=x); x %= MOD
    return power,x

b1 = 123450
b2 = 314159
pow1,H1 = calc_hash_data(MOD,b1)
pow2,H2 = calc_hash_data(MOD,b2)

X1 = (H1+H1[-1]*pow1)%MOD
X2 = (H2+H2[-1]*pow2)%MOD
X = (X1<<32)^X2

H = (H1<<32)^H2



X = X.tolist(); H = H.tolist()
counter = defaultdict(int)
for h in H:
    counter[h] += 1

answer = 0
for x,h in zip(X,H):
    counter[h] -= 1
    answer += counter[x]

print(answer)