doom 规律 大数 -ag凯发k8国际

比赛的时候没有做出来，补题。

题意：题目定义了一个斐波那契串

1) fib1=b;

2) fib2=a;

3) fibi=fibi-1fibi-2,i>2

举例，fib3=ab,fib4=aba,fib5=abaab

我们暂时将字符串sisi 1si 2si 3…sj记做s[i:j]

求满足s[1:i]=s[m-i 1:m](i

例如m=5时，lborderm=2,因为abaab中前两个和末尾两个相同，即黑色部分

解题思路：

一看到题目的数据这么大，理所当然就会想到必定存在规律，先列出几项观察一下

m  lborderm  d-value(差值)

1          0               1

2          0               2

3          1               2

4          1               3

5          2               3

6          3               3

7          2               5

8          3               5

9          4               5

10        5               5

11        6               5

12        4               8

13        5               8

14        6               8  

由上述例子可知，m与结果之间的差值是斐波那契数，仔细观察一下，便会得出这样一个结论：

当我们找到第一个i满足m 1<|fibi|时，lborderm=m-|fibi-2|(|fibi-2|表示斐波那契串fibi-2的长度)  

1 import java.util.*; 2 import java.io.*; 3 import java.math.*; 4 5 public class main { 6 public static scanner cin = new scanner(new bufferedinputstream(system.in)); 7 public final static int ms = 1005; 8 public final static biginteger mod = new biginteger("258280327"); 9 public final static biginteger[] fib = new biginteger[ms]; 10 static { 11 fib[1] = biginteger.one; 12 fib[2] = new biginteger("2"); 13 for(int i = 3; i < ms; i ) 14 fib[i] = fib[i - 1].add(fib[i - 2]); 15 } 16 public static void main(string[] args) { 17 int t, n; 18 biginteger m; 19 t = cin.nextint(); 20 while (t-- > 0) { 21 n = cin.nextint(); 22 m = cin.nextbiginteger(); 23 m.add(biginteger.one); 24 for (int i = 1; i < ms; i ) { 25 if (fib[i].compareto(m) > 0) { 26 system.out.println(m.subtract(fib[i - 2]).mod(mod)); 27 break; 28 } 29 } 30 } 31 } 32 }

 

转载于:https://www.cnblogs.com/hutaishi/p/4705902.html

总结

以上是ag凯发k8国际为你收集整理的doom 规律 大数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。