题解 P3311 【[SDOI2014]数数】
Log_x
2017-07-14 14:32:41
##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;
}
```