HDU6395 Sequence 【矩阵快速幂】【分块】

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6395

题意： 求$F(n)=D\ast F(n-1)+C\ast F(n-2)+[P/n]$的第n项，其中$F(1)=a,F(2)=b$

题解： 注意到因为递推式的常数项是个变量，所以不能无脑矩阵快速幂 这个函数很眼熟…分块？ 我们对 P/i 分块，可以构造单位矩阵： $DCP/i$ $100$ $100$ 然后对于此时 P/i 就是固定的了，跑矩阵快速幂即可 此题卡常，matrix 里以前 ma[3][3]是ma[15][15]的就会T

// by Balloons #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define mpr make_pair #define debug() puts("okkkkkkkk") #define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) using namespace std; typedef long long LL; #define int LL const int inf = 1 << 30,mod=1e9+7; int a,b,c,d,p,n; struct matrix{ int ma[3][3]; matrix(){memset(ma,0,sizeof ma);} }; matrix operator *(matrix a,matrix b){ matrix tmp; for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) (tmp.ma[i][j]+=a.ma[i][k]*b.ma[k][j])%=mod; return tmp; } matrix pow(matrix a,LL b){ matrix tmp; for(int i=0;i<3;i++)tmp.ma[i][i]=1; while(b){ if(b&1ll)tmp=tmp*a; b>>=1ll; a=a*a; } return tmp; } void work(){ scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&p,&n); if(n==1){ printf("%lld\n",a); return ; } if(n==2){ printf("%lld\n",b); return ; } int ok=0; for(LL i=3;i<=n;){ if(p/i==0){ matrix aa; aa.ma[0][0]=d;aa.ma[0][1]=c;aa.ma[0][2]=p/i; aa.ma[1][0]=1;aa.ma[2][2]=1; aa=pow(aa,n-i+1); int res=aa.ma[0][0]*b+aa.ma[0][1]*a+aa.ma[0][2]; res%=mod; printf("%lld\n",res); ok=1; break; } int j=min(n,p/(p/i)); matrix aa; aa.ma[0][0]=d;aa.ma[0][1]=c;aa.ma[0][2]=p/i; aa.ma[1][0]=1;aa.ma[2][2]=1; matrix tmp=pow(aa,j-i+1); int A=tmp.ma[1][0]*b+tmp.ma[1][1]*a+tmp.ma[1][2]; int B=tmp.ma[0][0]*b+tmp.ma[0][1]*a+tmp.ma[0][2]; A%=mod;B%=mod; a=A;b=B; i=j+1; } if(!ok)printf("%lld\n",b); } signed main(){ int T;scanf("%d",&T); while(T--)work(); return 0; }