AC自动机上的DP。
Table of Contents
- Description
- Solution
Description
JYY 来到了一个新的城市，为了和大家保持联系，第一件事就是办理新的手机号。JYY 对号码的要求很高，希望大家都能够顺畅地阅读手机号，因此 JYY 特别研究了地球人的电话号码阅读习惯，有如下重大发现 (请自行代入你们的手机号码)：地球人总是按照以下四种方式来朗读电话号码：
xxx-xxx-xxxxx 例如 151-958-83019
xxx-xxxx-xxxx 例如 151-9588-3019
xxxx-xxxx-xxx 例如 1519-5883-019
xxxx-xxx-xxxx 例如 1519-588-3019
即便是同一个电话号码，不同的人也会按照自己的习惯去解读，例如有些人会觉得电话号码是151-9588-3019，而有些却坚持 1519-588-3019。
为了让号码显得更上口，JYY 认为有些不吉利的数字串，在报电话号码时永远不应该被完整地读出来，例如，JYY 认为 7456 是不吉利的数字串 (气死我了)，那么 13000007456 就是一个不好的号码，因为有人会把这个号码读作 130-000-07456，而在最后一次完整地读出了 7456。然而，13000745600 却不是一个不好的号码，因为无论怎么读，7456 都会被拆分开来。
现在给出 JYY 认为不吉利的数字串，请你计算满足 JYY 要求的电话号码，总共有多少个。具体来说说，一个好的电话号码满足以下要求：
电话号码是以 1 开头的 11 位数字串。
这个号码无论按照之前描述的 4 种读法中的哪个，都不能在任意时刻连续读出不吉利的数字串。
Solution
一道Bouvardia在考场上总算想出完整思路的题。
AC自动机上DP，把每种长度和特殊情况压缩进节点的tag中。
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 105;
const int maxl = 505;
typedef long long ll;
int n;
ll ans, base;
char mode[105][20];
bool check(int sta, int l)
{
bool a, b, c, d, e;
a = ((sta & (1 << 3)) && (l != 4));
b = ((sta & (1 << 4)) && (l != 4 && l != 5 && l != 8));
c = ((sta & (1 << 5)) && (l == 10));
d = ((sta & (1 << 2)) || (sta & (1 << 1)));
e = ((sta & (1 << 6)) && (l == 2)) || ((sta & (1 << 7)) && (l == 3)) || ((sta & 1) && (l == 1));
return (a || b || c || d || e);
}
struct Aho
{
struct trie
{
int nxt[10];
int mtc;
trie(){memset(nxt, 0, sizeof nxt); mtc = 0;}
}node[maxl];
int tot, bfs[maxl], ptr;
int fail[maxl];
ll f[20][maxl][2];
void Insert(char *s)
{
int len = strlen(s), now = 0;
for(int i = 0; i < len; ++i)
{
int num = s[i] - '0';
if(!node[now].nxt[num]) node[now].nxt[num] = ++ptr;
now = node[now].nxt[num];
}
node[now].mtc |= (1 << len);
if(len < 5 && len > 1 && s[0] == '1')
{
now = 0;
for(int i = 1; i < len; ++i)
{
int num = s[i] - '0';
if(!node[now].nxt[num]) node[now].nxt[num] = ++ptr;
now = node[now].nxt[num];
}
if(len == 3) node[now].mtc |= (1 << 6);
else if(len == 4) node[now].mtc |= (1 << 7);
else if(len == 2) node[now].mtc |= 1;
}
return;
}
void build()
{
queue<int> q;
fail[0] = 0;
bfs[++tot] = 0;
for(int i = 0; i < 10; ++i)
if(node[0].nxt[i]) q.push(node[0].nxt[i]), fail[node[0].nxt[i]] = 0;
while(!q.empty())
{
int u = q.front(); q.pop(); bfs[++tot] = u;
for(int i = 0; i < 10; ++i)
{
int &to = node[u].nxt[i];
if(!to)
{
to = node[fail[u]].nxt[i];
continue;
}
q.push(to);
int v = fail[u];
fail[to] = node[v].nxt[i];
node[to].mtc |= node[fail[to]].mtc;
}
}
return;
}
void solve()
{
memset(f, 0, sizeof f);
f[0][0][0] = 1;
for(int i = 1; i <= 10; ++i)
for(int j = 1; j <= tot; ++j)
{
int u = bfs[j];
for(int x = 0; x < 10; ++x)
{
int y = node[u].nxt[x];
if(check(node[y].mtc, i))
{
f[i][y][1] += (f[i - 1][u][1] + f[i - 1][u][0]);
}
else
{
f[i][y][1] += f[i - 1][u][1];
f[i][y][0] += f[i - 1][u][0];
}
}
}
for(int i = 1; i <= tot; ++i)
ans += f[10][bfs[i]][1];
printf("%lld\n", base - ans);
}
}aho;
int main()
{
scanf("%d", &n);
base = 1ll;
for(int i = 1; i <= 10; ++i) base *= 10ll;
bool sol = true;
for(int i = 1; i <= n; ++i)
{
scanf("%s", mode[i]);
int ss = strlen(mode[i]);
if(ss == 1 && mode[i][0] == '1') sol = false;
}
if(!sol){puts("0"); return 0;}
for(int i = 1; i <= n; ++i)
aho.Insert(mode[i]);
aho.build();
aho.solve();
return 0;
}
|
