数字子串的和 str2int
程序员文章站
2022-04-30 18:21:47
...
UVA1673
这道题可以用广义后缀自动机,不过陈锋老师给我们讲了一个巧妙地方法,使得这道题可以用普通的后缀自动机做。
题目大意:
给出个完全由数字组成的字符串。计算将这个的字符串的所有子串转换为整数后先去重再求和的结果,输出其模2012的余数。也就是求其子串的所有本质不同的字符串的和。
预处理:
首先,我们可以将个字符串拼接起来,拼接的部位可以用一个特殊的分隔符隔开。比如这里我用 :,因为。我们将拼接好的字符串记作,这样问题就转换成求中所有不含分隔符的本质不同的子串的和。对建立后缀自动机。
定义:
为从的初始状态到状态中的所有不含分隔符以及前导0的数量(根据题意,前导0去掉后算一个。比如01和1算作同一个子串)。
为从初始状态到状态的所有合法路径形成的数字之和。
转移方程:
即v由u转移而来。而关于合法转移,只要在转移时不向分隔符的方向走子串就不会出现分隔符;只要不再初始状态往0走,就不会出现前导0。
即当前的状态和为上一状态十进制进一位加上当前选择的路径*对应的合法路径数量。
转移方式:
怎样保证方程中的在之前就更新过了呢?不难发现,由于都是由向下走一步得来,因此有:因此我们将所有状态按排个序,从小到大更新即可。本题中的是连续且大量重复的,可以采用计数排序解决,不过快排也够了。
AC代码:
#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() {
len = link = 0;
memset(next, 0, sizeof(next));
}
} node[MAXN * 2];
void init() {
for (int i = 0; i < size; i++) {
node[i].clear();
}
node[0].link = -1;
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;
p = node[p].link;
}
if (p == -1) {
node[cur].link = 0;
}
else {
int q = node[p].next[ch];
if (node[p].len + 1 == node[q].len) {
node[cur].link = q;
}
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;
p = node[p].link;
}
node[q].link = node[cur].link = 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(Order, Order + sam.size, [](const int&Left,const int&Right)->bool {
return sam.node[Left].len < sam.node[Right].len;
}
);
//空串合法
Cnt[0] = 1;
int&& Ans = 0;
for (int i = 0; i < sam.size; ++i) {
const int& u = Order[i];
//如果j是初始状态,就不能往0走,否则就可以,这样就可以去除前导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;
}