题目描述给定若干个仅包含数字0至9的字符串定义集合SSS包含输入中的所有字符串以及它们的所有可能子串连续子序列。将SSS中的每个字符串转换为十进制整数前导零忽略空串不存在并去除重复的整数最后计算所有不同整数的和除以201220122012的余数。例如若输入为101和123则所有不同子串转换后的整数为1, 10, 101, 2, 3, 12, 23, 123其和为275275275模201220122012仍为275275275。输入格式输入包含不超过202020个测试用例。每个测试用例第一行为一个正整数NNN1≤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. 去重与后缀自动机统计一个字符串集合的所有不同子串经典数据结构是后缀自动机SAMSuffix Automaton\texttt{SAMSuffix Automaton}SAMSuffix 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​uc∈[0,9]c \in [0,9]c∈[0,9]从vvv出发经过该边到达uuu再走uuu的任意后续路径ppp。若uuu的后续路径长度为lll数值为xxx则从vvv出发的该路径数值为c⋅10lxc \cdot 10^{l} xc⋅10lx。因此对A[v]A[v]A[v]的贡献为10⋅A[u]10 \cdot A[u]10⋅A[u]因为长度增加11110l110⋅10l10^{l1} 10 \cdot 10^l10l110⋅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//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMOD2012;constintALPHA11;// 0~9 和 #映射为 10structState{intnext[ALPHA];intlink,len;State(){memset(next,-1,sizeof(next));link-1;len0;}};vectorStatest;intlast;voidsam_init(){st.clear();st.push_back(State());last0;}voidsam_extend(intc){intcur(int)st.size();st.push_back(State());st[cur].lenst[last].len1;intplast;while(p!-1st[p].next[c]-1){st[p].next[c]cur;pst[p].link;}if(p-1){st[cur].link0;}else{intqst[p].next[c];if(st[p].len1st[q].len){st[cur].linkq;}else{intclone(int)st.size();st.push_back(State());st[clone].lenst[p].len1;memcpy(st[clone].next,st[q].next,sizeof(st[q].next));st[clone].linkst[q].link;while(p!-1st[p].next[c]q){st[p].next[c]clone;pst[p].link;}st[q].linkst[cur].linkclone;}}lastcur;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;while(cinN){string total;for(inti0;iN;i){string s;cins;totals;total#;// 分隔符不与数字混淆}sam_init();for(charch:total){intc(ch#)?10:(ch-0);sam_extend(c);}intsz(int)st.size();vectorintorder(sz);iota(order.begin(),order.end(),0);sort(order.begin(),order.end(),[](inta,intb){returnst[a].lenst[b].len;});vectorintA(sz,0),B(sz,0);for(intv:order){A[v]1;// 空路径10^0 1B[v]0;// 空路径数值为 0for(intc0;c9;c){// 只处理数字转移intust[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;}}intans0;for(intc1;c9;c){// 首位不能为 0intust[0].next[c];if(u-1)continue;ans(ansc*A[u]B[u])%MOD;}coutans\n;}return0;}总结本题巧妙地将去重子串问题转化为后缀自动机上的路径计数问题。关键技巧包括利用前导零的性质只统计非零开头的子串避免处理重复的0值在后缀自动机的DP\texttt{DP}DP中同时维护长度幂和数值和从而快速计算所有不同子串的数值之和通过分隔符将多个字符串合并保证自动机中的路径不会跨越不同原串正确得到所有子串。这种结合后缀自动机与动态规划的方法在处理大规模字符串集合的统计问题时非常有效值得熟练掌握。