BZOJ 3530 数数

题意：求\(\leq n\)且不包含模式串集合\(S\)内的数作为子串的数的数量， 模式串总长,\(n\leq 10^3\)

明显可以在ac自动机上dp 算是常规，限制n就不说了。

难题在于怎么处理前导0

考虑先把\(\leq n-1\)位的时候的\(ans\)算出来，这样就不存在前导0的问题了

具体来说就是前导0的位填上也不会被统计。

最后加上\(n\)位时候的答案就好了

#include<cstdio>
#include<cstring>
#include<queue>
const int mo = 1e9 + 7;
const int N = 1e3 + 5e2 + 7;
typedef long long ll;
inline ll max(ll a, ll b) {return a > b ? a : b;}
struct trie {int fail, end, sum, son[10];} t[N];
int pcnt = 0;

inline void ins() {
  char qs[N]; scanf ("%s", qs);
  int lens = strlen(qs), p = 0; //printf ("%d", lens);
  for (int i = 0; i < lens; i++) {
    if (!t[p].son[qs[i] - 48]) t[p].son[qs[i] - 48] = ++pcnt;
    p = t[p].son[qs[i] - 48];
  } t[p].end = 1;
}
inline void getfail() {
  std :: queue<int> q;
  for (int i = 0; i < 10; i++) if (t[0].son[i]) 
    q.push(t[0].son[i]), t[t[0].son[i]].fail = 0;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    //printf ("%d ", t[1].fail);
    for (int i = 0; i < 10; i++) {
      if (t[u].son[i]) 
        t[t[u].son[i]].fail = t[t[u].fail].son[i], q.push(t[u].son[i]);
      else t[u].son[i] = t[t[u].fail].son[i];
    } t[u].end |= t[t[u].fail].end; 
  }
} int m;
int g[N][N], f[N][N][2];char s[N];ll ans = 0; char ss[N];
int main() {
  scanf ("%s", s); scanf ("%d", &m);int up = strlen(s);
  while (m--) ins(); g[0][0] = 1; getfail();
  for (int i = 1; i <= up; i++) ss[i] = s[i - 1];
  int lens = up; //printf ("%d", pcnt);
  for (int i = 0; i < up; i++)
    for (int u = 0; u <= pcnt; u++) if (!t[u].end)
      for (int p = 0; p < 10; p++) if (!t[t[u].son[p]].end) {
        if (!i && !p) continue;
       // printf ("xxx");
        g[i + 1][t[u].son[p]] += g[i][u], g[i + 1][t[u].son[p]] %= mo;
      }
  for (int i = 1; i < lens; i++) 
    for (int j = 0; j <= pcnt; j++) ans = (ans + g[i][j]) % mo;
  f[0][0][1] = 1;// printf ("%lld\n", ans);
  for (int i = 0; i < lens; i++) 
    for (int u = 0; u <= pcnt; u++) if (!t[u].end)
      for (int p = 0; p < 10; p++) if (!t[t[u].son[p]].end) {
        if (!i && !p) continue;
        f[i + 1][t[u].son[p]][0] = (f[i + 1][t[u].son[p]][0] + f[i][u][0]) % mo;
        if (p < ss[i + 1] - '0') 
          f[i + 1][t[u].son[p]][0] = (f[i + 1][t[u].son[p]][0] + f[i][u][1]) % mo;
        if (p == ss[i + 1] - '0')
          f[i + 1][t[u].son[p]][1] = (f[i + 1][t[u].son[p]][1] + f[i][u][1]) % mo;
      }
  for(int i = 0; i <= pcnt; ++i)
    ans = (ans + f[lens][i][0]) % mo, ans = (ans + f[lens][i][1]) % mo;
  printf ("%lld\n", ans);
}

BZOJ 3530 数数

原文：https://www.cnblogs.com/cjc030205/p/11638082.html