https://www.luogu.com.cn/problem/AT4163
题意：
给一个无限长度的数组 ( − ∞ , ∞ ) (-\infty,\infty) (−∞,∞)，初始全为0，有一个指针初始指向0。
给一个字符串表示操作。操作+-<>为指针所指+1，指针所指-1，指针往左，指针往右。
问多少子区间的操作得到的结果与最终数组一致。
解析：
解决负下标区间变为 [ 1 , n + 1 , 2 n + 1 ] ( 0 → n + 1 ) [1,n+1,2n+1](0\to n+1) [1,n+1,2n+1](0→n+1)，这段区间的值进行Hash。
然后每次 p o s [ i ] pos[i] pos[i]的数 + 1 +1 +1就是 H a s h [ i ] = H a s h [ i − 1 ] + p p o s [ i ] − 1 Hash[i]=Hash[i-1]+p^{pos[i]-1} Hash[i]=Hash[i−1]+ppos[i]−1
考虑得到 [ l , r ] [l,r] [l,r]区间的结果：
假设不考虑位移即 p o s [ l − 1 ] = n + 1 pos[l-1]=n+1 pos[l−1]=n+1，那么其实Hash值直接相减即可如果 p o s [ l − 1 ] > n + 1 pos[l-1]>n+1 pos[l−1]>n+1，说明相减后还要往左移动（除 P k P^k Pk） ( h a s h [ r ] − h a s h [ l − 1 ] ) / P p o s [ l − 1 ] − ( n + 1 ) = h a s h [ n ] (hash[r]-hash[l-1])/P^{pos[l-1]-(n+1)} = hash[n] (hash[r]−hash[l−1])/Ppos[l−1]−(n+1)=hash[n]如果 p o s [ l − 1 ] < n + 1 pos[l-1]<n+1 pos[l−1]<n+1，说明相减后还要往右移动（乘 P k P^k Pk） ( h a s h [ r ] − h a s h [ l − 1 ] ) ∗ P p o s [ l − 1 ] − ( n + 1 ) = h a s h [ n ] (hash[r]-hash[l-1])*P^{pos[l-1]-(n+1)} = hash[n] (hash[r]−hash[l−1])∗Ppos[l−1]−(n+1)=hash[n]我们枚举 l l l，用map求出符合条件的 r r r的数量即可。代码：
/* * Author : Jk_Chen * Date : 2020-10-07-13.08.13 */ #include<bits/stdc++.h> using namespace std; #define LL long long #define LD long double #define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);i++) #define per(i,a,b) for(int i=(int)(a);i>=(int)(b);i--) #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back #define pill pair<int, int> #define fi first #define se second void test(){cerr<<"\n";} template<typename T,typename... Args>void test(T x,Args... args){cerr<<"> "<<x<<" ";test(args...);} const LL mod=1e9+7; const int maxn=5e5+9; const int inf=0x3f3f3f3f; LL rd(){ LL ans=0; char last=' ',ch=getchar(); while(!(ch>='0' && ch<='9'))last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; return ans; } #define rd rd() /*_________________________________________________________begin*/ int Mul(int a,int b){return 1ll*a*b%mod; } int Add(int a,int b){return (1ll*a+b)%mod; } LL Pow(LL a,LL b,LL mod=mod){ if(a>=mod)a%=mod; LL res=1; while(b>0){ if(b&1)res=res*a%mod; a=a*a%mod; b>>=1; } return res; } /*_________________________________________________________Pow*/ int inv(int a){return Pow(a,mod-2); } int n; char x[maxn]; int P[2]={int(1e6+81),int(1e6+83)}; int PowP[2][maxn]; int pos[maxn]; int Hash[2][maxn]; inline pill GH(int i){return {Hash[0][i],Hash[1][i]}; } int main(){ /// Hash位置 1 - n+1 - 2n+1，初始每个位置为0 int n=rd; rep(id,0,1){ PowP[id][0]=1; rep(i,1,maxn-1) PowP[id][i]=Mul(PowP[id][i-1],P[id]); } scanf("%s",x+1); pos[0]=n+1; rep(i,1,n){ if(x[i]=='+'){ pos[i]=pos[i-1]; rep(id,0,1) Hash[id][i]=Add(Hash[id][i-1],PowP[id][pos[i]-1]); } else if(x[i]=='-'){ pos[i]=pos[i-1]; rep(id,0,1) Hash[id][i]=Add(Hash[id][i-1],mod-PowP[id][pos[i]-1]); } else if(x[i]=='<'){ pos[i]=pos[i-1]-1; rep(id,0,1) Hash[id][i]=Hash[id][i-1]; } else if(x[i]=='>'){ pos[i]=pos[i-1]+1; rep(id,0,1) Hash[id][i]=Hash[id][i-1]; } //test(i,Hash[i]); } LL ans=0; map<pill,int>cnt; per(l,n,1){ cnt[GH(l)]=cnt[GH(l)]+1; pill find; if(pos[l-1]==n+1){ find.fi=Add(Hash[0][n],Hash[0][l-1]); find.se=Add(Hash[1][n],Hash[1][l-1]); } else if(pos[l-1]<=n+1){ find.fi=Add(Mul(Hash[0][n],inv(PowP[0][n+1-pos[l-1]])),Hash[0][l-1]); find.se=Add(Mul(Hash[1][n],inv(PowP[1][n+1-pos[l-1]])),Hash[1][l-1]); } else{ find.fi=Add(Mul(Hash[0][n],PowP[0][pos[l-1]-n-1]),Hash[0][l-1]); find.se=Add(Mul(Hash[1][n],PowP[1][pos[l-1]-n-1]),Hash[1][l-1]); } ans+=cnt[find]; } printf("%lld\n",ans); }