1$の整数列$\{A_i\}$と整数$P$がある。初め、この数列の各要素と$P$は$0$である。記号$+,-,\gt,\lt$はそれぞれ「$A_P$を$1$大きくする」、「$A_P$を$1$小さくする」、「$P$を$1$大きくする」、「$P$を$1$小さくする」という意味を持つ。N)$の個数を求めよ。{'+'},{'-'},{'\gt'},{'\lt'}$考え方$S$の$i$文字目から$j$文字目を処理した後の整数列を$A[i,j]$とする。j$の時は$A[i,j]$の各要素は$0$であるとする。組$(i,j)$ごとに$A[i,j]$を求めるわけにはいかないから、累積和のようにしてこれを求められないかを考える。$A[1,j]-A[1,i-1]$としても、$S$を初めから$i$文字目まで処理した後の$P$の値($P_i$とする)が$0$でなければ等しくない。逆に考えると、$A[i,j]$と$A[1,j]-A[1,i-1]$の違いは各要素の位置が$P_{i-1}$だけずれているだけである。Hashを用いることにする。H(A)$とする)と変換する。H(A[1,i-1]))$$b^{-P_{i-1}}$である。H(A[i,j])$となる組$(i,j)$の数である。これを愚直に試すことはできないので工夫する。H(A[1,i-1])$となる。すべての$i$について、これを求めて足し合わせたものが答えとなる。$H$をそのまま持つわけにはいかないから、素数で割った余りをいくつか持っておくことにする。N$であるべきである。これは十分高速である。構築は文字列を先頭から見ていき、$+$を処理したら$b^P$、$-$を処理したら$-b^P$だけ足せば良い。その際、$P$の代わりに$b^P$も計算していく。Hashの値を$H_i$とする。H_{i-1}$の数を見る。この数の総和が答えである。