[??记录]AT4163 [ARC099D] Eating Symbols Hard
command_block
·
·
个人记录
题意 ： 你有一个初始为 0 的数组 A （范围无限）和一个初始在 0 的指针。
给出一个长度为 n 的操作串 S ，由 <，>，+，- 组成，其中每个字符意义如下。
< 将指针左移一位。> 将指针右移一位。+ 将指针对应位置 +1。- 将指针对应位置 -1。
求有多少个子串，使得执行完子串的操作后，数组和执行完整个串是一样的。（不要求指针位置相同）
------------
Hash 题。
考虑使用经典的字符串 Hash 描述该数组。
对于数组 $A$，其 Hash 值定义为 ：
$$H=\sum\limits_{i=-\infty}^{\infty}A_[i]x^i\bmod m$$
其中 $x,m$ 是我们任选的常数。
另外，记指针位置为 $p$。
考察各个操作对 Hash 值的影响。
- 在串后添加一个 `<` : $p'=p-1
- 在串后添加一个
> : p'=p+1
- 在串后添加一个
+ : H'=H+x^p
- 在串后添加一个
- : H'=H-x^p
于是，容易求出每个前缀的 Hash 值。记执行 S[1,i] 得到的数组的 Hash 值为 H[i]。
记执行 S[1,i] 得到的指针位置为 p[i]。
考虑如何求出某个区间 (l,r] 的 Hash 值 H_{(l,r]}。
$$H_{(l,r]}=\big(H[r]-H[l]\big)/x^{p[l]}$$
我们的目标是，求出有多少组 $l,r$ 满足 ：
$$
\begin{aligned}
H_{(l,r]}&=H_{(0,n]}\\
\big(H[r]-H[l]\big)/x^{p[l]}&=H_{(0,n]}\\
H[r]&=H_{(0,n]}*x^{p[l]}+H[l]
\end{aligned}
$$
枚举左端点，使用 `std::map` 统计符合要求的右端点个数即可。
复杂度 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<map>
#define ll long long
#define Pr pair<int,int>
#define mp make_pair
#define MaxN 250500
using namespace std;
ll inv(ll a,int m){
int t=m-2;ll ret=1;
while(t){
if (t&1)ret=ret*a%m;
a=a*a%m;t>>=1;
}return ret;
}
int p[MaxN];
struct Hash
{
int mod,b,_pw[MaxN<<1],*pw=_pw+MaxN,h[MaxN];
void Init(char *s,int n)
{
pw[0]=1;
int invb=inv(b,mod);
for (int i=1;i<=n;i++){
pw[i]=1ll*pw[i-1]*b%mod;
pw[-i]=1ll*pw[-i+1]*invb%mod;
}
for (int i=1;i<=n;i++)
if (s[i]=='+')h[i]=(h[i-1]+pw[p[i]])%mod;
else if (s[i]=='-')h[i]=(h[i-1]-pw[p[i]]+mod)%mod;
else h[i]=h[i-1];
}
}T1,T2;
int n;char s[MaxN];
map<Pr,int> o;
int main()
{
scanf("%d%s",&n,s+1);
for (int i=1;i<=n;i++)
if (s[i]=='>')p[i]=p[i-1]+1;
else if (s[i]=='<')p[i]=p[i-1]-1;
else p[i]=p[i-1];
T1.mod=1000000007;T1.b=250009;T1.Init(s,n);
T2.mod=1000000009;T2.b=250007;T2.Init(s,n);
o[mp(T1.h[n],T2.h[n])]++;
ll ans=0;
for (int i=1;i<=n;i++){
Pr now=mp(T1.h[i],T2.h[i]);
if (o.find(now)!=o.end())ans+=o[now];
o[mp((1ll*T1.h[n]*T1.pw[p[i]]+T1.h[i])%T1.mod,(1ll*T2.h[n]*T2.pw[p[i]]+T2.h[i])%T2.mod)]++;
}printf("%lld",ans);
return 0;
}
```