# 描述

In this problem, you are given several strings that contain only digits from 0 to 9, inclusive.
An example is shown below.

101123

The set $S$ of strings is consists of the $N$ strings given in the input file, and all the possible substrings of each one of them.
It’s boring to manipulate strings, so you decide to convert strings in $S$ into integers.
You can convert a string that contains only digits into a decimal integer, for example, you can convert "101" into $101$, "01" into $1$, et al.
If an integer occurs multiple times, you only keep one of them.
For example, in the example shown above, all the integers are $1$, $10$, $101$, $2$, $3$, $12$, $23$, $123$.
Your task is to calculate the remainder of the sum of all the integers you get divided by $2012$.

## Input

There are no more than $20$ test cases.
The test case starts by a line contains an positive integer $N$.
Next $N$ lines each contains a string consists of one or more digits.
It’s guaranteed that $1≤N≤10000$ and the sum of the length of all the strings $≤100000$.
The input is terminated by EOF.

## Output

An integer between $0$ and $2011$, inclusive, for each test case.

# 思路

• 建立多串的后缀自动机，然后拓扑排序后DP。
• 设$dp[u]$表示走到结点$u$的方案数，$sum[u]$表示到达结点$u$的这些整数之和。这样有
\begin{align} dp[v] &= \sum_{\substack{u:\\(u,v,c)\in DAWG}}dp[u] \\ sum[v] &= \sum_{\substack{u:\\(u,v,c)\in DAWG}}(10\times sum[u] + dp[u] \times c) \end{align}
• 然后注意处理一下前导零就好了。

0%