企业官网建设流程全解析

题目描述

给定若干个仅包含数字'0'至'9'的字符串，定义集合SSS包含输入中的所有字符串以及它们的所有可能子串（连续子序列）。将SSS中的每个字符串转换为十进制整数（前导零忽略，空串不存在），并去除重复的整数，最后计算所有不同整数的和除以201220122012的余数。

例如，若输入为101和123，则所有不同子串转换后的整数为：1, 10, 101, 2, 3, 12, 23, 123，其和为275275275，模201220122012仍为275275275。

输入格式

输入包含不超过202020个测试用例。每个测试用例第一行为一个正整数NNN（1≤N≤100001 \le N \le 100001≤N≤10000），接下来NNN行每行一个由数字组成的非空字符串。所有字符串的长度之和不超过100000100000100000。输入以EOF\texttt{EOF}EOF结束。

输出格式

对于每个测试用例，输出一行一个整数，表示所求的余数，范围在[0,2011][0, 2011][0,2011]。

样例

输入

5 101 123 09 000 1234567890

输出

202

题目分析

本题的核心是：给定多个数字串，求其所有不同子串对应的数值之和，并对201220122012取模。

直接枚举所有子串并去重，总子串个数最坏为O(L2)O(L^2)O(L2)（其中LLL为总长度），显然不可行（LLL可达10510^5105）。因此需要利用自动机或后缀数据结构来高效地枚举所有不同的子串，并同时统计它们的数值之和。

注意到数值与子串的前缀有关，且前导零不影响数值（例如"01"与"1"数值相同）。因此，所有不同的整数实际上等价于：所有不以'0'开头且不同的子串的数值，再加上数值0（值为000，不影响和）。这样我们就避免了处理大量以'0'开头的重复情况。

解题思路

1. 去重与后缀自动机

统计一个字符串集合的所有不同子串，经典数据结构是后缀自动机（SAM，Suffix Automaton\texttt{SAM，Suffix Automaton}SAM，Suffix Automaton）。将所有输入串用一个分隔符（如'#'）连接成一个长串，构建其后缀自动机。在后缀自动机中，从初始状态出发的每一条路径都唯一对应原串的一个不同子串。

我们只关心数字路径，即不经过分隔符的路径。并且首位不能是'0'，因此我们只统计从初始状态出发，第一条边为'1'至'9'的所有路径。

2. 动态规划统计数值之和

对于后缀自动机上的每个状态vvv，我们需要计算从该状态出发的所有数字路径（包括空路径）的两类信息：

• A[v]A[v]A[v]：所有路径长度的10len10^{\text{len}}10len之和（即10路径长度10^{\text{路径长度}}10路径长度的和），模201220122012。空路径长度为000，贡献为111。
• B[v]B[v]B[v]：所有路径对应的十进制数值之和（空路径数值为000），模201220122012。

对于一条数字边v→cuv \xrightarrow{c} uvc​u（c∈[0,9]c \in [0,9]c∈[0,9]），从vvv出发经过该边到达uuu，再走uuu的任意后续路径ppp。若uuu的后续路径长度为lll，数值为xxx，则从vvv出发的该路径数值为c⋅10l+xc \cdot 10^{l} + xc⋅10l+x。因此，对A[v]A[v]A[v]的贡献为10⋅A[u]10 \cdot A[u]10⋅A[u]（因为长度增加111，10l+1=10⋅10l10^{l+1} = 10 \cdot 10^l10l+1=10⋅10l），对B[v]B[v]B[v]的贡献为c⋅A[u]+B[u]c \cdot A[u] + B[u]c⋅A[u]+B[u]。

由于后缀自动机的转移都是从长度较小的状态指向长度较大的状态，可以按状态长度递减的顺序进行DP\texttt{DP}DP。

3. 汇总答案

