HDU 5351 – MZL’s Border [找规律]

Problem Description

As is known to all, MZL is an extraordinarily lovely girl. One day, MZL was playing with her favorite data structure, strings.
MZL is really like Fibonacci Sequence, so she defines Fibonacci Strings in the similar way. The definition of Fibonacci Strings is given below.
1) fib1=b
2) fib2=a
3) fibi=fibi1fibi2, i>2
For instance, fib3=ab, fib4=aba, fib5=abaab.
Assume that a string s whose length is n is s1s2s3...sn. Then sisi+1si+2si+3...sj is called as a substring of s, which is written as s[i:j].
Assume that i<n. If s[1:i]=s[ni+1:n], then s[1:i] is called as a Border of s. In Borders of s, the longest Border is called as sLBorder. Moreover, s[1:i]‘s LBorder is called as LBorderi.
Now you are given 2 numbers n and m. MZL wonders what LBorderm of fibn is. For the number can be very big, you should just output the number modulo 258280327(=2×317+1).
Note that 1T100, 1n103, 1m|fibn|.

Input

The first line of the input is a number T, which means the number of test cases.
Then for the following T lines, each has two positive integers n and m, whose meanings are described in the description.

Output

The output consists of T lines. Each has one number, meaning fibn‘s LBorderm modulo 258280327(=2×317+1).
分析:先打表,然后发现一种奇妙的规律,类似于斐波那契数列的规律,打表还是用python快+爽啊。然后输入和计算需要用到大整数,建议使用java做题。需要注意的是这道题后面n很大会无限长,但是他们的前缀都是相同的,所以相当于直接在最大的n上进行查询,即输出的结果与n无关,只看m即可。
下面是python的打表程序:
s1, s2 = 'a', 'b'
for i in range(3, 15):
    s1, s2 = s2, s2+s1

print(s2)
print(len(s2))

for n in range(3, 200):
    print(n, ":", end=' ')
    for l in range(n-1, 0, -1):
        if s2[0:l] == s2[n-l:n]:
            print(l)
            break

运行的结果是:
babbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabab
377
3 : 1
4 : 1
5 : 2
6 : 3
7 : 2
8 : 3
9 : 4
10 : 5
11 : 6
12 : 4
13 : 5
14 : 6
15 : 7
16 : 8
17 : 9
18 : 10
19 : 11
20 : 7
21 : 8
22 : 9
23 : 10
24 : 11
25 : 12
26 : 13
27 : 14
28 : 15
29 : 16
30 : 17
31 : 18
32 : 19
33 : 12
34 : 13
35 : 14
36 : 15
37 : 16
38 : 17
39 : 18
40 : 19
41 : 20
42 : 21
43 : 22
44 : 23
45 : 24
46 : 25
47 : 26
48 : 27
49 : 28
50 : 29
51 : 30
52 : 31
53 : 32
54 : 20
55 : 21
56 : 22
57 : 23
58 : 24
59 : 25
60 : 26
61 : 27
62 : 28
63 : 29
64 : 30
65 : 31
66 : 32
67 : 33
68 : 34
69 : 35
70 : 36
71 : 37
72 : 38
73 : 39
74 : 40
75 : 41
76 : 42
77 : 43
78 : 44
79 : 45
80 : 46
81 : 47
82 : 48
83 : 49
84 : 50
85 : 51
86 : 52
87 : 53
88 : 33
89 : 34
90 : 35
91 : 36
92 : 37
93 : 38
94 : 39
95 : 40
96 : 41
97 : 42
98 : 43
99 : 44
100 : 45
101 : 46
102 : 47
103 : 48
104 : 49
105 : 50
106 : 51
107 : 52
108 : 53
109 : 54
110 : 55
111 : 56
112 : 57
113 : 58
114 : 59
115 : 60
116 : 61
117 : 62
118 : 63
119 : 64
120 : 65
121 : 66
122 : 67
123 : 68
124 : 69
125 : 70
126 : 71
127 : 72
128 : 73
129 : 74
130 : 75
131 : 76
132 : 77
133 : 78
134 : 79
135 : 80
136 : 81
137 : 82
138 : 83
139 : 84
140 : 85
141 : 86
142 : 87
143 : 54
144 : 55
145 : 56
146 : 57
147 : 58
148 : 59
149 : 60
150 : 61
151 : 62
152 : 63
153 : 64
154 : 65
155 : 66
156 : 67
157 : 68
158 : 69
159 : 70
160 : 71
161 : 72
162 : 73
163 : 74
164 : 75
165 : 76
166 : 77
167 : 78
168 : 79
169 : 80
170 : 81
171 : 82
172 : 83
173 : 84
174 : 85
175 : 86
176 : 87
177 : 88
178 : 89
179 : 90
180 : 91
181 : 92
182 : 93
183 : 94
184 : 95
185 : 96
186 : 97
187 : 98
188 : 99
189 : 100
190 : 101
191 : 102
192 : 103
193 : 104
194 : 105
195 : 106
196 : 107
197 : 108
198 : 109
199 : 110
上面是对于每个m对应的答案。
仔细查看上面的表,就会发现一些规律,即不断地顺序递增,每次递增的上下范围,列出表格来是一种类似于斐波那契的东西。
Java程序如下:

import java.math.BigInteger;
import java.util.Scanner;


public class Main {
    static BigInteger b[] = new BigInteger[1024];
    static BigInteger a[] = new BigInteger[1024];

    public static void init() {
        b[1] = BigInteger.valueOf(3); b[2] = BigInteger.valueOf(6);
        for(int i = 3; i < 1024; ++i)
            b[i] = b[i-1].add(b[i-2]).add(BigInteger.valueOf(2));
        a[1] = BigInteger.valueOf(1); a[2] = BigInteger.valueOf(2);
        for(int i = 3; i < 1024; ++i)
            a[i] = a[i-1].add(a[i-2]).add(BigInteger.ONE);
    }

    public static void main(String[] args) {
        init();
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        for(int t = 0; t < T; ++t) {
            int n = cin.nextInt();
            BigInteger m = cin.nextBigInteger();
            if(m.compareTo(BigInteger.valueOf(4)) == -1) {
                int mm = m.intValue();
                if(mm == 1) System.out.println(0);
                else if(mm == 2) System.out.println(0);
                else if(mm == 3) System.out.println(1);
                else if(mm == 4) System.out.println(1);
            } else {
                m = m.subtract(BigInteger.valueOf(4));
                for(int i = 1; i < 1020; ++i) {
                    BigInteger len = b[i].subtract(a[i]).add(BigInteger.ONE);
                    if(m.compareTo(len) == -1) {
                        System.out.println(a[i].add(m).mod(BigInteger.valueOf(258280327)));
                        break;
                    }
                    m = m.subtract(len);
                }
            }
        }
    }
}

欢迎留言