超级神奇有趣题。

AC自动机+数位DP。其实，数位DP在处理含有某些数字时特别不好处理，应该把它倒转为求不含有。这道题把数位DP+AC自动机结合起来，实在是很巧妙，把数字变为串来处理，强大！

要使用AC自动机来处理数位DP，首先就是要确定哪些状态由当前状态开始是不可以到达的，有哪些是可以到达的。这是显而易见的，因为既然是数位DP，必定涉及到数字的问题，每改变一个数字就会到达自动机上的一个状态，确定哪些状态可达或不可达是很有必要的。这就要求要构建trie图了。

其次就是DFS了，在进行DFS深搜前，要确定当前状态变更一个数字后的状态是否可达，再进行转移。

在这题，要处理前导0的问题，因为0000（十进制）里，其实只代表一个0，但可能会出现禁止状态（如二进制连续五个0违法，但四个0不违法）。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #define LL long long  6 using namespace std;  7 const LL MOD=1000000009;  8 const int root=0;  9 int trie[2010][2],tot,bit[210]; 10 int next[2010][10],fail[2010]; 11 bool tag[2010]; 12 char str[210]; 13 LL dp[210][2010]; 14 int que[2010],head,tail; 15  16 void clr(int now){ 17     trie[now][0]=trie[now][1]=-1; 18 } 19  20 void insert(){ 21     int p=root,i=0,len=strlen(str); 22     while(i++
          
           =len-i;i--){ 77         tmp=str[i]; 78         str[i]=str[len-i]; 79         str[len-i]=tmp; 80     } 81 } 82  83 int cal_next(int p,int j){ 84     if(tag[p]) return -1; 85     for(int k=3;k>=0;k--){ 86         p=trie[p][(j>>k)&1]; 87         if(tag[p]) return -1; 88     } 89     return p; 90 } 91  92 void Calculation(){ 93     for(int i=0;i<=tot;i++){ 94         for(int j=0;j<=9;j++){ 95             next[i][j]=cal_next(i,j); 96         } 97     } 98 } 99 100 LL dfs(int len,int j,bool limit,bool z){101     if(len==-1) return 1LL;102     if(!limit&&dp[len][j]!=-1) return dp[len][j];103     int up=limit?bit[len]:9;104     LL ans=0;105     if(z&&len>0){106         ans+=dfs(len-1,j,limit&&up==0,true);107     }108     else{109         if(next[j][0]!=-1&&!tag[next[j][0]])110         ans+=dfs(len-1,next[j][0],limit&&up==0,false);111     }112     for(int i=1;i<=up;i++){113         if(next[j][i]!=-1&&!tag[next[j][i]]){114             ans+=dfs(len-1,next[j][i],limit&&i==up,false);115         }116     }117     ans%=MOD;118     if(!limit) dp[len][j]=ans;119     return ans;120 }121 122 LL slove(){123     int len=strlen(str);124     len--;125     for(int i=len;i>=0;i--)126     bit[i]=str[i]-'0';127     return dfs(len,0,true,true);128 }129 130 int main(){131     int T,n,len;132     scanf("%d",&T);133     while(T--){134         memset(tag,false,sizeof(tag));135         memset(dp,-1,sizeof(dp));136         memset(fail,-1,sizeof(fail));137         scanf("%d",&n);138         tot=0;139         clr(root);140         for(int i=0;i