[CodeForces-585F]Digits of Number Pi

题目大意：
　　给你一个数字串s，一个序列范围l和r，（l和r的数字位数为d）求l到r中有多少个数，满足它的长度为d/2的子串，能够在s中被匹配。

思路：
　　首先将s中每一个长度为d/2的子串插入后缀自动机。
　　然后数位DP。
　　f[i][j]中第一维表示当前树与l和r的关系，包含四个状态，用二进制表示，每一位对应与l和r的不同关系。
　　第二维表示当前状态下每个结点匹配到的数的个数。
　　每一个数位的状态由上一个数位转移而来，我们用两个DP数组f和g滚动实现。
　　用o表示当前枚举的数字，用to表示数字所对应的第一维的状态，则转移方程为f[to[o]][p]=sum(f[j][par[p]])
　　然而一开始写AC自动机用的是指针，然后又是各种不方便，所以又用vector很粗糙地实现了结点的遍历。故常数巨大。

  1 #pragma GCC optimize("O3") 
  2 #include<queue>
  3 #include<cstdio>
  4 #include<vector>
  5 #include<cstring>
  6 const int mod=1e9+7;
  7 const int N=1001,D=51;
  8 char s[N],l[D],r[D];
  9 int n,d;
 10 class AhoCorasickAutomaton {
 11     private:
 12         static const int SIGMA_SIZE=10;
 13         struct Node {
 14             Node *ch[SIGMA_SIZE],*fail;
 15             bool isEnd;
 16             int id;
 17             Node(const int i) {
 18                 memset(ch,0,sizeof ch);
 19                 fail=NULL;
 20                 isEnd=false;
 21                 id=i;
 22             }
 23         };
 24         Node *root;
 25         std::vector<Node*> v; 
 26         int idx(const char ch) {
 27             return ch-'0';
 28         }
 29         int f[4][N*D>>1],g[4][N*D>>1];
 30         //第一维表示与l和r的关系
 31     public:
 32         AhoCorasickAutomaton() {
 33             root=new Node(v.size());
 34             v.push_back(root);
 35         }
 36         void insert(char s[],const int len) {
 37             Node *p=root;
 38             for(int i=0;i<len;i++) {
 39                 const int w=idx(s[i]);
 40                 if(!p->ch[w]) {
 41                     p->ch[w]=new Node(v.size());
 42                     v.push_back(p->ch[w]);
 43                 }
 44                 p=p->ch[w];
 45             }
 46             p->isEnd=true;
 47         }
 48         void getFail() {
 49             std::queue<Node*> q;
 50             root->fail=root;
 51             for(int i=0;i<SIGMA_SIZE;i++) {
 52                 if(root->ch[i]) {
 53                     root->ch[i]->fail=root;
 54                     q.push(root->ch[i]);
 55                 } else {
 56                     root->ch[i]=root;
 57                 }
 58             }
 59             while(!q.empty()) {
 60                 Node *p=q.front();
 61                 q.pop();
 62                 for(int i=0;i<SIGMA_SIZE;i++) {
 63                     if(p->ch[i]) {
 64                         p->ch[i]->fail=p->fail->ch[i];
 65                         q.push(p->ch[i]);
 66                     } else {
 67                         p->ch[i]=p->fail->ch[i];
 68                     }
 69                 }
 70             }
 71             Node *end=new Node(v.size());
 72             for(unsigned i=0;i<v.size();i++) {
 73                 Node *p=v[i];
 74                 for(int i=0;i<SIGMA_SIZE;i++) {
 75                     if(p->ch[i]->isEnd) {
 76                         p->ch[i]=end;
 77                     }
 78                 }
 79             }
 80             for(int i=0;i<SIGMA_SIZE;i++) {
 81                 end->ch[i]=end;
 82             }
 83             v.push_back(end);
 84         }
 85         int dp() {
 86             g[0][0]=1;
 87             int to[10];
 88             for(int i=0;i<d;i++) {
 89                 for(int i=0;i<4;i++) {
 90                     for(unsigned j=0;j<v.size();j++) {
 91                         f[i][j]=0;
 92                     }
 93                 }
 94                 for(int j=0;j<4;j++) {
 95                     int st=(j&1)?0:idx(l[i]),en=(j>1)?9:idx(r[i]);//确定当前数位数字的上下界 
 96                     for(int i=st;i<=en;i++) to[i]=0b11;//默认是在l和r之间 
 97                     if(~j&1) to[st]&=0b10;//如果比l小 
 98                     if(j<2) to[en]&=0b01;//如果比r大
 99                     //用&是因为有可能st=en 
100                     for(unsigned k=0;k<v.size();k++) {
101                         if(!g[j][k]) continue;
102                         for(int o=st;o<=en;o++) {//在当前数位的范围寻找子结点 
103                             (f[to[o]][v[k]->ch[o]->id]+=g[j][k])%=mod;
104                         }
105                     }
106                 }
107                 std::swap(f,g);
108             }
109             int ret=0;
110             for(int i=0;i<4;i++) {
111                 ret=(ret+g[i][v.size()-1])%mod;
112             }
113             return ret;
114         }
115 };
116 AhoCorasickAutomaton acam;
117 int main() {
118     scanf("%s%s%s",s,l,r);
119     n=strlen(s),d=strlen(l);
120     for(int i=0;i<=n-d/2;i++) {
121         acam.insert(&s[i],d/2);
122     }
123     acam.getFail();
124     printf("%d
",acam.dp());
125     return 0;
126 }