[HDU4436] str2int

Description

给定若干字符串，将每个字符串中的所有子串转化为数字，放在一起去重后，求它们的和 (mod 2012)。

Solution

将各个数字串用奇奇怪怪的字符连接起来，建立 SAM，基数排序预处理出拓扑序

对于结点 (i)，设从根到达它的路径数量（即本质不同子串数）为 (f[i])，它代表的所有本质不同子串转化为数字后的和为 (g[i])，则对于 (i o j) 经过 (c)，有

[f[j]=sum_{i} f[i] \ g[j] = sum_i 10 g[i]+ccdot f[i] ]

特别注意，有前导零的串一定会和另一个没有前导零的串相同，因此我们可以直接将所有带前导零的串都忽略。具体地，只需要根结点转移时控制一下即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 500005;
const int mod = 2012;
const int dbg = 0;

#define reset(x) memset(x,0,sizeof x)

int n;

struct SAM
{
    int len[N], ch[N][12], fa[N], ind, last;
    int t[N], a[N], cnt[N], f[N], g[N];
    SAM()
    {
        ind = last = 1;
    }
    void clear()
    {
        ind = last = 1;
        reset(len);
        reset(ch);
        reset(fa);
        reset(t);
        reset(a);
        reset(cnt);
        reset(f);
        reset(g);
    }
    inline void extend(int id)
    {
        int cur = (++ ind), p;
        len[cur] = len[last] + 1;
        cnt[cur] = 1;
        for (p = last; p && !ch[p][id]; p = fa[p]) ch[p][id] = cur;
        if (!p) fa[cur] = 1;
        else
        {
            int q = ch[p][id];
            if (len[q] == len[p] + 1) fa[cur] = q;
            else
            {
                int tmp = (++ ind);
                len[tmp] = len[p] + 1;
                for(int i=0; i<11; i++) ch[tmp][i] = ch[q][i];
                fa[tmp] = fa[q];
                for (; p && ch[p][id] == q; p = fa[p]) ch[p][id] = tmp;
                fa[cur] = fa[q] = tmp;
            }
        }
        last = cur;
    }
    void calc()
    {
        memset(t, 0, sizeof t);
        for(int i=1; i<=ind; i++) t[len[i]]++;
        for(int i=1; i<=ind; i++) t[i]+=t[i-1];
        for(int i=1; i<=ind; i++) a[t[len[i]]--]=i;
        for(int i=ind; i>=1; --i) cnt[fa[a[i]]]+=cnt[a[i]];
        cnt[1] = 0;
    }
    int solve()
    {
        int ans=0;
        f[1]=1;
        g[1]=0;
        for(int i=1; i<=ind; i++)
        {
            int p=a[i];
            ans+=g[p];
            ans%=mod;
            for(int j=0;j<10;j++) if(ch[p][j])
            {
                if(j==0 && len[p]==0) continue;
                int q=ch[p][j];
                f[q]+=f[p];
                f[q]%=mod;
                g[q]+=10*g[p]+j*f[p];
                g[q]%=mod;
            }
        }
        return ans;
    }
} sam;

void solve()
{
    ios::sync_with_stdio(false);
    sam.clear();
    string str,tmp;
    set <int> st;
    for(int i=1;i<=n;i++)
    {
        if(i>1) str+=':';
        cin>>tmp;
        str+=tmp;
        if(dbg)
        {
            for(int l=0;l<tmp.size();l++)
            {
                for(int r=l;r<tmp.size();r++)
                {
                    string t=tmp.substr(l,r-l+1);
                    int tv=atoi(t.c_str());
                    st.insert(tv);
                }
            }
        }
    }
    for(int i=0;i<str.length();i++)
    {
        sam.extend(str[i]-'0');
    }
    sam.calc();
    cout<<sam.solve()<<endl;
    if(dbg)
    {
        int sum=0;
        for(auto i:st) sum=(sum+i)%mod;
        cout<<sum<<endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);

    while(cin>>n) solve();
}