转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud
MZL's Border
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 905 Accepted Submission(s): 295
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=fibi−1fibi−2, 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[n−i+1:n], then s[1:i] is called as a Border of s. In Borders of s, the longest Border is called as s' LBorder. 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 1≤T≤100, 1≤n≤103, 1≤m≤|fibn|.
Then for the following T lines, each has two positive integers n and m, whose meanings are described in the description.
4 3
5 5
2
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream; /**
* Built using CHelper plug-in
* Actual solution is at the top
*
* @author xyiyy@www.cnblogs.com/fraud
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
Scanner in = new Scanner(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task1009 solver = new Task1009();
solver.solve(1, in, out);
out.close();
} static class Task1009 {
Scanner in;
PrintWriter out; public void solve(int testNumber, Scanner in, PrintWriter out) {
this.in = in;
this.out = out;
run();
} void run() {
BigInteger dp[] = new BigInteger[2010];
BigInteger a[] = new BigInteger[2010];
dp[0] = BigInteger.ONE;
dp[1] = BigInteger.ONE;
dp[2] = BigInteger.ONE;
dp[3] = BigInteger.valueOf(3);
dp[4] = BigInteger.valueOf(5);
a[0] = BigInteger.ZERO;
a[1] = BigInteger.ZERO;
a[2] = BigInteger.ONE;
a[3] = BigInteger.ONE;
a[4] = BigInteger.valueOf(2);
for (int i = 5; i < 2010; i++) {
dp[i] = dp[i - 1].add(dp[i - 2]);
a[i] = a[i - 2].add(dp[i - 2]);
}
for (int i = 1; i < 2010; i++) {
dp[i] = dp[i].add(dp[i - 1]);
}
BigInteger m;
int t, n;
t = in.nextInt();
while (t != 0) {
t--;
n = in.nextInt();
m = in.nextBigInteger();
if (m.compareTo(BigInteger.ONE) == 0) {
out.println(1);
continue;
}
int i = 0;
for (i = 0; i < 2010; i++) {
if (dp[i].compareTo(m) >= 0) break;
}
i--;
out.println(a[i + 1].add(m.subtract(dp[i].add(BigInteger.ONE))).mod(BigInteger.valueOf(258280327)));
}
} } static class Scanner {
BufferedReader br;
StringTokenizer st; public Scanner(InputStream in) {
br = new BufferedReader(new InputStreamReader(in));
eat("");
} private void eat(String s) {
st = new StringTokenizer(s);
} public String nextLine() {
try {
return br.readLine();
} catch (IOException e) {
return null;
}
} public boolean hasNext() {
while (!st.hasMoreTokens()) {
String s = nextLine();
if (s == null)
return false;
eat(s);
}
return true;
} public String next() {
hasNext();
return st.nextToken();
} public int nextInt() {
return Integer.parseInt(next());
} public BigInteger nextBigInteger() {
return new BigInteger(next());
} }
}