题意：

　　将一个整数表示成4个bit的bcd码就成了一个01串，如果该串中出现了部分病毒串，则是危险的。给出n个病毒串（n<=100,长度<21），问区间[L,R]中有几个数字是不含病毒串的（结果需要取模）？（0<L<=R<=10²⁰⁰）

 

思路：

　　区间非常大，怎样暴力统计都是不科学的。首先确定状态，按传统，一维必定是位数，二维就是压缩的状态了，如果长度为20个bit的话，200*104万的数组是不行的。类似多模式串匹配问题，病毒串可以构建成AC自动机，那么每个点可以代表一个独立状态，而n<=100，所以最多20n个节点，是可以的。转移的话可以根据新考虑的数位是多少，然后在AC自动机上面走4步（BCD码是4bit）到达另一个状态（点），如果经过了病毒串的末尾节点，表示该数出现病毒串，就不能转移。这个可以在AC自动机创建完成后，预处理出来就行了。而对于每个询问[L,R]，L仍然是需要减1的，大数减1比较简单。注意点是，AC自动机上的tag需要特殊处理，如果有病毒串"asdf"和串"sd"，而碰到原串为"asdd"，别忘了还有"sd"。这只需要在构建fail指针的时候处理一下。

 

 

 

 

 

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           

que; 46 for(int i=0; i

0? 0: 1; //起 86 int u= e? bit[i]-'0': 9;//终 87 for(; d<=u; d++) 88 { 89 if(bcd[s][d]!=-1) 90 { 91 ans+=dfs(i-1, bcd[s][d], sum+d, e&&d==u); 92 ans%=mod; 93 } 94 } 95 if(!e&&sum) f[i][s]=ans; //没有前导零 96 return ans; 97 } 98 99 100 LL cal()101 {102 reverse(bit+1, bit+len+1);103 if(len==1&&bit[len]=='0') return 1;104 return dfs(len, 0, 0, true);105 }106 107 int changeto(int s,int t)108 {109 if(AC.tag[s]) return -1; //已经是病毒串110 int now=s;111 for(int i=3; i>=0; i--)112 {113 if( AC.tag[AC.next[now][(t>>i)&1]]==1 ) return -1; //病毒串114 now=AC.next[now][(t>>i)&1];115 }116 return now;117 }118 void pre_cal() //预处理转移119 {120 for(int i=0; i

>t;128 LL ans[2];129 while( t-- )130 {131 memset(bcd, -1, sizeof(bcd));132 memset(f, -1, sizeof(f));133 AC.init();134 scanf("%d",&n);135 for(int i=0; i

0; i--) //注意逆序150 {151 if( bit[i]>'0' ){bit[i]--;break;}152 else bit[i]='9';153 }154 }155 ans[j]=cal();156 }157 printf("%lld\n",(ans[1]+mod-ans[0])%mod);158 }159 return 0;160 }