HihoCoder - 1457 后缀自动机四·重复旋律7 后缀自动机+拓扑排序+递推、BFS

2017年4月22日 11点热度 0条评论 来源: ProLightsfxjh

后缀自动机四·重复旋律7

时间限制:
15000ms 单点时限:
3000ms 内存限制:
512MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。

神奇的是小Hi发现了一部名字叫《十进制进行曲大全》的作品集,顾名思义,这部作品集里有许多作品,但是所有的作品有一个共同特征:只用了十个音符,所有的音符都表示成0-9的数字。

现在小Hi想知道这部作品中所有不同的旋律的“和”(也就是把串看成数字,在十进制下的求和,允许有前导0)。答案有可能很大,我们需要对(10^9 + 7)取摸。

解题方法提示

输入

第一行,一个整数N,表示有N部作品。

接下来N行,每行包含一个由数字0-9构成的字符串S。

所有字符串长度和不超过 1000000。

输出

共一行,一个整数,表示答案 mod (10^9 + 7)。

样例输入

2
101
09

样例输出

131

Source

HihoCoder - 1457

My Solution

题意:所有字符串的不同子串的“和”(也就是把串看成数字,在十进制下的求和,允许有前导0)。

后缀自动机+拓扑排序+递推、BFS

首先如果只是一个字符串,则转移的时候,st[i] == v节点会转移到u节点,则 cnt[u] = sigma{cnt[v] * 10 + c *  |substrings(v)|  | trans[v][c] = u},

其中cnt[v]表示以v结尾的不同子串的和, |substrings(v)| 即为以v结尾的不同子串的个数即从s到v的路径数。

然后推广到这里的n个串,可以用 ':' 来连接这些字符串成一个串,其中 ':' - '0' == 10,

此时转移的时候,st[i] == v节点会转移到u节点,则 cnt[u] = sigma{cnt[v] * 10 + c *  |validsubstrings(v)|  | trans[v][c] = u},

其中 validsubstring(v)表示不含':' 的不同子串的个数,即从s到v的不含 ':' 的路径条数这个可以通过拓扑排序求出,因为SAM本身就是一个DAG。

然后 cnt[i]也是通过拓扑排序递推出来,2个拓扑排序可以同时进行。

最后的答案就是 sigma{cnt[i]} % MOD。

复杂度 O(n + m)

#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
const int MAXN = 2*1e6 + 8;
const LL MOD = 1e9 + 7;

string s;
struct SAM{
    int ch[MAXN][12], pre[MAXN], val[MAXN];
    int last, tot;
    void init(){
        last = tot = 0;
        memset(ch[0], -1, sizeof ch[0]);
        pre[0] = -1; val[0] = 0;
    }
    void extend(int c){
        int p = last, np = ++tot;
        val[np] = val[p] + 1;
        memset(ch[np], -1, sizeof ch[np]);
        while(~p && ch[p][c] == -1) ch[p][c] = np, p = pre[p];
        if(p == -1) pre[np] = 0;
        else{
            int q = ch[p][c];
            if(val[q] != val[p] + 1){
                int nq = ++tot;
                memcpy(ch[nq], ch[q], sizeof ch[q]);
                val[nq] = val[p] + 1;
                pre[nq] = pre[q];
                pre[q] = pre[np] = nq;
                while(~p && ch[p][c] == q) ch[p][c] = nq, p = pre[p];
            }
            else pre[np] = q;
        }
        last = np;
    }

    //get_ans
    int deg[MAXN];
    LL cnt[MAXN], validsubstr[MAXN];
    queue<ii> que;
    LL mod(LL x){
        return x - x / MOD * MOD;
    }
    LL sum = 0;
    string str;
    void bfs(){
        int fa, u, v, sz, i;
        LL validsubstring;
        validsubstr[0] = 1;
        sz = 11;
        while(!que.empty()){
            u = que.front().first;
            fa = que.front().second;
            que.pop();
            for(i = 0; i < sz; i++){
                v = ch[u][i];
                if(v == fa) continue;
                if(v == -1) continue;
                deg[v]--;
                validsubstring = i == 10 ? 0 : validsubstr[u];
                validsubstr[v] = mod(validsubstr[v] + validsubstring);
                if(validsubstring > 0) cnt[v] = mod(cnt[v] + mod(cnt[u]*10) + validsubstring * i);
                if(deg[v] == 0){
                    que.push(ii(v, u));
                    sum = mod(sum + cnt[v]);
                }
            }
        }
    }
    void get_deg(){
        int i, j;
        for(i = 0; i <= tot; i++){
            for(j = 0; j <= 10; j++){
                if(ch[i][j] != -1) deg[ch[i][j]]++;
            }
        }
    }
    void get_ans(){
        memset(deg, 0, sizeof deg);
        memset(cnt, 0, sizeof cnt);
        memset(validsubstr, 0, sizeof validsubstr);
        int n, i, j, sz;
        cin >> n;
        cin >> s;
        for(i = 1; i < n; i++){
            cin >> str;
            s += ':';
            s += str;
        }
        //cout << (':' - '0') << endl;  //(':' - '0') == 10
        sz = s.size();
        init();
        for(i = 0; i < sz; i++) extend(s[i] - '0');
        get_deg();
        que.push(ii(0, -1));
        bfs();
        cout << sum << endl;
    }

} sam;

int main()
{
    #ifdef LOCAL
    freopen("23.in", "r", stdin);
    //freopen("23.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    sam.get_ans();

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

  Thank you!

                                                                                                                                             ------from ProLights

    原文作者:ProLightsfxjh
    原文地址: https://blog.csdn.net/ProLightsfxjh/article/details/70473775
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。