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());
}
}
}
}
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());
}
}
}
}
