CSL的密码2(后缀自动机+DP)

描述

传送门:ACM集训队暑期集训热身赛 - Problem I

众所周知,CSL最喜欢的密码是******。

为了改变这一点,他随机生成了一个只包含$0$和$1$的字符串,并打算把他的密码改成这个字符串的一个子串
他的密码需要满足以下条件:

  • 密码的二进制表示必须是$3$的倍数,且不能为$0$。
  • 密码中不能含有前导零。

由于他生成的字符串太长了,他希望你帮他数一下他有多少种不同的选择。
两种方案不同当且仅当最后的密码不同。

输入

第一行有一个整数$T$,表示测试数据的组数。
对于每组测试数据,有一个字符串$S$(只包含$0$和$1$)。
$T≤100$
$1≤|S|≤10^6$
$\sum |S|≤2⋅10^6$

输出

对于每组测试数据,在一行内输出答案。

样例

Input Output
1
2
3
4
5
4
101010
000111
111000
000000
1
2
3
4
2
1
4
0

提示

对于第一个样例,两种方案分别为:$10101$,$101010$。

思路

  • 类似需要统计本质不同的子串,想到使用后缀数据结构来维护。
  • 对原串建后缀自动机后,在 DWAG 上 DP。
  • 令 $dp[i][j]$ 表示在自动机 $i$ 结点模数为 $j$ 的方案数。
  • 由于在后缀自动机上,从根结点出发的每一条路径,就代表一个本质不同的子串,于是我们只需要按拓扑序进行递推即可。
  • 转移的时候不要让根结点走$0$的转移。
  • 最后答案就是$\sum dp[i][0] - 1$(去掉空串的情况)。
  • 这题没人验过啊……
  • 来自某次牛客上比赛看错了题。
  • 在群里和大佬讨论过,似乎也是一眼SAM的。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1 << 20;
struct SAM
{
int len[maxn << 1], link[maxn << 1], ch[maxn << 1][2];
int sz, rt, last;
int newnode(int x = 0)
{
len[sz] = x;
link[sz] = -1;
memset(ch[sz], -1, sizeof(ch[sz]));
return sz++;
}
void init() { sz = last = 0, rt = newnode(); }
void extend(int c)
{
int np = newnode(len[last] + 1);
int p;
for (p = last; ~p && ch[p][c] == -1; p = link[p]) ch[p][c] = np;
if (p == -1)
link[np] = rt;
else
{
int q = ch[p][c];
if (len[p] + 1 == len[q])
link[np] = q;
else
{
int nq = newnode(len[p] + 1);
memcpy(ch[nq], ch[q], sizeof(ch[q]));
link[nq] = link[q], link[q] = link[np] = nq;
for (; ~p && ch[p][c] == q; p = link[p]) ch[p][c] = nq;
}
}
last = np;
}
int topcnt[maxn], topsam[maxn << 1];
ll dp[maxn << 1][3];
void solve()
{
memset(topcnt, 0, sizeof(topcnt)), memset(dp, 0, sizeof(dp));
for (int i = 0; i < sz; i++) topcnt[len[i]]++;
for (int i = 0; i < maxn - 1; i++) topcnt[i + 1] += topcnt[i];
for (int i = 0; i < sz; i++) topsam[--topcnt[len[i]]] = i;
dp[rt][0] = 1;
ll ret = 0;
for (int i = 0; i < sz; i++)
{
int u = topsam[i];
for (int c = 0; c < 2; c++)
{
if (u == 0 && c == 0) continue;
if (~ch[u][c])
{
int v = ch[u][c];
for (int j = 0; j < 3; j++) dp[v][(j << 1 | c) % 3] += dp[u][j];
}
}
ret += dp[u][0];
}
printf("%lld\n", ret - 1);
}
} gao;

char s[maxn];

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
gao.init();
scanf("%s", s);
for (int i = 0; s[i]; i++) gao.extend(s[i] - '0');
gao.solve();
}
return 0;
}
捐助作者
0%