题解 AT4163 【[ARC099D] Eating Symbols Hard】
皎月半洒花
2020-03-05 21:39:16
（如果题解页面公式锅了可以选择去blog内看
这题数据奇水，水到我觉得这 $83$ 组数据就是在闹着玩的。谷这题唯一有代码的那篇题解，只要把第二组样例 `reverse` 一下就可以 `hack` 掉；我双哈希把俩模数写混了都能对 $71/83$。
_____
> 给定一个下标范围在 $[-\infty,\infty]$ 的数组。一开始指针在 $0$ 处。给定一段操作序列。求有多少个子序列的操作结果等价于整个序列的操作结果。操作有四种，左移/右移/某个位置$+1$/某个位置$-1$ 。
>
> $1\leq n\leq 250,000$
一拿到题首先考虑 $dp$ ，发现 $dp$ 不是很可做…
于是就发现，类似这种题目可以使用哈希。四种操作分别对应 $\times base^{-1}$、$\times base$、$+base$、$-base$ 。
考虑这样做如何去求某一段的哈希值。普通的求法原理如下：
对于每个 $p$ ，截止到 $p$ 的哈希值，如果将 $x$ 看做 $base$ 的一个等价，那么就是是
$$
\sum_{i=1}^ps_ix^{p-i}
$$
考虑将上式记作 $o(p)$ 。则片段 $[l,r]$ 的哈希值可以如此得到：
考虑如果整个串的哈希值为 $q$，那么需要统计的是 $o(r)-o(l-1)\cdot x^{r-l+1}=q$ 。考虑从前至后用 $map$ 完成这个过程。由于不知道右端点的信息，需要对原式进行变形，即：
$$\frac{q-o(r)}{x^r}=\frac{o(l-1)}{x^{l-1}}$$
这样就可以做到 $l,r$ 无关了。随便选前缀或者后缀统计就好了。
但是注意到本题有个额外限制，最后只需要结果相同而不需要指针位置相同。所以需要在一开始哈希时稍微处理一下即可（这也是那篇挂了的题解的挂点）。
```cpp
#define mkp make_pair
#define pll pair<LL, LL>
const LL B1 = 237ll ;
const LL B2 = 637ll ;
const int N = 300010 ;
const LL P1 = 998244353 ;
const LL P2 = 1004535809 ;
int n ;
LL ans ;
char s[N] ;
LL I1, I2 ;
LL g[N][2] ;
LL S[N], T[N] ;
map <pll, LL> buc ;
LL expow(LL a, LL b, LL p){
LL ret = 1 ;
while (b){
if (b & 1)
(ret *= a) %= p ;
(a *= a) %= p ; b >>= 1 ;
}
return ret ;
}
int main(){
cin >> n >> (s + 1) ;
g[0][0] = g[0][1] = 1ll ;
I1 = expow(B1, P1 - 2, P1) ;
I2 = expow(B2, P2 - 2, P2) ;
for (int i = 1 ; i <= n ; ++ i){
if (s[i] == '-'){
g[i][0] = g[i - 1][0] ;
g[i][1] = g[i - 1][1] ;
S[i] = (S[i - 1] - g[i][0] + P1) % P1 ;
T[i] = (T[i - 1] - g[i][1] + P2) % P2 ;
}
if (s[i] == '+'){
g[i][0] = g[i - 1][0] ;
g[i][1] = g[i - 1][1] ;
S[i] = (S[i - 1] + g[i][0]) % P1 ;
T[i] = (T[i - 1] + g[i][1]) % P2 ;
}
if (s[i] == '<'){
g[i][0] = g[i - 1][0] * I1 % P1 ;
g[i][1] = g[i - 1][1] * I2 % P2 ;
S[i] = S[i - 1] ; T[i] = T[i - 1] ;
}
if (s[i] == '>'){
g[i][0] = g[i - 1][0] * B1 % P1 ;
g[i][1] = g[i - 1][1] * B2 % P2 ;
S[i] = S[i - 1] ; T[i] = T[i - 1] ;
}
++ buc[mkp(S[i], T[i])] ;
}
++ buc[mkp(0, 0)] ; LL x, y ;
for (int i = 0 ; i < n ; ++ i){
buc[mkp(S[i] , T[i])] -- ;
x = (S[i] + S[n] * g[i][0] % P1) % P1 ;
y = (T[i] + T[n] * g[i][1] % P2) % P2 ;
ans += buc[mkp(x, y)] ;
}
cout << ans << endl ; return 0 ;
}
```