首页 > 代码库 > [BZOJ3530][Sdoi2014]数数

[BZOJ3530][Sdoi2014]数数

2024-08-02 20:02:41   218人阅读

阿拉~好像最近总是做到 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         else120             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             else132                 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 }
机房不卡代码插入了 好评如潮

 

[BZOJ3530][Sdoi2014]数数


联系
我们