考研路茫茫——单词情结 HDU-2243

题面

题解

正好又把AC自动机复习了一遍

正难则反, 我们可以去求有多少至多长度为L的串不含任何任何匹配串的数量

在 query 的时候对每个经过的节点打标记, 统计文本有多少个匹配串

这道题是不能走到任何一个字符串结尾的节点

除了在(insert)的时候打标记, 还要在构建(fail)指针的时候, 打标记 tag[trie[p][ch]] |= tag[trie[fail[p]][ch]]}$

尽管当前节点不是结尾, 但是存在失陪之后向下走遇到结尾节点, 所以(build()) 的时候也要打标记

就是没考虑到这点, wa了一下午, wssb

回到题目, 本质上就是我们在自动机上乱走, 走至多L步且不经过结尾节点的路径条数

求走过x步的路径条数, 这明显是矩阵加速就路径数

不经过结尾节点, 那就在路径矩阵矩阵(A(1))中把对应的边扔了就好

路径矩阵中 (a_{ij}) 表示从 (i) 到 (j) 的路径条数

这道题是求至多L步, 也就是 (sum_{i = 1}^L sum_{j = 0}^{自动机节点数} A_i.a_{0, j})

且 (A_i = A_{i - 1} imes A_1)

(S_i = sum_{i = 1}^L A_i) 则存在 (S_i = S_{i - 1} imes A_1 + A_1)

则可矩阵加速求(S_i)

(egin{vmatrix} S_i & A_1 end{vmatrix} = egin{vmatrix} S_0 & A_i end{vmatrix} imes egin{vmatrix} A_1 & 0 \ E & E end{vmatrix})

现在就差至多走L步有多少条路径了, 这就好求多了, 设至多走x步有 (F(i)) 路径数, 则(F(i) = F(i - 1) * 26 + 26) 也是个矩阵加速

(egin{vmatrix} F_i & 26 end{vmatrix} = egin{vmatrix} F_0 & 26 end{vmatrix} imes egin{vmatrix} 26 & 0 \ E & E end{vmatrix})

最后一减就有了, 什么取膜? ull自然取膜啦

代码

struct AC {
    static const int N = 26, M = 26, C = 'a';
    int tr[N][M], cnt[N], fail[N], q[N], tot;
    void init() { memset(tr[0], 0, sizeof tr[0]); fail[0] = tot = 0; }
    int newNode() { memset(tr[++tot], 0, sizeof tr[0]); fail[tot] = cnt[tot] = 0; return tot; }
    void insert(char* s) {
        int p = 0;
        for (int i = 0, ch = s[i] - C; s[i]; p = tr[p][ch], ch = s[++i] - C)
            if (!tr[p][ch]) tr[p][ch] = newNode();
        ++cnt[p];
    }
    void build() {
        int h = 0, t = -1;
        rep(i, 0, M - 1) if (tr[0][i]) q[++t] = tr[0][i];
        for (int p = q[h]; t >= h; p = q[++h]) rep(i, 0, M - 1)
            if (tr[p][i]) {
                fail[tr[p][i]] = tr[fail[p]][i], q[++t] = tr[p][i];
                cnt[tr[p][i]] += cnt[tr[fail[p]][i]];
            }
            else tr[p][i] = tr[fail[p]][i];
    }
} ac;

struct Matrix {
    vector<vector<ull>> a;
    Matrix(int N = 0, int M = 0) { vector<vector<ull>>(N, vector<ull>(M)).swap(a); }
    Matrix operator*(Matrix b) {
        Matrix c(a.size(), b.a[0].size());
        rep(i, 0, a.size() - 1) rep(j, 0, b.a[0].size() - 1) rep(k, 0, b.a.size() - 1)
            c.a[i][j] += a[i][k] * b.a[k][j];
        return c;
    }
};

Matrix qpow(Matrix a, ll b) {
    Matrix c(a.a.size(), a.a.size());
    rep(i, 0, a.a.size() - 1) c.a[i][i] = 1;
    for (; b; b >>= 1, a = a * a) if (b & 1) c = c * a;
    return c;
}

int n, m, _, k, cas;
char s[6];

pair<Matrix, Matrix> init() {
    Matrix a(ac.tot + 1, ac.tot + 1 << 1), c(ac.tot + 1 << 1, ac.tot + 1 << 1);
    rep(i, 0, ac.tot) c.a[i + ac.tot + 1][i] = c.a[i + ac.tot + 1][i + ac.tot + 1] = 1;
    rep(i, 0, ac.tot) if (!ac.cnt[i]) rep(j, 0, ac.M - 1) if (!ac.cnt[ac.tr[i][j]])
        a.a[i][ac.tr[i][j] + ac.tot + 1] = ++c.a[i][ac.tr[i][j]];
    return { a, c };
}

int main() {
    IOS; Matrix p(2, 2); p.a[0][0] = 26; p.a[1][0] = p.a[1][1] = 1;
    while (cin >> n >> m) {
        ac.init(); ull ans = 0; auto b = qpow(p, m);
        rep(i, 1, n) cin >> s, ac.insert(s);
        ac.build(); auto a = init();
        a.se = qpow(a.se, m); a.fi = a.fi * a.se;
        rep(i, 0, ac.tot) ans += a.fi.a[0][i];
        cout << b.a[1][0] * 26ull - ans << '
';
    }
    return 0;
}