分块+矩阵快速幂_分块矩阵的幂

http://acm.hdu.edu.cn/showproblem.php?pid=6395

P/i会有相同的一段，所以想到分块，这个也经常用

#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
typedef long long ll;
const int Mod=1e9+7;
int A,B,C,D,n,P;
 
struct Mat
{
    int t[3][3];
    
    Mat(){memset(t,0,sizeof t);}
}I;
 
Mat operator * (Mat a,Mat b)
{
    Mat c;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        {
            ll t=0;
            for(int k=0;k<3;k++)
                t+=(ll)a.t[i][k]*b.t[k][j];
            c.t[i][j]=t%Mod;
        }
    return c;
}
 
Mat Pow(Mat a,int b)
{
    Mat c=I;
    while(b)
    {
        if(b&1)
            c=c*a;
        a=a*a;b>>=1;
    }
    return c;
}
 
void solve()
{
    scanf("%d%d%d%d%d%d",&A,&B,&C,&D,&P,&n);
    if(n==1)
    {
        cout<<A<<endl;
        return;
    }
    Mat f;
    f.t[0][0]=D;
    f.t[0][1]=C;
    f.t[1][0]=1;
    f.t[2][2]=1;
    for(int i=3;i<=n;)
    {
        if(P/i==0)
        {
            Mat w=f;
            w=Pow(w,n-i+1);
            cout<<(w.t[0][0]*(ll)B+w.t[0][1]*(ll)A+w.t[0][2])%Mod<<endl;return;
        }
        int j=min(n,P/(P/i));
        Mat w=f;w.t[0][2]=P/i;
        w=Pow(w,j-i+1);
        ll a=(w.t[1][0]*(ll)B+w.t[1][1]*(ll)A+w.t[1][2])%Mod,b=(w.t[0][0]*(ll)B+w.t[0][1]*(ll)A+w.t[0][2])%Mod;
        A=a;B=b;
        i=j+1;
    }
    cout<<B<<endl;
}
 
int main()
{
    I.t[1][1]=I.t[0][0]=I.t[2][2]=1;
    int t;cin>>t;
    while(t--)
        solve(); 
    return 0;
}