HDU 4436 str2int

HDU 4436 str2int

HDU 4436 str2int

题意

给出$n$个串,问这些串中所有不同的子串可组成的数字之和模$2012$的结果是多少?

思路

后缀数组

定义前缀和$sigma[i] = s_0 + s_0s_1 + s_0s_1s_2 + … + (s_0s_1s_2s_3s_4…s_i)$

这一连续的整数值定义$rest[i] = s_0s_1s_2s_3s_4…s_i$

也就是说$sigma[i]$是$rest[i]$的前缀和

例如对于字符串 $s = “12345” $

$sigma[0] = 1, sigma[1] = 1 + 12, sigma[3] = 1 + 12 + 123…$

$rest[0] = 1, rest[1] = 12, rest[3] = 123…$

对于用未出现字符隔开的连起来的总串, 预处理出$sigma, rest$数组

用$tens[i]$ 表示$(∑10^j) \% 2012 (1 <= j <= i)$

就和容易找到连续的起点在$sa[i]$, 终点在$(sa[i] + height[i] , i)$所在字符串的整数值的和了

例如对于$“12345” $查询$3 + 34 + 345$:

$3 + 34 + 345 $

$= (123 + 1234 + 12345) - 12*(10 + 100 + 1000)$

$= (sigma[4] - sigma[1] + 2012 - rest[1]*tens[3]) % 2012$

题解代码

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
#include<bits/stdc++.h>
using namespace std;
const int mod = 2012;
#define maxn 1000010
int wa[maxn], wb[maxn], wv[maxn], Ws[maxn];
int cmp(int *r, int a, int b, int l)
{
return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int *r, int *sa, int n, int m)
{
int *x = wa, *y = wb, *t, i, j, p;
for(i = 0; i < m; i++) Ws[i] = 0;
for(i = 0; i < n; i++) Ws[x[i] = r[i]]++;
for(i = 1; i < m; i++) Ws[i] += Ws[i - 1];
for(i = n - 1; i >= 0; i--) sa[--Ws[x[i]]] = i;
for(j = 1, p = 1; p < n; j *= 2, m = p)
{
for(p = 0, i = n - j; i < n; i++) y[p++] = i;
for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] - j;
for(i = 0; i < n; i++) wv[i] = x[y[i]];
for(i = 0; i < m; i++) Ws[i] = 0;
for(i = 0; i < n; i++) Ws[wv[i]]++;
for(i = 1; i < m; i++) Ws[i] += Ws[i - 1];
for(i = n - 1; i >= 0; i--) sa[--Ws[wv[i]]] = y[i];
for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
}
return;
}

int rank[maxn], height[maxn];
void calheight(int *r, int *sa, int n)
{
int i, j, k = 0;
for(i = 1; i <= n; i++) rank[sa[i]] = i;
for(i = 0; i < n; height[rank[i++]] = k)
for(k ? k-- : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++);
return;
}

int n, N;
char in[maxn];
int s[maxn], sa[maxn];
int end[maxn];
int sigma[maxn];
int rest[maxn];
int tens[maxn];

int main()
{
while(scanf("%d", &n) != EOF)
{
N = 0;
for(int i = 0; i < n; i++)
{
scanf("%s", in);
int tmp = strlen(in);
int pos = N + tmp - 1;
for(int j = 0; j < tmp; j++)
{
end[N] = pos;
s[N++] = in[j] - '0' + 1;
}
end[N] = pos;
s[N++] = 11;
}
N--;
s[N] = 0;
da(s, sa, N + 1, 12);
calheight(s, sa, N);
memset(sigma, 0, sizeof(sigma));
memset(rest, 0, sizeof(rest));
memset(tens, 0, sizeof(tens));
rest[0] = (s[0] - 1) % mod;
sigma[0] = rest[0];
tens[0] = 0;
int ten = 1;
for(int i = 1; i <= N; i++)
{
rest[i] = (rest[i - 1] * 10 + s[i] - 1) % mod;
sigma[i] = (sigma[i - 1] + rest[i]) % mod;
ten = ten*10 % mod;
tens[i] = (tens[i - 1] + ten) % mod;
}
int ans = 0;
for(int i = 1; i <= N; i++)
{
if(s[sa[i]] == 1) continue;
int start = sa[i] + height[i];
int tail = end[sa[i]];
if(tail < start) continue;
if(start == 0)
ans = (ans + sigma[tail]) % mod;
else
ans = (ans + sigma[tail] - sigma[start - 1] + mod - rest[sa[i] - 1] * (tens[tail - sa[i] + 1] - tens[start - sa[i]] + mod) % mod + mod) % mod;
}
printf("%d\n", ans);
}
return 0;
}