最终答案只需枚举初始状态000的数字出边c∈[1,9]c \in [1,9]c∈[1,9]，设到达状态为uuu，则所有以ccc开头的不同子串的数值总和为c⋅A[u]+B[u]c \cdot A[u] + B[u]c⋅A[u]+B[u]，累加并对201220122012取模即可。

4. 复杂度分析

• 构建后缀自动机的时间复杂度为O(L)O(L)O(L)，其中LLL为所有输入串长度之和加上分隔符个数，L≤1.1×105L \le 1.1 \times 10^5L≤1.1×105。
• DP\texttt{DP}DP状态数为自动机状态数O(L)O(L)O(L)，每个状态枚举101010个数字转移，复杂度O(10⋅L)O(10 \cdot L)O(10⋅L)。
• 排序状态按长度递减，可使用基数排序或直接按长度排序，复杂度O(Llog⁡L)O(L \log L)O(LlogL)或O(L)O(L)O(L)（本文代码采用sort\texttt{sort}sort，满足要求）。
• 总时间复杂度O(Llog⁡L)O(L \log L)O(LlogL)，空间复杂度O(L⋅11)O(L \cdot 11)O(L⋅11)（转移数组大小）。

代码实现

// str2int// UVa ID: 1673// Verdict: Accepted// Submission Date: 2026-06-20// UVa Run Time: 0.080s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMOD=2012;constintALPHA=11;// 0~9 和 '#'（映射为 10）structState{intnext[ALPHA];intlink,len;State(){memset(next,-1,sizeof(next));link=-1;len=0;}};vector<State>st;intlast;voidsam_init(){st.clear();st.push_back(State());last=0;}voidsam_extend(intc){intcur=(int)st.size();st.push_back(State());st[cur].len=st[last].len+1;intp=last;while(p!=-1&&st[p].next[c]==-1){st[p].next[c]=cur;p=st[p].link;}if(p==-1){st[cur].link=0;}else{intq=st[p].next[c];if(st[p].len+1==st[q].len){st[cur].link=q;}else{intclone=(int)st.size();st.push_back(State());st[clone].len=st[p].len+1;memcpy(st[clone].next,st[q].next,sizeof(st[q].next));st[clone].link=st[q].link;while(p!=-1&&st[p].next[c]==q){st[p].next[c]=clone;p=st[p].link;}st[q].link=st[cur].link=clone;}}last=cur;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;while(cin>>N){string total;for(inti=0;i<N;++i){string s;cin>>s;total+=s;total+='#';// 分隔符，不与数字混淆}sam_init();for(charch:total){intc=(ch=='#')?10:(ch-'0');sam_extend(c);}intsz=(int)st.size();vector<int>order(sz);iota(order.begin(),order.end(),0);sort(order.begin(),order.end(),[&](inta,intb){returnst[a].len>st[b].len;});vector<int>A(sz,0),B(sz,0);for(intv:order){A[v]=1;// 空路径：10^0 = 1B[v]=0;// 空路径数值为 0for(intc=0;c<=9;++c){// 只处理数字转移intu=st[v].next[c];if(u==-1)continue;A[v]=(A[v]+10*A[u])%MOD;B[v]=(B[v]+c*A[u]+B[u])%MOD;}}intans=0;for(intc=1;c<=9;++c){// 首位不能为 '0'intu=st[0].next[c];if(u==-1)continue;ans=(ans+c*A[u]+B[u])%MOD;}cout<<ans<<'\n';}return0;}

总结

本题巧妙地将去重子串问题转化为后缀自动机上的路径计数问题。关键技巧包括：

• 利用前导零的性质，只统计非零开头的子串，避免处理重复的0值；
• 在后缀自动机的DP\texttt{DP}DP中，同时维护长度幂和数值和，从而快速计算所有不同子串的数值之和；
• 通过分隔符将多个字符串合并，保证自动机中的路径不会跨越不同原串，正确得到所有子串。

这种结合后缀自动机与动态规划的方法，在处理大规模字符串集合的统计问题时非常有效，值得熟练掌握。