2015 Multi-University Training Contest 5 1009 MZL's BorderMZL's Border Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5351

Mean: 

给出一个类似斐波那契数列的字符串序列,要你求给出的f[n]字符串中截取前m位的字符串s中s[1...i] = s[s.size()-i+1....s.size()]的最大长度。

analyse:

  过计算可以发现，b字符串的前缀都是相同的，所以只要求出m的LBorder就行，和n是无关的，打表找出规律，找出对应不同的m，LBorder的值.

Time complexity: O(N)

Source code: 

import java.math.BigInteger;

import java.util.Scanner;

public class Main {

   static BigInteger[] fib1 = new BigInteger[1010];

   static BigInteger[] fib2 = new BigInteger[1010];

   static BigInteger[] fib3 = new BigInteger[1010];

   public static void main(String[] args) {

       fib1[1] = new BigInteger("2");

       fib1[2] = new BigInteger("2");

       fib2[1] = BigInteger.ONE;

       fib2[2] = BigInteger.ONE;

       fib3[1] = BigInteger.ZERO;

       fib3[2] = BigInteger.ONE;

       for (int i = 3; i <= 1005; i++) {

           fib1[i] = fib1[i - 1].add(fib1[i - 2]);

           fib2[i] = fib2[i - 1].add(fib2[i - 2]);

       }

           fib3[i] = fib3[i - 1].add(fib2[i - 1]);

       Scanner in = new Scanner(System.in);

       int t = in.nextInt();

       for (int cas = 0; cas < t; ++cas) {

           BigInteger m;

           int n = in.nextInt(), i;

           m = in.nextBigInteger();

           for (i = 1; i <= 1005; i++) {

               if (m.compareTo(fib1[i]) == 1) {

                   m = m.subtract(fib1[i]);

               } else break;

           }

           if (m.compareTo(fib1[i].divide(new BigInteger("2"))) == 1) {

               m = m.subtract(fib1[i].divide(new BigInteger("2")));

               BigInteger ans = m.add(fib3[i]);

               ans = ans.subtract(BigInteger.ONE);

               ans = ans.remainder(new BigInteger("258280327"));

               System.out.println(ans.toString());

           } else {

   }

}