思路

后缀自动机

将所有串中间中$10$隔开连接起来建立后缀自动机, 然后从根节点开始按照拓扑序向下遍历

计算出到达每一个结点的方案数(不能沿着$10$走,根节点还不能沿着$0$走)

然后对于状态 $s$ 经过边 $j$ 到达 $t$ 状态

$t$ 状态中从$s$转移来的字符串的贡献是 $s$ 状态中字符串的贡献*$10$ + $j$*$s$中不同满足条件的字符串数量,

最后拓扑序遍历即可

题解代码

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
#include<bits/stdc++.h>
using namespace std;
#define maxn 222000
#define maxm 111000

const int mod = 2012;

struct Suffix_Automation
{
struct State
{
State *par;
State *go[12];
int right, val, mi, sum, cnt;
void init(int _val)
{
par = 0, val = _val, right = mi = sum = cnt = 0;
memset(go, 0, sizeof(go));
}
};
State *root, *last, *cur;
State nodePool[maxn];
State* newState(int val = 0)
{
cur->init(val);
return cur++;
}
void initSAM()
{
cur = nodePool;
root = newState();
last = root;
}
void extend(int w, int len)
{
State *p = last;
State *np = newState(p->val + 1);
np->right = 1;
while(p && p->go[w] == 0)
{
p->go[w] = np;
p = p->par;
}
if(p == 0)
{
np->par = root;
}
else
{
State *q = p->go[w];
if(q->val == p->val + 1)
{
np->par = q;
}
else
{
State *nq = newState(p->val + 1);
memcpy(nq->go, q->go, sizeof(q->go));
nq->par = q->par;
q->par = nq;
np->par = nq;
while(p && p->go[w] == q)
{
p->go[w] = nq;
p = p->par;
}
}
}
last = np;
}
int d[maxm];
State *b[maxn];
void topo()
{
int cnt = cur - nodePool;
int maxVal = 0;
memset(d, 0, sizeof(d));
for(int i = 1; i < cnt; i++)
maxVal = max(maxVal, nodePool[i].val), d[nodePool[i].val]++;
for(int i = 1; i <= maxVal; i++) d[i] += d[i - 1];
for(int i = 1; i < cnt; i++) b[d[nodePool[i].val]--] = &nodePool[i];
b[0] = root;
}
};

Suffix_Automation sam;
char s[maxn];
int pre[maxn];

int main()
{
int n;
while(~scanf("%d", &n))
{
sam.initSAM();
while(n--)
{
scanf("%s", s);
int len = strlen(s);
for(int i = 0; i < len; i++)
sam.extend(s[i] - '0', i + 1);
sam.extend(10, -1);
}
sam.topo();
int ans = 0;
int cnt = sam.cur - sam.nodePool;
sam.b[0]->cnt = 1;
for(int i = 0; i < cnt; i++)
{
for(int j = 0; j < 10; j++)
{
if(!i && !j) continue;
if(!sam.b[i]->go[j]) continue;
sam.b[i]->go[j]->sum = (sam.b[i]->go[j]->sum + sam.b[i]->sum*10 + sam.b[i]->cnt*j) % mod;
sam.b[i]->go[j]->cnt = (sam.b[i]->go[j]->cnt + sam.b[i]->cnt) % mod;
}
ans = (ans + sam.b[i]->sum) % mod;
}
printf("%d\n", ans);
}
return 0;
}