Sequence HDU - 6395

L_Ambition · 2021-07-19 10:44:11 · 个人记录

题目链接

HDU 6395 Sequence

题目大意

先给出递推的方程，然后进行多次询问

每次给出A,B,C,D,n,P的值

然后输出第n项的值。

题解

该题是一道显然的递推求解。

递推求解的显然做法：矩阵快速幂。

但是我们可以看到这里有一项是自变量，而单纯的矩阵乘法是没有办法去处理的。

看到向下取整，我们自然的想到了整除分块。

可以发现乘除分块部分最后一项的值是不会发生改变的，我们就通过整除分块，一块一块得使用矩阵快速幂。

每一块乘完以后，再改变单位矩阵这样的做法是可行的。

#include<bits/stdc++.h>
using namespace std;
const long long mod =1e9+7;
struct matrix {
    long long a[3][3];
    matrix() {
        memset(a,0,sizeof(a));
    }
} ans;
long long A,B,C,D,P,n;
matrix c_matrix(matrix a,matrix b) {
    matrix c;
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            for(int k=0; k<3; k++) {
                c.a[i][j]+=a.a[i][k]*b.a[k][j];
                c.a[i][j]%=mod;
            }
        }
    }
    return c;
}
matrix pow(matrix x,long long a) {
    matrix ans;
    ans.a[0][0]=ans.a[1][1]=ans.a[2][2]=1;
    while(a) {
        if(a&1) {
            ans=c_matrix(ans,x);
        }
        x=c_matrix(x,x);
        a/=2;
    }
    return ans;
}
inline void solve() {
    ans.a[0][0]=D;
    ans.a[0][1]=C;
    ans.a[1][0]=1;
    ans.a[2][2]=1;
    for(int i=3; i<=n;) {
        if(P/i==0) {
            matrix out=ans;
            out=pow(out,n-i+1);
            printf("%lld\n",(A*out.a[0][1]+B*out.a[0][0]+out.a[0][2])%mod);
            return ;
        }
        long long j=min(n,P/(P/i));
        matrix out=ans;
        out.a[0][2]=P/i;
        out=pow(out,j-i+1);
        long long a=(out.a[1][0]*B+out.a[1][1]*A+out.a[1][2])%mod;
        long long b=(out.a[0][0]*B+out.a[0][1]*A+out.a[0][2])%mod;
        A=a,B=b;
        i=j+1;
    }
    printf("%lld\n",B);
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%lld%lld%lld%lld%lld%lld",&A,&B,&C,&D,&P,&n);
        switch (n) {
            case 1 : {
                printf("%lld\n",A);
           break;
         }
            case 2 : {
                printf("%lld\n",B);
                break;
            }
            default :
                solve();
        }
    }
}