解題區/解題區 - UVa

UVa 12040 - Again Lucky Numbers

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem

Some people believe that 13 is an unlucky number. So they always want to avoid the number 13. But I believe that 7 is an unlucky number and want to avoid it. So unlucky number is different for man to man. If 13 is an unlucky number and in a number there is no 13 (i.e. no ‘1’ is followed by a ‘3’) then we can call it a lucky number. For example, if we consider 13 as an unlucky number then 12345 is a lucky number. But if any number contains 13 then it is not a lucky number, such as 13254 and 21345 are not lucky numbers. Given the number of digits N in a number and the unlucky number M, you have to find out how many lucky numbers are possible with N digits considering that M is unlucky number. Note that leading 0’s are not allowed. So, 011 is not a valid three digit number.

Input

The first line of the input file contains an integer T (T ≤ 1000) which denotes the total number of test cases. The description of each test case is given below:

Two positive integers N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 10100).

Output

For each test case print the number of lucky numbers of N digits considering that M is the unlucky number. The result may be very large. You have to output the result modulo 10000007.

Sample Input

1
2
3
4
3
1 3
2 13
2 1

Sample Output

1
2
3
9
89
72

Solution

題目描述：

找到長度為 n 的數字，並且數字中不會出現指定的數字為 substring，求符合數字的總數。

題目解法：

特別考慮以 0 開頭的情況 (n 位數字前導不可為 0，但 n = 1 位數字可以是 0)。
最後，建造一台 AC 自動機，接著對於每一個節點著手 dp 轉移。

也就是考慮再將字串進行 AC 自動機匹配時所會遇到的所有轉移情況，因此我們要避免出現指定的字符串時，在結尾處標記不可轉移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// http://mypaper.pchome.com.tw/zerojudge/post/1324462879
// AC 自動機 DP
#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
struct Node {
    Node *next[10], *fail, *prev;
    int eos;//prefix has a string end
    long long dp[105]; // [string length]
    int ASCII;
    Node() {
        fail = NULL, prev = NULL;
        memset(next, 0, sizeof(next));
        memset(dp, 0, sizeof(dp));
        eos = 0;
        ASCII = 0;
    }
};
void insertTrie(const char str[], Node *root, int label) {
    static Node *p;
    static int i, idx, eos;
    p = root, eos = 0;
    for(i = 0; str[i]; i++) {
        idx = str[i] - '0';
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
            p->next[idx]->prev = p;
            p->next[idx]->ASCII = idx;
        }
        eos |= p->eos;
        p = p->next[idx];
        p->eos |= eos;
    }
    p->eos |= label;
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
        delete nd;
    }
}
void buildACautomation(Node *root) {
    queue<Node*> Q;
    Node *nd, *p;
    root->fail = NULL;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] == NULL)
                continue;
            Q.push(nd->next[i]);
            p = nd->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                nd->next[i]->fail = root;
            else {
                nd->next[i]->fail = p->next[i];
                nd->next[i]->eos |= p->next[i]->eos;//special for dp
            }
        }
    }
}
const int mod = 10000007;
long long dp(Node *root, int len) {
    queue<Node*> Q;
    Node *nd, *p;
    root->dp[0] = 1;
    int k, i, j;
    long long ans, ret = 0;
    for(k = 0; k <= len; k++) {
        Q.push(root);
        ans = 0;
        while(!Q.empty()) {
            nd = Q.front(), Q.pop();
            for(i = (k == 0); i < 10; i++) { // leading 0's are not allowed
                if(nd->next[i] != NULL) {
                    if(nd->next[i]->eos)
                        continue;//not safe
                    nd->next[i]->dp[k+1] += nd->dp[k];
                    nd->next[i]->dp[k+1] %= mod;
                    Q.push(nd->next[i]);
                } else {
                    p = nd;
                    while(p != root && p->next[i] == NULL)
                        p = p->fail;
                    p = p->next[i];
                    if(p == NULL) // error message
                        puts("NULL");
                    if(p->eos)
                        continue;//not safe
                    p->dp[k+1] += nd->dp[k];
                    p->dp[k+1] %= mod;
                }
            }
            ans += nd->dp[k];
            ans %= mod;
        }
        if(k == len) {
            ret += ans;
            ret %= mod;
        }
    }
    return ret;
}
int main() {
    int n, p, i;
    int cases = 0, testcase;
    char pattern[105], s[105];
    scanf("%d", &testcase);
    while(testcase--) {
        Node *root = new Node();
        scanf("%d %s", &n, pattern);
        insertTrie(pattern, root, 1);
        for(int i = 0; i < 10; i++) {
        	s[0] = i + '0', s[1] = '\0';
        	insertTrie(s, root, 0);
        }
        buildACautomation(root);
        long long ret = dp(root, n);
        freeTrie(root);
        if(n == 1 && strcmp("0", pattern))
        	ret++;
        printf("%lld\n", ret);
    }
    return 0;
}
/*
3
1 3
2 13
2 1
*/