2015 Multi-University Training Contest 5 1009 MZL#39;s Border

本文主要是介绍2015 Multi-University Training Contest 5 1009 MZL#39;s Border，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

MZL'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 ]); 
         } 
         for ( int i = 3; i <= 1005; i ++) { 
             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 { 
                 BigInteger ans = m . add( fib3 [ i ]); 
                 ans = ans . subtract( BigInteger . ONE); 
                 ans = ans . remainder( new BigInteger( "258280327")); 
                 System . out . println( ans . toString()); 
             } 
         } 
     } 
 } 