现在要组成一个长度为11且开头为1的数字串，有n（1<=n<=100）个长度小于等于5的数字串,现在把组成的字符串分成三段，有四种分法： 1. xxx-xxx-xxxxx 例如 151-958-83019 2. xxx-xxxx-xxxx 例如 151-9588-3019 3. xxxx-xxxx-xxx 例如 1519-5883-019 4. xxxx-xxx-xxxx 例如 1519-588-3019 要求每一段都不包含那个n串，有多少种方案。
比赛时直接预处理了一下接着暴力，然后梦想地过了。 题解说，对n个串建一个AC自动机，设 fi,S 表示走了i步，在自动机上的状态为S的方案数，然后设 g(i) 表示在各种分法中，比它小的最大的边界，判一下，不合法就不传。 给出暴力标：
#include<cstdio> #include<cstring> #define ll long long #define fo(i, x, y) for(int i = x; i <= y; i ++) #define fd(i, x, y) for(int i = x; i >= y; i --) using namespace std; int n, a10[20], a[101][2], f[12][100000]; char c[10]; int d[100000][101]; int b[10][2] = {{0, 0}, {5, 5}, {4, 4}, {3, 3}, {8, 3}, {8, 4}, {7, 4}, {7, 3}, {11, 3}, {11, 4}}; int main() { a10[0] = 1; fo(i, 1, 9) a10[i] = a10[i - 1] * 10; scanf("%d", &n); fo(i, 1, n) { scanf("%s", c + 1); a[i][1] = strlen(c + 1); a[i][0] = 0; fd(j, a[i][1], 1) a[i][0] = a[i][0] * 10 + c[j] - 48; } fo(i, 1, n) { fo(j, 0, 99999) { int bz = 0; fo(w, 1, 6 - a[i][1]) if((j % a10[a[i][1] + w - 1]) / a10[w - 1] == a[i][0]) { bz = w + a[i][1] - 1; break; } if(bz) d[j][++ d[j][0]] = bz; } } f[0][0] = 1; fo(i, 1, 11) { fo(j, 0, 99999) fo(num, 0, 9) f[i][j % a10[4] * 10 + num] += f[i - 1][j]; fo(k, 1, 9) if(b[k][0] == i){ fo(j, 0, 99999) if(f[i][j] > 0) { fo(u, 1, d[j][0]) if(d[j][u] <= b[k][1]) { f[i][j] = 0; break; } } } } ll ans = 0; fo(i, 0, 99999) if(i % 10 == 1) ans += f[11][i]; printf("%lld\n", ans); }