[BZOJ 3530][Sdoi 2014]数数

阿拉~好像最近总是做到 AC 自动机的题目呢喵~

题目的算法似乎马上就能猜到的样子…… AC 自动机 + 数位 dp

先暴力转移出 f[i][j] ：表示从 AC 自动机上第 j 号节点走 i 步且不碰到匹配串的方案数

然后直接用数位 dp 一位一位的试就可以了，大家都会吧~

但是…… 有前导 0 的情况真尼玛蛋疼啊！

忽的灵光一闪……

前导 0 仅能影响长度小于 L 的数的统计

那么所有长度 <L 的数全部专门暴力统计一边不就可以了！我真是特么太机智了喵~ O(∩_∩)O~

虽然有个 O(10*L*l) 的转移但是只跑了 272 ms 呢

  1 #include <cstdio>
  2 #include <cstring>
  3 #define ord(ch) ((ch)-'0')
  4 const int sizeOfLength=1201;
  5 const int sizeOfNumber=1501;
  6 const int sizeOfType=10;
  7 const int mod=1000000007;
  8 
  9 struct node
 10 {
 11     int idx;
 12     bool end;
 13     node * fail, * ch[sizeOfType];
 14 };
 15 node * dfa;
 16 node memory[sizeOfNumber], * port=memory;
 17 inline node * newnode();
 18 inline void insert(char * , int);
 19 node * q[sizeOfNumber]; int l, r;
 20 inline void build();
 21 inline void dynamicprogramming();
 22 
 23 char N[sizeOfLength]; int L;
 24 int M;
 25 int f[sizeOfLength][sizeOfNumber];
 26 char s[sizeOfNumber]; int len;
 27 inline int getint();
 28 inline int getstr(char * );
 29 inline void putint(int);
 30 
 31 int main()
 32 {
 33     int ans=0;
 34     bool find=true;
 35     node * t;
 36 
 37     L=getstr(N);
 38     M=getint();
 39     dfa=newnode();
 40     for (int i=1;i<=M;i++)
 41     {
 42         len=getstr(s);
 43         insert(s, len);
 44     }
 45     build();
 46     dynamicprogramming();
 47 
 48     t=dfa;
 49     for (int i=0;i<L;i++)
 50     {
 51         for (int j=(i==0);j<ord(N[i]);j++) if (!t->ch[j]->end)
 52             ans=(ans+f[L-i-1][t->ch[j]->idx])%mod;
 53         t=t->ch[ord(N[i])];
 54         if (t->end)
 55         {
 56             find=false;
 57             break;
 58         }
 59     }
 60     for (int i=L-2;i>=0;i--)
 61         for (int j=1;j<=9;j++)
 62             ans=(ans+f[i][dfa->ch[j]->idx])%mod;
 63 
 64     putint(ans+find);
 65 
 66     return 0;
 67 }
 68 inline int getint()
 69 {
 70     register int num=0;
 71     register char ch;
 72     do ch=getchar(); while (ch<'0' || ch>'9');
 73     do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
 74     return num;
 75 }
 76 inline int getstr(char * str)
 77 {
 78     register int len=0;
 79     register char ch;
 80     do ch=getchar(); while (ch<'0' || ch>'9');
 81     do str[len++]=ch, ch=getchar(); while (ch>='0' && ch<='9');
 82     return len;
 83 }
 84 inline void putint(int num)
 85 {
 86     char stack[11];
 87     register int top=0;
 88     for ( ;num;num/=10) stack[++top]=num%10+'0';
 89     for ( ;top;top--) putchar(stack[top]);
 90     putchar('\n');
 91 }
 92 inline node * newnode()
 93 {
 94     node * ret=port++;
 95     ret->idx=port-memory-1;
 96     ret->fail=NULL;
 97     memset(ret->ch, 0, sizeof ret->ch);
 98     return ret;
 99 }
100 inline void insert(char * s, int l)
101 {
102     node * t=dfa;
103     for (int i=0;i<l;i++)
104     {
105         if (!t->ch[ord(s[i])]) t->ch[ord(s[i])]=newnode();
106         t=t->ch[ord(s[i])];
107     }
108     t->end=true;
109 }
110 inline void build()
111 {
112     dfa->fail=dfa;
113     for (int i=0;i<sizeOfType;i++)
114         if (dfa->ch[i])
115         {
116             dfa->ch[i]->fail=dfa;
117             q[r++]=dfa->ch[i];
118         }
119         else
120             dfa->ch[i]=dfa;
121     for ( ;l<r;l++)
122     {
123         node * u=q[l];
124         u->end|=u->fail->end;
125         for (int i=0;i<sizeOfType;i++)
126             if (u->ch[i])
127             {
128                 u->ch[i]->fail=u->fail->ch[i];
129                 q[r++]=u->ch[i];
130             }
131             else
132                 u->ch[i]=u->fail->ch[i];
133     }
134 }
135 inline void dynamicprogramming()
136 {
137     int tot=port-memory;
138     for (int i=0;i<tot;i++)
139         if (!(dfa+i)->end)
140             f[0][(dfa+i)->idx]=1;
141     for (int i=1;i<=L;i++)
142         for (int j=0;j<tot;j++) if (!(dfa+j)->end)
143             for (int k=0;k<sizeOfType;k++)
144                 f[i][(dfa+j)->idx]=(f[i][(dfa+j)->idx]+f[i-1][(dfa+j)->ch[k]->idx])%mod;
145 }

机房不卡代码插入了好评如潮

秒客网

[BZOJ 3530][Sdoi 2014]数数

相关文章