hyz's blog
0%

HDU 2825 Wireless Password 题解

发表于

题意

已知有m个单词，问有多少个长度为n的、且至少含有m个单词中的k个的WIFI密码，注意单词可以重叠。

分析

注意到是多模式串匹配问题，考虑用AC自动机建状态转移图。节点上标记下该节点覆盖了哪些单词，用一个int表示即可，注意要或上fail指针指向节点的标记。然后以dp[i][j][k]表示从单词长度为i、当前节点为j、覆盖单词为k的方案数，转移途径为j的下一个节点。最终答案就是单词长度为n、图上各节点、覆盖单词数不小于k的dp和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const long double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double Eps = 1e-7;
const int N = 1e5+9;

const int mod = 20090717;

char s[19];
int n, m, k, dp[26][109][1029];

struct node {
    int idx, status;
    node() {}
    node(int idx, int status): idx(idx), status(status){}
};

/********************************************************************************/
/* AC自动机：解决多个模式串匹配问题(Tested 3 times)
 */
struct AC {
    int next[109][26], fail[109], end[109], idx, root; // 可以修改下数组大小，以防MLE
    void init() {
        idx = 0;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < 26; i++)
            next[idx][i] = -1;
        end[idx] = 0;
        return idx++;
    }
    void insert(char s[], int id) {
        int len = strlen(s), now = root;
        for(int i = 0; i < len; i++) {
            if(next[now][s[i] - 'a'] == -1)
                next[now][s[i] - 'a'] = newNode();
            now = next[now][s[i] - 'a'];
        }
        end[now] = 1 << id;
    }
    void build() {
        queue<int> que;
        fail[root] = root;
        for(int i = 0; i < 26; i++) {
            if(next[root][i] == -1) {
                next[root][i] = root;
            }
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        }
        while(que.size()) {
            int now = que.front();
            que.pop();
            end[now] |= end[fail[now]];
            for(int i = 0; i < 26; i++) {
                if(next[now][i] == -1) {
                    next[now][i] = next[fail[now]][i];
                }
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
            }
        }
    }
    void query() {
        for(int i = 0; i <= n; i++)
            for(int j = 0; j < idx; j++)
                for(int k = 0; k < (1 << m); k++)
                    dp[i][j][k] = 0;
        dp[0][0][0] = 1;
        queue<node> que;
        que.push(node{0, 0});
        bool vis[259][1029];
        for(int i = 1; i <= n; i++) {
            queue<node> nextque;
            memset(vis, 0, sizeof vis);
            while(que.size()) {
                node t = que.front();
                que.pop();
                for(int o = 0; o < 26; o++) {
                    int j = t.idx;
                    int k = t.status;
                    int newj = next[j][o];
                    int newk = t.status | end[newj];
                    dp[i][newj][newk] += dp[i - 1][j][k];
                    if(dp[i][newj][newk] >= mod)
                        dp[i][newj][newk] -= mod;
                    if(!vis[newj][newk]) {
                        vis[newj][newk] = true;
                        nextque.push({newj, newk});
                    }
                }
            }
            que = nextque;
        }
        ll ans = 0;
        for(int i = 0; i < idx; i++) {
            for(int j = 0; j < 1 << m; j++) {
                // 可以把__builtin_popcount(j)预处理掉，这样更快
                if(__builtin_popcount(j) >= k) {
                    ans += dp[n][i][j];
                    if(ans >= mod)
                        ans -= mod;
                }
            }
        }
        printf("%lld\n", ans);
    }
    void debug() {
        printf("%37c", ' ');
        for(int i = 0; i < 26; i++)
            printf("%2c", i + 'a');
        printf("\n");
        for(int i = 0;i < idx;i++) {
            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
}ac;
/********************************************************************************/

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d%d", &n, &m, &k) && n) {
        ac.init();
        for(int i = 0; i < m; i++) {
            scanf("%s", s);
            ac.insert(s, i);
        }
        ac.build();
        ac.query();
    }

    return 0;
}