SCNU 2013校赛 Choose a password（AC自动机、矩阵递推）

Problem Description

BandBandRock is quite sensitive with numbers (a number is defined as a sequence formed by
‘0’-‘9’). He thinks this list of lucky numbers can bring him luck (for example his lucky list could
be 9, 13) and he loves these numbers very much!
One day, BandBandRock is choosing a password for his bank account (a password is a sequence
formed by ‘0’-‘9’). He always forms his password with at least one of those lucky numbers as
substrings. For example, if the passwords length is set as 3, 913and 113 are both available options
but 123 is not.
After choosing a password, BandBandRock is worrying about the security of his account. If
a hacker realizes his habit and know his number list, he might make some guess and find out
BandBandRock’s password!
In order to evaluate how secure his account is, BandBandRock wants to know the amount of
possibilities of his password.
For example, if the password can be 2 digits at most, therere 21 possibilities as follow:
(1 possibility) 9
(10 possibilities) 90, 92 . . . 99
(9 possibilities) 09, 19 . . . 89
(1 possibility) 13

Input

The input consists of multiple cases, and there’re less than 100 cases.
Each case begins with the number n (0 < n < 6), and the length of password L
(0 < L < 1, 000, 000, 000). Then following n lines will be the lucky numbers, each per line.
Its guarantee that the length of every number wont exceed 5. Every number will be different from
the others.
Theres always a blank line after each input case.

Output

For each case, you should output the answer in a line, which means the amount of the possibility.
As the answer may be so large, you should output the answer mod 1000000007.

Sample Input

2 2 9 13

Sample Output

题目大意：给n个幸运数字，问长度≤L的数字串中，包含幸运数字的数字串有多少个。

思路：先算出长度为L的数字串的总数，然后减去不含有幸运数字的数字串总数

由于L过大，可使用矩阵+快速幂协助递推，或用公式，公式要用到乘法逆，111111112就是9对模1000000007的逆

利用AC自动机，记录某一个状态到下一个状态的数量，做出一个二维的DP递推矩阵

然后用矩阵+快速幂进行递推

  1 #include <cstdio>  
  2 #include <cstring>  
  3 #include <queue>  
  4 #define MAXN 50  
  5 #define MOD(x) ((x)%1000000007)  
  6 #define LL long long  
  7 using namespace std;  
  8      
  9 int ecnt;  
 10      
 11 void gcd(LL a, LL b, LL &d, LL &x, LL & y){  
 12     if(!b) {d = a; x = 1; y = 0;}  
 13     else {gcd(b, a%b, d, y, x); y -= x*(a/b);}  
 14 }  
 15      
 16 LL inv(LL a, LL n){  
 17     LL d, x, y;  
 18     gcd(a, n, d, x, y);  
 19     return d == 1 ? (x+n)%n : -1;  
 20 }  
 21      
 22 struct Mat{  
 23     LL mat[MAXN][MAXN];  
 24     Mat operator * (const Mat &a) const{  
 25         Mat c;  
 26         for(int i = 0; i < ecnt; ++i)  
 27             for(int j = 0; j < ecnt; ++j){  
 28                 c.mat[i][j] = 0;  
 29                 for(int k = 0; k < ecnt; ++k)  
 30                     c.mat[i][j] = MOD(c.mat[i][j] + MOD(a.mat[i][k] * mat[k][j]));  
 31             }  
 32         return c;  
 33     }  
 34     void clear() {memset(mat,0,sizeof(mat));}  
 35     void E(){  
 36         clear();  
 37         for(int i = 0; i < ecnt; ++i) mat[i][i] = 1;  
 38     }  
 39 } dp;  
 40      
 41 Mat mul(Mat &dp, int k){  
 42     Mat p = dp, ans; ans.E();  
 43     while(k){  
 44         if(k&1) ans = ans * p;  
 45         p = p * p;  
 46         k >>= 1;  
 47     }  
 48     return ans;  
 49 }  
 50      
 51 LL mul(LL x, LL k){  
 52     LL p = x, ans = 1;  
 53     while(k){  
 54         if(k&1) ans = MOD(ans * p);  
 55         p = MOD(p * p);  
 56         k >>= 1;  
 57     }  
 58     return ans;  
 59 }  
 60      
 61 struct Node{  
 62     Node *fail, *next[10];  
 63     bool flag;  
 64     int ord;  
 65     Node(int t){  
 66         memset(next,0,sizeof(next));  
 67         flag = 0; fail = 0; ord = t;  
 68     }  
 69 };  
 70      
 71 void buildTrie(Node *root, char *str){  
 72     Node *p = root;  
 73     for(int i = 0; str[i]; ++i){  
 74         int index = str[i] - '0';  
 75         if(!p->next[index]) p->next[index] = new Node(ecnt++);  
 76         p = p->next[index];  
 77     }  
 78     p->flag = true;  
 79 }  
 80      
 81 void makeFair(Node *root){  
 82     queue<Node*> que; que.push(root);  
 83     while(!que.empty()){  
 84         Node *tmp = que.front(); que.pop();  
 85         for(int i = 0; i < 10; ++i){  
 86             if(!tmp->next[i]) continue;  
 87             if(tmp == root) tmp->next[i]->fail = root;  
 88             else{  
 89                 Node *p = tmp->fail;  
 90                 while(p){  
 91                     if(p->next[i]){  
 92                         tmp->next[i]->fail = p->next[i];  
 93                         break;  
 94                     }  
 95                     p = p->fail;  
 96                 }  
 97                 if(!p) tmp->next[i]->fail = root;  
 98             }  
 99             if(tmp->next[i]->fail->flag) tmp->next[i]->flag = true;  
100             else que.push(tmp->next[i]);  
101         }  
102     }  
103     root->fail = root;  
104 }  
105      
106 void makeDp(Node *root){  
107     queue<Node*> que; que.push(root);  
108     while(!que.empty()){  
109         Node *tmp = que.front(); que.pop();  
110         for(int i = 0; i < 10; ++i){  
111             if(tmp->next[i]){  
112                 if(tmp->next[i]->flag) continue;  
113                 dp.mat[tmp->next[i]->ord][tmp->ord]++;  
114                 que.push(tmp->next[i]);  
115                 continue;  
116             }  
117             Node *p = tmp->fail;  
118             while(!p->next[i] && p != root) p = p->fail;  
119             if(p->next[i] && p->next[i]->flag) continue;  
120             if(!p->next[i]) dp.mat[root->ord][tmp->ord]++;  
121             else dp.mat[p->next[i]->ord][tmp->ord]++;  
122         }  
123     }  
124     for(int i = 0; i < ecnt; ++i) dp.mat[ecnt-1][i] = 1;  
125 }  
126      
127 int main()  
128 {  
129     int n, L;  
130     LL sum;  
131     char str[8];  
132     while(scanf("%d%d",&n,&L)!=EOF){  
133         Node *root = new Node(0);  
134         ecnt = 1;  
135         while(n--){  
136             scanf("%s",str);  
137             buildTrie(root, str);  
138         }  
139         ecnt++;  
140         makeFair(root);  
141         dp.clear();  
142         makeDp(root);  
143         dp = mul(dp, L+1);  
144         sum = MOD(MOD(mul(10, L+1) - 10 + 1000000007) * (LL)111111112);  
145         printf("%I64d\n",MOD(sum - dp.mat[ecnt-1][0] + 1 + 1000000007));  
146     }  
147     return 0;  
148 }

View Code