【题意】
给定N个数字串，每个串的子串成一个数字，问这些数字放进一个set里面去重后和模2012是多少
【算法】
后缀数组也可以做，但是后缀自动机无疑简单一点。
类似于后缀数组，把所有串通过10这个不属于任意一个数字的元素串连在一起。
然后把结点按val直接sort一下，从前往后递推统计。
递推的时候记录两个值，到达这个结点的方案数way以及到达这个状态的数字之和sum。
每次接收一个c转移显然就应该是给下一个结点的sum加上$$\sum_{i = 1}^{way} (number_i * 10 + c)$$。
把这个式子的常数c拉出来就是$$way * c + 10 * \sum_{i = 1}^{way} number_i$$
亦即$$way * c + 10 * sum$$
就这样从前往后推一下就好了，最后把每个结点的sum值都加起来就是答案。
推的时候要注意的就只有两点
- 根节点不应该接收0开头的串，因为这会弄出有前导0的串从而导致重复，这个很显然吧。
- 所有的转移都无视10这个分支，因为那本身就是不应该走的…这个也很显然把。
【时间复杂度】
$$O(N * 11 + N \log N)$$
其中N为输入字符总数。后面的N lg N是因为我贪方便直接按val sort了，这一步用了链表跳一下很容易做到O(n)的。 11自然就是字符集大小了。
【空间复杂度】
$$O(N * 11)$$
【吐槽】
今天贴了后缀自动机的模板以后花了不到5分钟就过掉了…现场调了1小时没过是怎么回事，当时的做法是一模一样的 :Cry-Out: 难道又是模板敲错了？
好后悔没有把现场打印的代码拿回来。
#include
#include
#include
#include
#include
using namespace std;
template void checkmin(T &t,T x){if (x < t) t = x;}
template void checkmax(T &t,T x){if (x > t) t = x;}
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 250005;
const int Mod = 2012;
struct Node {
Node *ch[11], *fa;
int val;
int way;
int sum;
Node():
val(0), fa(NULL), way(0), sum(0) {
memset(ch, 0, sizeof(ch));
}
}pool[N * 2 + 5], *last, *root;
vector vec[N];
namespace SAM {
int cnt;
void init() {
if (cnt)
for (int i = 0; i < cnt; i++)
pool[i] = Node();
cnt = 1;
root = &pool[0];
last = root;
}
void add(int c) {
Node *p = last, *np = &pool[cnt++];
last = np;
np->val = p->val + 1;
for (; p && !p->ch; p = p->fa)
p->ch = np;
if (!p) {
np->fa = root;
} else {
Node *q = p->ch;
if (p->val + 1 == q->val) {
np->fa = q;
} else {
Node *nq = &pool[cnt++];
*nq = *q;
nq->val = p->val + 1;
q->fa = nq;
np->fa = nq;
for (; p && p->ch == q; p = p->fa)
p->ch = nq;
}
}
}
}
bool cmp(int i, int j) {
return pool[i].val < pool[j].val;
}
int n, m;
char S[N], buf[N];
void calc() {
int ans = 0;
vector vec;
for (int i = 0; i < SAM::cnt; i++) {
vec.push_back(i);
pool[i].way = pool[i].sum = 0;
}
sort(vec.begin(), vec.end(), cmp);
root->way = 1;
root->sum = 0;
foreach (it, vec) {
int i = *it;
Node *p = &pool[i];
for (int c = i == 0 ? 1 : 0; c < 10; c++) {
if (p->ch) {
p->ch->way += p->way;
p->ch->way %= Mod;
p->ch->sum += p->sum * 10 + p->way * c;
p->ch->sum %= Mod;
}
}
ans += p->sum;
ans %= Mod;
}
printf("%d\n", ans);
}
int main(){
while (scanf("%d", &n) != EOF) {
m = 0;
SAM::init();
for (int i = 0; i < n; i++) {
scanf("%s", buf);
int len = strlen(buf);
for (int j = 0; j < len; j++) {
SAM::add(buf[j] - '0');
}
SAM::add(10);
}
calc();
}
}