str2int(后缀自动机)

描述

传送门:HDU4436

In this problem, you are given several strings that contain only digits from 0 to 9, inclusive.
An example is shown below.

101123

The set $S$ of strings is consists of the $N$ strings given in the input file, and all the possible substrings of each one of them.
It’s boring to manipulate strings, so you decide to convert strings in $S$ into integers.
You can convert a string that contains only digits into a decimal integer, for example, you can convert "101" into $101$, "01" into $1$, et al.
If an integer occurs multiple times, you only keep one of them.
For example, in the example shown above, all the integers are $1$, $10$, $101$, $2$, $3$, $12$, $23$, $123$.
Your task is to calculate the remainder of the sum of all the integers you get divided by $2012$.

Input

There are no more than $20$ test cases.
The test case starts by a line contains an positive integer $N$.
Next $N$ lines each contains a string consists of one or more digits.
It’s guaranteed that $1≤N≤10000$ and the sum of the length of all the strings $≤100000$.
The input is terminated by EOF.

Output

An integer between $0$ and $2011$, inclusive, for each test case.

Sample Input

1
2
3
4
5
6
5
101
123
09
000
1234567890

Sample Output

1
202

思路

  • 建立多串的后缀自动机,然后拓扑排序后DP。
  • 设$dp[u]$表示走到结点$u$的方案数,$sum[u]$表示到达结点$u$的这些整数之和。这样有
    $$
    \begin{align}
    dp[v] &= \sum_{\substack{u:\\(u,v,c)\in DAWG}}dp[u] \\
    sum[v] &= \sum_{\substack{u:\\(u,v,c)\in DAWG}}(10\times sum[u] + dp[u] \times c)
    \end{align}
    $$
  • 然后注意处理一下前导零就好了。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 2012;
const double eps = 1e-6;

const int maxn = 100005;
struct SAM
{
int len[maxn << 1], link[maxn << 1], ch[maxn << 1][12];
int sz, rt, last;
int newnode(int x = 0)
{
len[sz] = x;
link[sz] = -1;
clr(ch[sz], -1);
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];
int topsam[maxn << 1];
int dp[maxn << 1], sum[maxn << 1];
int solve()
{
int ret = 0;
clr(topcnt, 0), clr(dp, 0), clr(sum, 0);
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] = 1;
for (int i = 0; i < sz; i++)
{
int u = topsam[i];
for (int c = 0; c < 10; c++)
{
if (u == 0 && c == 0) continue;
if (~ch[u][c])
{
int v = ch[u][c];
(dp[v] += dp[u]) %= mod;
(sum[v] += sum[u] * 10 + dp[u] * c) %= mod;
}
}
(ret += sum[u]) %= mod;
}
return ret;
}
};

SAM sam;
char buf[maxn];

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n;
while (~scanf("%d", &n))
{
sam.init();
while (n--)
{
scanf("%s", buf);
int m = strlen(buf);
for (int i = 0; i < m; i++) sam.extend(buf[i] - '0');
sam.last = 0;
}
printf("%d\n", sam.solve());
}
return 0;
}
捐助作者
0%