# Sum of number substring str2int

UVA1673
This problem can be generalized suffix automata, but Mr. Chen Feng told us a clever way to make this problem can be done with ordinary suffix automata.
Main idea:
The NNN strings are given, which consist entirely of numbers. Calculate the result of converting all substrings of this NNN string to integers, then de duplication and sum first, and output the remainder of its modulus 2012. That is to find the sum of all essentially different strings of its substring.
Pretreatment:
First of all, we can splice NNN strings. The spliced parts can be separated by a special separator. For example, here I use: because ':' - 0 '= 10': '-' 0 '= 10': '- 0' = 10. We record the concatenated string as SSS, so the problem is converted into finding the sum of all substrings without separators in SSS. Establish suffix automata for SSS.
Definition:
Cnt[v]Cnt[v]Cnt[v] is the number of all leading zeros in samsamsamsamsam from the initial state to the state vvv without separators (according to the meaning of the question, the leading zeros are calculated after they are removed). For example, 01 and 1 count as the same substring).
Sum[v]Sum[v]Sum[v] sum [v] is the sum of all the legal paths from the initial state to the state vvv.
Transfer equation:
Cnt[v] = ∑ u ∈ FatherOf(v) Cnt[u] Cnt[v] = \ sum \ limits {u \ in FatherOf(v)} {Cnt[u]} Cnt[v] = u ∈ FatherOf(v) ∑ Cnt[u], that is, V is transferred from U. As for the legal transfer, as long as the substring does not go in the direction of the separator during the transfer, there will be no separator; as long as the initial state does not go to 0, there will be no leading 0.
Sum[v] = ∑ u ∈ FatherOf(v)Sum[u] * 10+Cnt[u] * Isum [v] = \ sum \ limits {u \ in FatherOf(v)} {Sum[u] * 10+Cnt[u] * i} Sum[v] = u ∈ FatherOf(v) ∑ Sum[u] * 10+Cnt[u] * i is the current status and the number of legal paths corresponding to the last status decimal plus the currently selected path *.
Transfer method:
How to ensure that the uuu in the equation is updated before vvv? It's not hard to find that since v v v comes from u u u, there are: len (U) < len (V) LEN (U) < len (V) LEN (U) < len (V), so we can arrange all States in order of lenlenlen, and update them from small to large. Lenlenlen in this question is continuous and a large number of repetitions, which can be solved by counting and sorting O(N)O(N)O(N), but fast sorting is enough.
AC Code:

```#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
const int MAXN = 120000;
int n;
string S;
struct SAM {
int size, last;
struct Node {
int len = 0, link = 0;
int next[11];
void clear() {
memset(next, 0, sizeof(next));
}
} node[MAXN * 2];
void init() {
for (int i = 0; i < size; i++) {
node[i].clear();
}
size = 1;
last = 0;
}
void insert(char x) {
int ch = x - '0';
int cur = size++;
node[cur].len = node[last].len + 1;
int p = last;
while (p != -1 && !node[p].next[ch]) {
node[p].next[ch] = cur;
}
if (p == -1) {
}
else {
int q = node[p].next[ch];
if (node[p].len + 1 == node[q].len) {
}
else {
int clone = size++;
node[clone] = node[q];
node[clone].len = node[p].len + 1;
while (p != -1 && node[p].next[ch] == q) {
node[p].next[ch] = clone;
}
}
}
last = cur;
}
}sam;
int N, Size = 0;
int
Cnt[2 * MAXN],
SUM[2 * MAXN],
Order[2 * MAXN];

bool Input() {
if (scanf("%d", &N) == EOF) {
return false;
}
S.clear();
while (N--) {
string Temp;
cin >> Temp;
S.insert(S.end(), Temp.begin(), Temp.end());
S.push_back(':');
}

sam.init();
for (int i = 0; i < S.size(); ++i) {
sam.insert(S[i]);
}

return true;
}
constexpr static int mod = 2012;
int DP() {
for (int i = 0; i < sam.size; ++i) {
Order[i] = i;
}
//sort
sort(Order, Order + sam.size, [](const int&Left,const int&Right)->bool {
return sam.node[Left].len < sam.node[Right].len;
}
);
//Empty string method
Cnt[0] = 1;
int&& Ans = 0;
for (int i = 0; i < sam.size; ++i) {
const int& u = Order[i];
//If j is the initial state, we can't go to 0, otherwise we can, so we can remove the leading 0
for (int j = (u ? 0 : 1); j < 10; ++j) {
const int& v = sam.node[u].next[j];
if (sam.node[v].len) {
Cnt[v] += Cnt[u];
Cnt[v] %= mod;
SUM[v] += SUM[u] * 10 + j * Cnt[u];
SUM[v] %= mod;
}
}
Ans += SUM[u];
Ans %= mod;
}
return Ans;
}
int main() {
while (Input()) {
memset(Cnt, 0x0, sizeof(Cnt));
memset(SUM, 0x0, sizeof(SUM));
printf("%d\n", DP());
}
return 0;
}```
45 original articles published, 49 praised, 20000 visitors+

Added by amma on Sun, 26 Jan 2020 11:10:04 +0200