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=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|.

Input

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

T lines. Each has one number, meaning 

fibn's 

LBorderm modulo 

258280327(=2×317+1).

Sample Input

2
4 3
5 5      

Sample Output

1

2

找找規律，然後模拟一下,注意有大數

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main
{
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);    
        BigInteger f[][] = new BigInteger[1005][3];
        int i;
        f[0][1]=BigInteger.ZERO;
        f[0][2]=BigInteger.ZERO;
        f[1][1]=BigInteger.ZERO;
        f[1][2]=BigInteger.ZERO;
        f[0][0]=BigInteger.ONE;
        f[1][0]=BigInteger.ONE;
        for (i=2;i<=1000;i++)
        {
            f[i][0]=f[i-1][0].add(f[i-2][0]);
            f[i][1]=f[i-1][2].subtract(f[i-1][1]);
            f[i][2]=f[i][1].add(f[i][0]).subtract(BigInteger.ONE);
        }
        int T=cin.nextInt();
        for(;T>=1;T--)
        {
            int n;
            BigInteger m;
            n=cin.nextInt();
            m=cin.nextBigInteger();
            for(i=1;i<=1000;i++)
            {
              if(m.compareTo(f[i][0])<1)
              {
                  m=f[i][1].add(m).subtract(BigInteger.ONE);
                  m=m.mod(BigInteger.valueOf(258280327));
                  System.out.println(m);
                  break;
              }
              else
                  m=m.subtract(f[i][0]);
            }
        }
    }
}