题意：设一个斐波那契串序列，F1=b, F2=a, ..., Fn=Fn-1Fn-2。一个串的LBoardm意思是：取此串的长为m的前缀作为子串，则此子串自身的前后缀最长匹配即为原串的LBoardm。现给出n和m，求斐波那契串Fn的LBoardm。（不知道讲清楚没有。。题意就是这么绕。。）
分析：鉴于题意这么BT，过的人又这么多，怀疑是打表找规律。遂写了个暴力CPP程序跑了一下：
1 // Test Successd! 2 #include3 using namespace std; 4 5 const int N = 110000; 6 int next[N], extend[N]; 7 int len[20]; 8 string f[20]; 9 void kmp_pre(string x,int m,int next[])10 {11 int i,j;12 j=next[0]=-1;13 i=0;14 while(i
跑完之后果然规律出来了。。。
结果实际上与n无关，只和m有关，当m依次取1~1000时，对应的结果序列为：（0）（0）（1）（1）（2,3）（2,3）（4,5,6）（4,5,6）（7,8,9,10，11）（7,8,9,10，11）....
序列分为若干组，每组元素的个数成斐波那契数列，且重复两次。不看重复，所有元素依次递增。要求的第m项是几？
假设第m项落在第k组里，则有不等式：2*（F1+F2+..+Fk-1）< m <= 2*（F1+F2+..+Fk）成立，可以预处理Fn的前缀和，然后O(n)扫过去求出k。
然后看它在该组里的第几项。设不等式左右边界分别为L和R，则m在该组内的偏移量为m-L。
但是！
每组是重复两次的，所以若偏移量m-L>Fk，则偏移量应该再减去Fk，所以最终偏移量为 (m-L>Fk)?(m-L-Fk)：(m-L)。
鉴于数据太大，上java大数类。。。
1 // AC 358ms 13640k 1330B 2 // 2015-11-29 20:04 @qiucz 3 import java.io.*; 4 import java.util.*; 5 import java.math.*; 6 7 public class Main 8 { 9 public static void main(String[] args) 10 {11 BigInteger[] f = new BigInteger[1100];12 BigInteger[] sum = new BigInteger[1100];13 f[1] = f[2] = BigInteger.ONE;14 sum[1] = BigInteger.ONE;15 sum[2] = BigInteger.valueOf(2);16 BigInteger MD = BigInteger.valueOf(258280327);17 for(int i = 3; i <= 1010; ++i)18 {19 f[i] = f[i-1].add(f[i-2]);//.mod(MD);20 sum[i] = sum[i-1].add(f[i]);//.mod(MD);21 //System.out.println(i + " " + f[i] + " " + sum[i]);//22 }23 24 Scanner cin = new Scanner(System.in);25 int T = cin.nextInt();26 while(T > 0)27 {28 BigInteger n = cin.nextBigInteger();29 BigInteger m = cin.nextBigInteger();30 if(m.compareTo(BigInteger.valueOf(2)) <= 0)31 {32 System.out.println("0");33 continue;34 }35 //System.out.println(n + " " + m);//36 //n = n.mod(MD); m = m.mod(MD);37 int i = 1;38 while(sum[i].multiply(BigInteger.valueOf(2)).compareTo(m) < 0) ++i;39 //System.out.println(i);//40 BigInteger d = m.subtract(sum[i-1].multiply(BigInteger.valueOf(2)));//.mod(MD)41 if(d.compareTo(BigInteger.ZERO) < 0) d.add(MD);42 if(d.compareTo(f[i]) > 0) d = d.subtract(f[i]);43 BigInteger ans = sum[i-1].subtract(BigInteger.ONE).add(d).mod(MD);44 System.out.println(ans);45 --T;46 }47 }48 }49 50 /*51 10052 1000 25828032653 1000 25828032754 */55 56 /*57 15594617158 15594617259 */ PS：最后别忘了取模。。。