题解 P3311 【[SDOI2014]数数】

Log_x

2017-07-14 14:32:41

Solution

##AC自动机 + DP **【解题思路】** 参考[http://blog.csdn.net/Regina8023/article/details/44974979](http://blog.csdn.net/Regina8023/article/details/44974979) 先用 $AC$ 自动机对 $S$ 集合的字符串建立 $Trie$ 树,记数组 $nxt$ 表示 $AC$ 自动机的失败指针,数组 $lst[x]$ 在点 $x$ 表示沿着失败指针能否走到一个 $S$ 集合中的串末尾,如有则记为这个字符串的编号。 然后我们记 $f[i][j][k]$ 表示当前已经确定到第 $i$ 位数,走到 $AC$ 自动机上的节点 $j$,且状态为 $k$ 的总方案数(因为要处理前导0的问题,这里的第 $i$ 位从高位向低位计算,当取最高位,即 $i = 1$ 时,应不包含取0的方案数)。 对于状态 $k$,我们有如下定义: [1]. $k = 0$ 已经确定的 $i$ 位数小于 $N$ 的前 $i$位; [2]. $k = 1$ 已经确定的 $i$ 位数等于 $N$ 的前 $i$ 位; [3]. $k = 2$ 已经确定的 $i$ 位数大于 $N$ 的前 $i$ 位。 接下来我们考虑如何转移:枚举第 $i + 1$ 位选取的数字 $num$,可以利用我们刚才的 $AC$ 自动机判断:这样确定的 $i + 1$ 位数字是否存在某个 $S$ 集合中的串是它的后缀。如不存在我们就可以确定 $AC$ 自动机上的节点 $x$,则 $f[i + 1][x][k’]$ 就可以由 $f[i][j][k]$ 转移过来,最终的转移如下(可结合此时已经确定的 $i$ 位数与 $N$ 的前 $i$ 位的大小关系来理解): [1]. 若 $num$ 小于 $N$ 的第 $i + 1$ 位: $f[i + 1][x][0] += f[i][j][0] + f[i][j][1]$ $f[i + 1][x][2] += f[i][j][2]$ [2]. 若 $num$ 等于 $N$ 的第 $i + 1$ 位: $f[i + 1][x][0] += f[i][j][0] $ $f[i + 1][x][1] += f[i][j][1]$ $f[i + 1][x][2] += f[i][j][2]$ [3]. 若 $num$ 大于 $N$ 的第 $i + 1$位: $f[i + 1][x][0] += f[i][j][0]$ $f[i + 1][x][2] += f[i][j][2] + f[i][j][1]$ 每确定一位数都要将 $\sum \limits^2_{k’ = 0} f[i + 1][j][k’]$ 累加进答案 $Ans$,同时因为幸运数不能大于 $N$,所以最终的答案还要减去 $\sum f[n][j][2]$($n$ 为数 $N$ 的位数)。 **【代码】** ```cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int Maxn = 0x3f3f3f3f; const int N = 1505, M = 1205; const ll Mod = 1e9 + 7; ll f[M][N][3], Ans; bool pos[N]; char s[M], a[N]; int n, m, T, G[N][10], Q[N], nxt[N], lst[N]; inline int get() { char ch; bool f = false; int res = 0; while (((ch = getchar()) < '0' || ch > '9') && ch != '-'); if (ch == '-') f = true; else res = ch - '0'; while ((ch = getchar()) >='0' && ch <= '9') res = (res << 3) + (res << 1) + ch - '0'; return f? ~res + 1 : res; } inline void put(int x) { if (x < 0) x = ~x + 1, putchar('-'); if (x > 9) put(x / 10); putchar(x % 10 + 48); } inline void Insert() { scanf("%s", a + 1); int x = 0, l = strlen(a + 1); for (int i = 1; i <= l; ++i) { int y = a[i] - '0'; if (!G[x][y]) G[x][y] = ++T; x = G[x][y]; } pos[x] = true; } inline void Bfs() { int t, w, x, y; t = w = 0; for (int i = 0; i < 10; ++i) if (G[0][i]) Q[++w] = G[0][i]; while (t < w) { x = Q[++t]; for (int i = 0; i < 10; ++i) if (!G[x][i]) G[x][i] = G[nxt[x]][i]; else { Q[++w] = y = G[x][i]; int v = nxt[x]; while (!G[v][i] && v) v = nxt[v]; nxt[y] = G[v][i]; lst[y] = pos[nxt[y]] ? nxt[y] : lst[nxt[y]]; } } } inline int cmp(const int &x, const int &y) { if (x > y) return 2; if (x < y) return 0; return 1; } int main() { scanf("%s", s + 1); n = strlen(s + 1); m = get(); while (m--) Insert(); Bfs(); for (int i = 1; i < 10; ++i) //不含前导0 { int x = G[0][i]; if (!pos[x] && !lst[x]) f[1][x][cmp(i, s[1] - '0')]++; } for (int i = 0; i <= T; ++i) (Ans += f[1][i][0] + f[1][i][1] + f[1][i][2]) %= Mod; for (int i = 1; i < n; ++i) { for (int j = 0; j <= T; ++j) if (f[i][j][0] || f[i][j][1] || f[i][j][2]) for (int k = 0; k < 10; ++k) { int x = j; while (!G[x][k] && x) x = nxt[x]; x = G[x][k]; if (pos[x] || lst[x]) continue; int v = cmp(k, s[i + 1] - '0'); switch (v) { case 0: (f[i + 1][x][0] += f[i][j][0] + f[i][j][1]) %= Mod; (f[i + 1][x][2] += f[i][j][2]) %= Mod; break; case 1: (f[i + 1][x][0] += f[i][j][0]) %= Mod; (f[i + 1][x][1] += f[i][j][1]) %= Mod; (f[i + 1][x][2] += f[i][j][2]) %= Mod; break; case 2: (f[i + 1][x][2] += f[i][j][2] + f[i][j][1]) %= Mod; (f[i + 1][x][0] += f[i][j][0]) %= Mod; break; } } for (int j = 0; j <= T; ++j) { (Ans += f[i + 1][j][0] + f[i + 1][j][1]) %= Mod; if (i + 1 < n) (Ans += f[i + 1][j][2]) %= Mod; } } return put(Ans), 0; } ```