Description

出乎意料的是，幸运E 的小R 居然赢了那个游戏。现在欣喜万分的小R 想要写一张明信片给小Y，但是因为小R 非常羞涩，所以他打算采用一些比较神奇的方式来表达。

他定义了一些字符串，s1 = a,s2 = b,si =s_i-1  +  s_i-2  (i >=3)。同时他定义了一个字符串s 的权值为一个最大的i <|s|满足s 长度为i 的前缀等于长度为i 的后缀。比如字符串aba 的权值就是1，abab 的权值就是2，aaaa 的权值就是3。

现在小R 在明信片上给出了两个数n 和m，他想要告诉小Y 的信息是字符串sn 的前m个字符组成的字符串的权值。你可以帮小Y 计算一下吗？

 

Input

第一行输入一个正整数T 表示数据组数。

对于每组数据，第一行是两个整数n;m。保证1<= m <=|sn|

Output

对于每组数据，输出一个整数表示答案。答案可能很大，你只需要输出模258280327 后的答案。

 

Sample Input

24 35 5

Sample Output

12

 

Data Constraint

对于30% 的数据，n <= 20

对于60% 的数据，n <= 60

对于100% 的数据，n <= 10^3，1 <= T <= 100

 

题解

• 这就是道打表找规律的题目，至于怎么证明有没有大佬教一教
• 找到第一个斐波那契数列长度n大于m+1，答案就是 m-|n-2|
• 然后就要上高精度了，因为我们还要找到n，打个二分

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define mo 258280327 5 #define N 1010 6 using namespace std; 7 struct edge{ int a[1005],l; }f[N],p; 8 int T,n,P[N]; 9 void add(edge &x,edge &y,edge &k)10 {11     for (int i=1;i
        
         '9');29         P[p.l=1]=ch-48; while (ch=getchar(),ch>='0'&&ch<='9') P[++p.l]=ch-48;30         for (int i=p.l;i;i--) p.a[p.l-i+1]=P[i]; p.a[1]++;31         for (int i=1;i<=p.l;i++) p.a[i+1]+=p.a[i]/10,p.a[i]%=10;32         if (p.a[p.l+1]) p.l++;33         int l=1,r=1001,q=0;34         while (l<=r)35         {36             int mid=l+r>>1;37             if (check(p,f[mid])) q=mid,r=mid-1; else l=mid+1;38         }39         q-=2,p.a[1]--;40         for (int i=1;i<=f[q].l;i++)41         {42             p.a[i]-=f[q].a[i];43             if (p.a[i]<0) p.a[i]+=10,p.a[i+1]--;44         }45         while (p.l>1&&!p.a[p.l]) p.l--;46         q=0; for (int i=p.l;i;i--) q=(q*10ll+p.a[i])%mo;47         printf("%d\n",q);48     }49 }