HDU 5351——MZL's Border——————【高精度+找規律】

MZL's Border

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 944    Accepted Submission(s): 306

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

Sample Input 2 4 3 5 5  

Sample Output 1 2   題目大意：這個題目定義了一些新概念，而且比較繞，是以題意不是太好了解。給T組測試資料，每組有n,m。表示從fibn這個字元串中截取子串s[1:m]。然後在這個字串中找到最大的i滿足s[1:i]=s[m-i+1:m]，即公共前字尾。當時了解成了跟n有關系，即s[1:i]=s[n-i+1:n]，主要受那個題的描述影響了。   解題思路：其實這個題目計算隻跟m有關系，因為n隻是進行限制了m的大小，跟n沒多大關系。我們列出幾項會發現，m跟LBorder m的內插補點是成斐波那契數列的。

import java.io.*;
import java.util.*;
import java.math.*;
public class Main{
	public static void main(String [] args){
		BigInteger one=BigInteger.ONE, zero = BigInteger.ZERO ;
		BigInteger fib[] = new BigInteger [1200];
		fib[1]=one;
		fib[2]=one;
		for(int i=3;i<=1005;i++){
			fib[i]=fib[i-1].add( fib[i-2] );
		}
		Scanner cin = new Scanner (System.in);
		int t=cin.nextInt();
		while(t>0){
			t--;
			int n= cin.nextInt();
			BigInteger m =  cin.nextBigInteger();
			for(int i=1;i<=1005;i++){
				if(fib[i].compareTo(m.add( one ) )==1){
					System.out.println( m.subtract(fib[i-2]).mod(BigInteger.valueOf(258280327 )));
					break;
				}
			}
		}
	}
}
           

　　

轉載于:https://www.cnblogs.com/chengsheng/p/4707352.html