3530: [Sdoi2014]數數

3530: [Sdoi2014]數數

鏈接

分析：

　　對給定的串建立AC自動機，然后數位dp。數位dp的過程中，記錄當前在AC自動機的哪個點上，保證不能走到出現了給定串的點。

代碼：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;inline int read() {int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}const int N = 2005, mod = 1e9 + 7;
int ch[N][10], q[N], fail[N], last[N], val[N], dp[N][N], Index;
char s[N], t[N];void Insert(char *s) {int len = strlen(s), u = 0;for (int i = 0; i < len; ++i) {int c = s[i] - '0';if (!ch[u][c]) ch[u][c] = ++Index;u = ch[u][c];}val[u] = 1;
}
void bfs() {int L = 1, R = 0;for (int i = 0; i < 10; ++i) if (ch[0][i]) q[++R] = ch[0][i];while (L <= R) {int u = q[L ++];for (int c = 0; c < 10; ++c) {int v = ch[u][c];if (!v) ch[u][c] = ch[fail[u]][c];else fail[v] = ch[fail[u]][c], last[v] = val[fail[v]] ? fail[v] : last[fail[v]], q[++R] = v;}}
}
int dfs(int pos,int now,bool lim,bool fir) { // 從高位數第pos位，在AC自動機上的位置，是否有小于n的限制，是否有前導0的限制 if (pos == 0) return 1;if (!lim && !fir && dp[pos][now] != -1) return dp[pos][now];int res = 0, u = lim ? (s[pos] - '0') : 9;if (fir) res = (res + dfs(pos - 1, 0, lim && 0 == u, 1)) % mod; // 如果當前依然沒有出現第一個正整數作為開始，那么繼續從0號點開始走，不能是ch[0][0]!!! for (int i = fir; i <= u; ++i) {int v = ch[now][i];if (val[v] || last[v]) continue; // last表示從當前點沿著fail指針跳的過程中，第一個是給定串的點 res = (res + dfs(pos - 1, v, lim && i == u , 0)) % mod;}if (!lim && !fir) dp[pos][now] = res;return res;
}
int main() {scanf("%s", s + 1);int n = strlen(s + 1);reverse(s + 1, s + n + 1);int m = read();for (int i = 1; i <= m; ++i) {scanf("%s", t);Insert(t);}bfs();memset(dp, -1, sizeof(dp));cout << (dfs(n, 0, 1, 1) - 1 + mod) % mod;return 0;
}

?