【题解】牛牛的斐波那契

题意

其中表示向上取整。
求第个斐波那契数对取模。

思路

首先若是一个常数那就是一个简单的矩阵快速幂题目了。但是由于的值在不断变化所以并不好直接去套用矩阵快速幂。但是由于在某一段的区间之内其值是不变化的，而且这样的区间大概有只有个。那么我们就可以通过这个角度来加速矩阵快速幂了。
假设当前区间的开始值为，结束值为，那么构建的矩阵就是
我们只要每次记录下新一段的和就可以利用其求解出下一段的值。
那么如何去求的值呢。由于的值是递减的，所以我们可以利用二分去找第一个大于当前值的下标。

int Find(int n,int i)
{
    int x=ceil(1.0*n/i);
    int l=i;
    int r=n;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(ceil(1.0*n/mid)<x)
            r=mid-1;
        else
            l=mid+1;
    }
    return r;
}

需要注意的是小于m的部分和大于m的部分应该分开处理。

复杂度

时间复杂度为

代码

#include<bits/stdc++.h>
#define MAX 3
using namespace std;
typedef struct
{
    long long m[MAX][MAX];
} Matrix;
Matrix P= {1,1,1,1,0,0,0,0,1};
Matrix I= {1,0,0,0,1,0,0,0,1};
const long long mod=1e9+7;
Matrix Matrixmul(Matrix a,Matrix b)
{
    int i,j,k;
    Matrix c;
    for(i=0; i<MAX; i++)
        for(j=0; j<MAX; j++)
        {
            c.m[i][j]=0;
            for(k=0; k<MAX; k++)
            {
                c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod;
            }
            c.m[i][j]%=mod;
        }
    return c;
}
Matrix quickpow(long long n)
{
    Matrix m=P,b=I;
    while(n>0)
    {
        if(n%2==1)
            b=Matrixmul(b,m);
        n=n/2;
        m=Matrixmul(m,m);
    }
    return b;
}
int Find(int n,int i)
{
    int x=ceil(1.0*n/i);
    int l=i;
    int r=n;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(ceil(1.0*n/mid)<x)
            r=mid-1;
        else
            l=mid+1;
    }
    return r;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        if(n<=2)
        {
            printf("1\n");
            continue;
        }
        long long ans=0;
        long long ta=1;
        long long tb=1;
        int minn=min(n,m);
        for(int i=3,last; i<=minn; i=last+1)//9 5 3 3 2 2 2 2 1
        {
            last=min(Find(m,i),minn);
            Matrix A=quickpow(last-i+1);
            ans=(A.m[0][0]*tb%mod+A.m[0][1]*ta%mod+A.m[0][2]*(long long)ceil(1.0*m/i)%mod+mod)%mod;
            ta=(A.m[1][0]*tb%mod+A.m[1][1]*ta%mod+A.m[1][2]*(long long)ceil(1.0*m/i)%mod+mod)%mod;
            tb=ans;
        }
        if(n>m)
        {
            Matrix A=quickpow(n-max(m,2));
            ans=(A.m[0][0]*tb%mod+A.m[0][1]*ta%mod+A.m[0][2]%mod+mod)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}