CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Sequence
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
#define mul(a,b,c) (1LL*(a)*(b)%(c))
using namespace std;
typedef int ll;
const ll N=3,M=1e9+7;
struct Matrix
{
static int n;
ll a[N][N];
Matrix(ll k=0)
{
for(int i=0; i<n; ++i)fill(a[i],a[i]+n,0),a[i][i]=k;
}
};
int Matrix::n=N;
Matrix operator*(const Matrix &a,const Matrix &b)
{
Matrix r(0);
for(int i=0; i<r.n; ++i)
for(int j=0; j<r.n; ++j)
for(int k=0; k<r.n; ++k)
r.a[i][j]=(r.a[i][j]+mul(a.a[i][k],b.a[k][j],M))%M;
return r;
}
Matrix pow(Matrix a,ll b)
{
Matrix r(1);
for(; b; b>>=1,a=a*a)
if(b&1)r=r*a;
return r;
}
int main()
{
int t,a,b,c,d,p,n;
for(scanf("%d",&t); t--;)
{
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&p,&n);
Matrix ans,e;
ans.a[0][0]=a,ans.a[1][0]=b;
e.a[1][0]=c,e.a[1][1]=d,e.a[0][1]=e.a[1][2]=e.a[2][2]=1;
for(int i=3,last; i<=n; i=last+1)
{
if(ans.a[2][0]=p/i,ans.a[2][0])last=min(p/ans.a[2][0],n);
else last=n;
ans=pow(e,last-i+1)*ans;
}
printf("%lld\n",ans.a[1][0]);
}
}