HDU6395 分块思想

约定不等于承诺〃 2022-05-16 04:25 134阅读 0赞

[传送门][Link 1]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e5+10;
    const int mo=1e9+7;
    ll n, P, F[N], C, D, inv[N];
    struct Matrix{
        ll m[3][3];
    };
    
    void init(){
        F[1]%=mo; F[2]%=mo;
        for(int i=3; i<=1e5; i++)
            F[i]=(C*F[i-2]%mo+D*F[i-1]%mo+P/i)%mo;
    }
    
    inline void gouzao1(Matrix& tmp){
        memset(tmp.m, 0, sizeof tmp.m);
        tmp.m[1][0]=C; tmp.m[1][1]=D;
        tmp.m[0][1]=1;  tmp.m[2][2]=1;
    }
    inline void gouzao2(Matrix& tmp){
        memset(tmp.m, 0, sizeof tmp.m);
        tmp.m[0][0]=F[99998], tmp.m[1][0]=F[99999], tmp.m[2][0]=1;
    }
    
    inline Matrix Mul(Matrix& a, Matrix& b){
        Matrix c;
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                c.m[i][j]=0;
                for(int k=0; k<3; k++)
                    c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%mo)%mo;
            }
        }
        return c;
    }
    
    Matrix M_pow(Matrix bas, int m){
        Matrix ret;
        memset(ret.m, 0, sizeof ret.m);
        ret.m[0][0]=ret.m[1][1]=ret.m[2][2]=1;
        while(m){
            if(m&1)
                ret=Mul(ret, bas);
            m>>=1;
            bas=Mul(bas, bas);
        }
        return ret;
    }
    
    int main(){
        int T;
        scanf("%d", &T);
        while(T--){
    
            scanf("%lld%lld%lld%lld%lld%lld", &F[1], &F[2], &C, &D, &P, &n);
            init();
            if(n<=1e5)
                printf("%lld\n", F[n]);
            else{
                Matrix tmp, ans, tmp1;
                gouzao1(tmp); gouzao2(ans);
                for(int i=1e5, las; i<=n; i=las+1){
                    las=P/i==0 ? n : min(P/(P/i), n); tmp.m[1][2]=P/i;
    
                    tmp1=M_pow(tmp, las-i+1);
                    ans=Mul(tmp1, ans);
                }
                printf("%lld\n", ans.m[1][0]);
            }
        }
    
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6395