相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2471
神犇题解:http://www.cnblogs.com/clrs97/p/5993606.html
解题报告
我们考虑从高位开始,逐位枚举。那么每枚举一位相当于将序列划分为10分,并且取其中一份。
对于一段连续的序列来讲,我们只需要关注其进入这段序列之前会匹配到x的哪一位、匹配完这一段之后匹配到了x的哪一位、这期间总共贡献了多少次成功的匹配。
不难发现这个状态是很少的,于是我们可以记忆化搜索。
另外这题很容易扩展到:“左右边界为任意值的情况”
然后我把这题搬到了今年的全国胡策里,不知道有没有人能切掉
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 16; const int M = 10; const int SGZ = 10; const int MOD = 1000000007; int n, m, nxt[M]; char s[M]; struct Transfer{ LL pos, cnt; inline Transfer() { } inline Transfer(LL a, LL b):pos(a), cnt(b) { } inline Transfer operator + (const Transfer &T) { return Transfer(T.pos, cnt + T.cnt); } }t[M][SGZ]; map<int, Transfer> f[N][M]; struct MatchStatus{ int HashVal; Transfer t[M]; inline void GetHashVal() { const static int MOD = 1000000007; const static int SEED1 = 13, SEED2 = 131; HashVal = 0; for (int i = 0; i < m; i++) { HashVal = (HashVal + (LL)t[i].pos * SEED2 + t[i].cnt) * SEED1 % MOD; } } inline bool operator < (const MatchStatus &MS) const { return HashVal < MS.HashVal; } }; inline Transfer DFS(int w, int p, const MatchStatus &cur) { if (w <= 0) { return cur.t[p]; } else if (f[w][p].count(cur.HashVal)) { return f[w][p][cur.HashVal]; } else { Transfer ret(p, 0); for (int i = 0; i < SGZ; i++) { MatchStatus nw = cur; for (int j = 0; j < m; j++) { nw.t[j] = nw.t[j] + t[nw.t[j].pos][i]; } nw.GetHashVal(); ret = ret + DFS(w - 1, ret.pos, nw); } return f[w][p][cur.HashVal] = ret; } } int main() { while (~scanf("%d %s", &n, s + 1) && n) { m = strlen(s + 1); for (int i = 1; i <= m; i++) { s[i] -= '0'; } nxt[1] = 0; for (int i = 2, j = 0; i <= m; nxt[i++] = j) { for (; j && s[j + 1] != s[i]; j = nxt[j]); j += s[j + 1] == s[i]; } for (int i = 0; i < m; i++) { for (int j = 0; j < SGZ; j++) { int k = i; for (; k && s[k + 1] != j; k = nxt[k]); k += s[k + 1] == j; t[i][j] = k == m? Transfer(nxt[k], 1): Transfer(k, 0); } } for (int i = 1; i <= n; i++) { for (int j = 0; j < m; j++) { f[i][j].clear(); } } Transfer ans(0, 0); for (int i = 1; i <= n; i++) { for (int j = 1; j < SGZ; j++) { MatchStatus cur; for (int k = 0; k < m; k++) { cur.t[k] = t[k][j]; } cur.GetHashVal(); ans = ans + DFS(i - 1, ans.pos, cur); } } printf("%lld\n", ans.cnt); } return 0; }