做网站找哪里,成品网站灬源码1688,宣传片策划拍摄制作公司,玉儿做春梦网站3530: [Sdoi2014]数数 链接 分析#xff1a; 对给定的串建立AC自动机#xff0c;然后数位dp。数位dp的过程中#xff0c;记录当前在AC自动机的哪个点上#xff0c;保证不能走到出现了给定串的点。 代码#xff1a; #includecstdio
#includealgorithm
#inc…3530: [Sdoi2014]数数 链接 分析 对给定的串建立AC自动机然后数位dp。数位dp的过程中记录当前在AC自动机的哪个点上保证不能走到出现了给定串的点。 代码 #includecstdio
#includealgorithm
#includecstring
#includeiostream
#includecmath
#includecctype
#includeset
#includequeue
#includevector
#includemap
using namespace std;
typedef long long LL;inline int read() {int x0,f1;char chgetchar();for(;!isdigit(ch);chgetchar())if(ch-)f-1;for(;isdigit(ch);chgetchar())xx*10ch-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;
} 转载于:https://www.cnblogs.com/mjtcn/p/10526404.html
