hdu2825（AC 自动机）

hdu2825

题意

给出一些字符串，要求构造一个长度为 \(n\) 的字符串至少包括其中的 \(k\) 个，问有多少种字符串满足条件。

分析

AC自动机构造状态转移，然后状态压缩DP 即可。

\(dp[i][j][k]\) 表示长度为 \(i\) 在 AC自动机上的状态为 \(j\) 已包含的字符串为 \(k\) 时的字符串数量（ \(k\) 二进制表示是否有某个给出的字符串）。

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

typedef long long ll;

const int MAXN = 1e2 + 10;

const int MOD = 20090717;

struct Trie {

    int root, L, nxt[MAXN][26], fail[MAXN], val[MAXN];

    int newnode() {

        memset(nxt[L], -1, sizeof nxt[L]);

        return L++;

    }

    void init() {

        L = 0;

        root = newnode();

        memset(val, 0, sizeof val);

        memset(fail, 0, sizeof fail);

    }

    void insert(int id, char S[]) {

        int len = strlen(S);

        int now = root;

        for(int i = 0; i < len; i++) {

            int d = S[i] - 'a';

            if(nxt[now][d] == -1) nxt[now][d] = newnode();

            now = nxt[now][d];

        }

        val[now] |= (1 << id);

    }

    void build() {

        queue<int> Q;

        for(int i = 0; i < 26; i++) {

            if(nxt[root][i] == -1) nxt[root][i] = 0;

            else { fail[nxt[root][i]] = root; Q.push(nxt[root][i]); }

        }

        while(!Q.empty()) {

            int now = Q.front(); Q.pop();

            val[now] |= val[fail[now]];

            for(int i = 0; i < 26; i++) {

                if(nxt[now][i] == -1) nxt[now][i] = nxt[fail[now]][i];

                else { fail[nxt[now][i]] = nxt[fail[now]][i]; Q.push(nxt[now][i]); }

            }

        }

    }

}trie;

int dp[30][MAXN][1024];

int cnt[1024];

int main() {

    int n, m, k;

    cnt[0] = 0;

    for(int i = 1; i < 1024; i++) {

        int j = 0;

        while(!((i >> j) & 1)) j++;

        cnt[i] = cnt[i - (1 << j)] + 1;

    }

    while(~scanf("%d%d%d", &n, &m, &k) && (n + m + k)) {

        trie.init();

        for(int i = 0; i < m; i++) {

            char s[15];

            scanf("%s", s);

            trie.insert(i, s);

        }

        trie.build();

        for(int i = 0; i <= n; i++) {

            for(int j = 0; j < trie.L; j++) {

                for(int k = 0; k < (1 << m); k++) {

                    dp[i][j][k] = 0;

                }

            }

        }

        dp[0][0][0] = 1;

        for(int i = 0; i < n; i++) {

            for(int j = 0; j < trie.L; j++) {

                for(int bit = 0; bit < (1 << m); bit++) {

                    if(!dp[i][j][bit]) continue;

                    for(int k = 0; k < 26; k++) {

                        int tmp = trie.nxt[j][k];

                        (dp[i + 1][tmp][trie.val[tmp] | bit] += dp[i][j][bit]) %= MOD;

                    }

                }

            }

        }

        int sum = 0;

        for(int i = 0; i < trie.L; i++) {

            for(int j = 0; j < (1 << m); j++) {

                if(cnt[j] >= k) sum = (sum + dp[n][i][j]) % MOD;

            }

        }

        printf("%d\n", sum);

    }

    return 0;

}

巴特西

hdu2825（AC 自动机）

hdu2825

题意

分析

code

最新文章

热门文章