Wuyanru's blog
0%

[ARC099F] Eating Symbols Hard

发表于 分类于 ，

打开一看题面，噫，像是神仙 dp，我不会做！

哎，哈希

题目链接

题意

现在有一个数组 ，初始全 ，范围可看作 ，此为还有一个指针 。

一个操作串仅包含 <>+- 四种字符，是这样操作的：

  • < 表示令指针左移一位。
  • > 表示令指针右移一位。
  • + 表示令指针所指位置自增 。
  • - 表示令指针所指位置自减 。

给定一个操作串，求这个操作串有多少个子串，操作结束后与整个串结果相同（指针位置不管）。

题解

首先整个串最终的结果是易于模拟的。

如果我们想要知道两个串最终结果相不相等，从操作序列上下手是困难的，就只能从最终结果上下手，考虑哈希。

首先可以发现，指针左移右移可以看成整个序列右移左移，方便我们计算哈希值。

那么就会有：

  • < 表示令 。
  • > 表示令 。
  • + 表示令 。
  • - 表示令 。

设 < 比 > 多出现了 次，那么最终数组哈希值就是 。

考虑设 表示前 个字符的 值，。

考虑如果一个区间 与整个区间 等价，我们可以列出一个怎样的式子。

大体的思路是，先执行 ，再执行 ，与执行 等价。

那么就可以列出式子：。

整理一下就是 。

直接哈希即可。

复杂度为 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int mod1=998244853;
const int mod2=1004535809;
const int base1=1145141;
const int base2=1919810;
char s[250005];
int n;
inline ll qow(ll a,ll b,int mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
struct node
{
    ll a,b;
    node(ll a=0,ll b=0):a(a),b(b){}
    node operator + (node c)
    {
        return node((a+c.a)%mod1,(b+c.b)%mod2);
    }
    node operator - (node c)
    {
        return node((a-c.a+mod1)%mod1,(b-c.b+mod2)%mod2);
    }
    node operator * (node c)
    {
        return node(a*c.a%mod1,b*c.b%mod2);
    }
    node operator ^ (int c)
    {
        return node(qow(a,c,mod1),qow(b,c,mod2));
    }
    node operator = (node c)
    {
        a=c.a,b=c.b;
        return *this;
    }
    bool operator < (node c)const
    {
        if(a!=c.a) return a<c.a;
        return b<c.b;
    }
}pre[250001],B,RB;
map<node,int>vis;
node num[250001];
int p[250001];
inline void ins(int id)
{
    node ans=num[n];
    if(p[id]>0) ans=ans*(RB^p[id]);
    else ans=ans*(B^(-p[id]));
    vis[ans+num[id]]++;
}
int main()
{
    n=read();scanf("%s",s+1);
    B=node(base1,base2);
    RB=node(qow(base1,mod1-2,mod1),qow(base2,mod2-2,mod2));
    for(int i=1;i<=n;i++)
    {
        p[i]=p[i-1];
        if(s[i]=='+') pre[i]=pre[i-1]+node(1,1);
        else if(s[i]=='-') pre[i]=pre[i-1]-node(1,1);
        else if(s[i]=='<') pre[i]=pre[i-1]*B,p[i]++;
        else pre[i]=pre[i-1]*RB,p[i]--;
        if(p[i]>0) num[i]=pre[i]*(RB^p[i]);
        else num[i]=pre[i]*(B^(-p[i]));
    }
    ins(0);ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=vis[num[i]];
        ins(i);
    }
    printf("%lld\n",ans);
    return 0;
}

感谢观看！