甘肃兰州/网站关键词优化排名公司

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

题意：给出数列递推式，Fn=C⋅Fn−2+D⋅Fn−1+⌊P/n⌋求数列的第n项。

解析：由于公式中包含非常数项⌊P/i⌋，所以不能直接用矩阵快速幂，因为n-3个矩阵是不同的，但可以想到按⌊P/i⌋的值分块，那么每块中的⌊P/i⌋相同，就可以对每个块单独构造矩阵使用矩阵快速幂，然后将多块矩阵再相乘即可。

这里可以简化一点，就是只先将多块的矩阵相乘，而先不乘初始的列向量（初始列向量即{F2,F1,1}）。这样比每块都乘上由上一块算出来的列向量要好实现一些。

这题首先分块是个难点，而且块的级别在sqrt(P)，直接对于3~n分块的话会超时，所以我们直接暴力前1e5项（因为前面分的块多），后面的再分块，就能有较好的复杂度。

代码：

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
#define M 3
#define mod 1000000007ll A,B,C,D,P,n;struct Matrix
{Matrix(){memset(a,0,sizeof(a));}ll a[M][M];void init()//初始化为单位矩阵{for(ll i=0;i<M;i++)for(ll j=0;j<M;j++)a[i][j]=0;for(ll i=0;i<M;i++)a[i][i]=1;}
}MA,MT;
Matrix mul(Matrix a,Matrix b) //(a*b)%mod
{Matrix ans;ll i,j,k;for(i=0;i<M;i++)for(j=0;j<M;j++){for(k=0;k<M;k++)ans.a[i][j]+=a.a[i][k]*b.a[k][j];ans.a[i][j]%=mod;}return ans;
}
Matrix pow(Matrix a,ll n) //(a^n)%mod
{Matrix ans;ans.init();while(n){if(n&1)ans=mul(ans,a);n>>=1;a=mul(a,a);}return ans;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%lld%lld%lld%lld%lld%lld",&A,&B,&C,&D,&P,&n);if(n==1)printf("%lld\n",&A);else if(n==2)printf("%lld\n",&B);else if(n==3)printf("%lld\n",(C*A+D*B+P/3)%mod);else if(n<=100005)//n较小直接暴力{ll x,y,z;x=A;y=B;for(int i=3;i<=n;i++){z=C*x+D*y+P/i;z%=mod;x=y;y=z;}printf("%lld\n",y);}else{ll x,y,z;x=A;y=B;for(int i=3;i<=100000;i++)//前1e5项暴力，后面分块{z=C*x+D*y+P/i;z%=mod;x=y;y=z;}MT.init();int l=n,r,c;//假设区间从左到右为从n~100001for(int i=P/n;i<=P/100001;i++)//（P/i）就是块值为i的这一块的左端点{r=P/(i+1)+1;//（P/(i+1)）是下一块的左端，（P/(i+1)+1）就是本块的右端r=max(r,100001);c=l-r+1;//块长度MA.a[0][0]=D; MA.a[0][1]=C; MA.a[0][2]=i;MA.a[1][0]=1; MA.a[1][1]=0; MA.a[1][2]=0;MA.a[2][0]=0; MA.a[2][1]=0; MA.a[2][2]=1;MA=pow(MA,c);MT=mul(MT,MA);l=r-1;}ll ans=(MT.a[0][0]*y+MT.a[0][1]*x+MT.a[0][2]*1)%mod;//最后乘上列向量printf("%lld\n",ans);}}return 0;
}