2018 Multi-University Training Contest 7 （hdu6395 Sequence）

Input

The first line has only one integer T, indicates the number of tasks.

Then, for the next T lines, each line consists of 6 integers, A , B, C, D, P, n.

1≤T≤200≤A,B,C,D≤1091≤P,n≤109

Sample Input

3 3 2 1 3 5

3 2 2 2 1 4

Sample Output

题意：略

思路：因为[P/n]这个的存在，所以如果想用矩阵快速幂必须得分块讨论，比如当n>P/2时，[P/n]为1，当n>P/3，[P/n]为2...。就这样分块计算，因为实在不行我们可以预处理前1e6项，从1e6到1e9最多分1000块，所以一定不会超时。然后里面一个小技巧。

当本位是从i=3开始表示2的后一位数的位置，然后(P/(P/i))+1就是下一个块的下一位了。记得分类讨论P和n大小。

代码：

const ll mod=1e9+7;
const int ssize=3;
struct matrix
{
long long num[ssize+1][ssize+1];
matrix() {memset(num,0,sizeof(num));}
matrix operator*(const matrix &P)const
{
matrix ans;
for(int k=1;k<=ssize;k++)
for(int i=1;i<=ssize;i++)
for(int j=1;j<=ssize;j++)
ans.num[i][j]=(ans.num[i][j]+num[i][k]*P.num[k][j]%mod)%mod;
return ans;
}
}ans,tmp;
matrix pOw(matrix m,ll n)
{
matrix ans;
for(int i=1;i<=ssize;i++) ans.num[i][i]=1;
while(n)
{
if(n&1) ans=ans*m;
m=m*m;
n=n>>1;
}
return ans;
}
void init(ll A,ll B,ll C,ll D,ll x)
{
tmp.num[1][1]=0;tmp.num[1][2]=1;tmp.num[1][3]=0;
tmp.num[2][1]=C;tmp.num[2][2]=D;tmp.num[2][3]=x;
tmp.num[3][1]=0;tmp.num[3][2]=0;tmp.num[3][3]=1;
return ;
}
int main()
{
int T_T;
ll A,B,C,D,P,n;
scanf("%d",&T_T);
while(T_T--)
{

scanf("%lld%lld%lld%lld%lld%lld",&A,&B,&C,&D,&P,&n);
if(n==1) {cout<<A<<endl;continue;}
if(P>n)
{
ans.num[1][1]=A;
ans.num[2][1]=B;
ans.num[3][1]=1;
for(ll i=3;i<=n;i=P/(P/i)+1)// i 表是本块的开始的位置
{
init(A,B,C,D,P/i);
if(P/(P/i)>=n) tmp=pOw(tmp,n-i+1);
else tmp=pOw(tmp,P/(P/i)+1-i);
ans=tmp*ans;
}
cout<<ans.num[2][1]<<endl;
}
else
{
ans.num[1][1]=A;
ans.num[2][1]=B;
ans.num[3][1]=1;
for(ll i=3;i<=P;i=P/(P/i)+1)
{
init(A,B,C,D,P/i);
tmp=pOw(tmp,P/(P/i)+1-i);
ans=tmp*ans;
}
init(A,B,C,D,0);
tmp=pOw(tmp,n-max(P,2ll));
ans=tmp*ans;
cout<<ans.num[2][1]<<endl;
}
}
}

2018 Multi-University Training Contest 7 （hdu6395 Sequence）

相关推荐