题解：CF696D Legen...

· · 题解

更好的阅读体验

前置知识：AC 自动机。

Solution

看到子串出现次数，首先会想到建 AC 自动机，这样我们就处理掉了子串出现次数的问题。

但是它带了一个权值 val_i，考虑 dp，记 f_{i,j} 表示当前构造到了长度 i，在自动机上以 j 节点结尾的最大价值，记录每个串的结尾 end，直接 end \leftarrow end + val_i 就可以更方便得到一个子串的权值，只需要在 fail 树上子树和。

那么我们肯定是从根往子节点一路跳，就有：

f_{i+1,son_{j,x}} \leftarrow \max\{f_{i,j} + val_{son_{j,x}}\}

但是你看到 l\leq 10^{14}，这样转移瞬间爆炸。

诶！当我们转移的时候有且仅有 i \to i + 1，那么就可以用矩乘快速幂来优化（其实转移跟遍历图差不多，从上一个状态走到下一个）。

为符合转移的运算我们把矩乘重定义为加法然后取 \max，初始矩阵 mat_{i,son_{i,j}} = end_{son_{i,j}}，想要的答案是 \max\limits_{i=0}^{N}{mat_{0,i}}。

Code

#include <bits/stdc++.h>
#define int long long
#define fail(now) Amt[now].fail
#define end(now) Amt[now].end
#define son(now,x) Amt[now].son[x]

using namespace std;
const int MAXN = 210;
const int MAXS = 200010;

int N, M, cnt, ans;
int val[MAXN];
string Style;

struct Amton {
    int son[26];
    int fail, end;
} Amt[MAXS];

struct Matt {
    int mat[MAXN][MAXN];

    Matt() { memset (mat, -0x3f, sizeof(mat)); }
    Matt operator * (const Matt &s) const {
        Matt res = Matt();
        for (int k = 0; k <= cnt; k ++) {
            for (int i = 0; i <= cnt; i ++) {
                for (int j = 0; j <= cnt; j ++)
                    res.mat[i][j] = max (res.mat[i][j], mat[i][k] + s.mat[k][j]);
            }
        }
        return res;
    }
} base, final;

Matt binpow (Matt x, int p) {
    Matt res = x;
    for (--p; p; p >>= 1) {
        if (p & 1)
            res = res * x;
        x = x * x;
    }
    return res;
}

inline void InsertString (int val) {
    int now = 0, len = Style.length();
    for (int i = 0; i < len; i ++) {
        int chVal = Style[i] - 'a';
        if (!son(now, chVal))
            son(now, chVal) = ++cnt;
        now = son(now, chVal);
    }
    end(now) += val;
}

inline void GetFailPointer() {
    queue<int> q;
    for (int i = 0; i < 26; i ++) {
        if (son(0, i))
            q.emplace (son(0, i));
    }
    while (!q.empty()) {
        int now = q.front(); q.pop();
        end(now) += end(fail(now));
        for (int i = 0; i < 26; i ++) {
            if (!son(now, i))
                son(now, i) = son(fail(now), i);
            else {
                fail(son(now, i)) = son(fail(now), i);
                q.emplace (son(now, i));
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> N >> M, base = Matt();
    for (int i = 1; i <= N; i ++) cin >> val[i];
    for (int i = 1; i <= N; i ++) cin >> Style, InsertString(val[i]);
    GetFailPointer();
    for (int i = 0; i <= cnt; i ++) {
        for (int j = 0; j < 26; j ++)
            base.mat[i][son(i, j)] = end(son(i, j));
    }
    final = binpow (base, M);
    ans = -0x7f7f7f7f7f7f;
    for (int i = 0; i <= cnt; i ++)
        ans = max (ans, final.mat[0][i]);
    cout << ans << '\n';
    return 0;
}