「kuangbin带你飞」专题十九 矩阵

传送门

A.CodeForces - 450B Jzzhu and Sequences

题意

水题,主要是拿来试试模板

题解

F[i]=f[i-1]-f[i-2]

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pp pair<int,int>
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int (int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
struct Matrix{
ll mat[5][5];
int n;
Matrix(){}
Matrix(int _n){
n=_n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
mat[i][j]=0;
}
Matrix operator *(const Matrix &b)const{
Matrix ret=Matrix(n);
for(int i=0;i<n;i++){
for(int k=0;k<n;k++){
if(mat[i][k])
for(int j=0;j<n;j++){
ret.mat[i][j]+=(mat[i][k]*b.mat[k][j]+mod)%mod;
ret.mat[i][j]+=mod;
ret.mat[i][j]%=mod;
}
}
}
return ret;
}
ull pow_m(ull a,int n){
ull ret=1,tmp=a;
while(n){
if(n&1)ret*=tmp;
tmp*=tmp;
n>>=1;
}
return ret;
}
Matrix pow_M(Matrix a,ll n){
Matrix ret=Matrix(a.n);
for(int i=0;i<a.n;i++)ret.mat[i][i]=1;
Matrix tmp=a;
while(n){
if(n&1)ret=ret*tmp;
tmp=tmp*tmp;
n>>=1;
}
return ret;
}
};
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll x,y,n;
cin>>x>>y>>n;
Matrix a=Matrix(2);
a.mat[0][0]=1;a.mat[0][1]=-1;
a.mat[1][0]=1,a.mat[1][1]=0;
if(n==1){cout<<(x+mod)%mod<<endl;return 0;}
if(n==2){cout<<(y+mod)%mod<<endl;return 0;}
a=a.pow_M(a,n-2);
cout<<((a.mat[0][0]*y+a.mat[0][1]*x)%mod+mod)%mod;
return 0;
}
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

using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int (int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
ll x,y;
typedef vector<ll>vec;
typedef vector<vec>mat;
mat mul(mat& A,mat &B){
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();i++)
for(int k=0;k<B.size();k++)
if(A[i][k])
for(int j=0;j<B[0].size();j++)
C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod+mod)%mod;
return C;
}
mat Pow(mat A,ll n){
mat B(A.size(),vec(A.size()));
for(int i=0;i<A.size();i++)B[i][i]=1;
for(;n;n>>=1,A=mul(A,A))
if(n&1)B=mul(B,A);
return B;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>x>>y;
ll n;
cin>>n;
if(n==1){
cout<<(x+mod)%mod<<endl;return 0;
}
else if(n==2){
cout<<(y+mod)%mod<<endl;return 0;
}
mat a(2,vec(2));
a[0][0]=1;a[0][1]=-1;a[1][0]=1;a[1][1]=0;
a=Pow(a,n-2);
cout<<(a[0][0]*y%mod+a[0][1]*x%mod+mod+mod)%mod<<endl;
return 0;
}

B.HDU - 5015 233 Matrix

题意

给出矩阵的第0行(0,233,2333,23333,…)和第0列a1,a2,…an(n<=10,m<=10^9),给出式子:

题解

假设要求A[a]【b]则

相当于上图,红色部分为绿色部分之和,而顶上的绿色部分很好求 左边的部分就是前一列的(1-n)的和

所以我们只要知道第一列和第一行就能推出任意列@

构造上图的中间矩阵,因为第0列到第一列不符合 所以手动求出第一列的答案,然后再求出中间矩阵的m-1次方 和第一列相乘就是答案了

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pp pair<int,int>
const ll mod=1e7+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int (int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
struct Matrix{
ll mat[15][15];
int n;
Matrix(){}
Matrix(int _n){
n=_n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
mat[i][j]=0;
}
Matrix operator *(const Matrix &b)const{
Matrix ret=Matrix(n);
for(int i=0;i<n;i++){
for(int k=0;k<n;k++){
if(mat[i][k])
for(int j=0;j<n;j++){
ret.mat[i][j]+=(mat[i][k]*b.mat[k][j]+mod)%mod;
ret.mat[i][j]+=mod;
ret.mat[i][j]%=mod;
}
}
}
return ret;
}
ull pow_m(ull a,int n){
ull ret=1,tmp=a;
while(n){
if(n&1)ret*=tmp;
tmp*=tmp;
n>>=1;
}
return ret;
}
Matrix pow_M(Matrix a,ll n){
Matrix ret=Matrix(a.n);
for(int i=0;i<a.n;i++)ret.mat[i][i]=1;
Matrix tmp=a;
while(n){
if(n&1)ret=ret*tmp;
tmp=tmp*tmp;
n>>=1;
}
return ret;
}
};
ll num[20];
ll sum[20];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll n,m;
while(cin>>n>>m){
Matrix a=Matrix(n+2);
num[0]=0;
for(int i=1;i<=n;i++)cin>>num[i];
sum[0]=233;
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+num[i];
sum[n+1]=3;
if(m==0){
cout<<num[m]<<endl;continue;
}
else if(m==1){
cout<<sum[m]<<endl;continue;
}
else{
for(int i=0;i<n+1;i++)a.mat[i][0]=10;
for(int i=1;i<n+1;i++){
for(int j=1;j<=i;j++){
a.mat[i][j]=1;
}
}
for(int i=0;i<n+2;i++)a.mat[i][n+1]=1;

for(int j=0;j<n+2;j++){
cout<<a.mat[i][j]<<" ";
}
cout<<endl;
}*/
a=a.pow_M(a,m-1);
ll ans=0;
ll anw[15]={0};
for(int i=0;i<n+2;i++){
for(int j=0;j<n+2;j++){
anw[i]=(anw[i]+(a.mat[i][j]*sum[j])%mod)%mod;
}
}
cout<<anw[n]%mod<<endl;
}
}
return 0;
}

C.HDU - 4990 Reading comprehension

题意

题目给我们一个O(N)求值程序 让我们求这个值在操作N次后的答案

n&1->ans=ans*2+1;

else->ans=ans*2;

题解

因为数据量很大(1e9)所以很可能会超时,所以只能用加速算法

现在我们考虑只有偶数项
如果是偶数就直接求n/2次方,如果是奇数就求出二次方后再*2+1;

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pp pair<int,int>
//const ll mod=1e7+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int (int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
ll mod;
struct Matrix{
ll mat[15][15];
int n;
Matrix(){}
Matrix(int _n){
n=_n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
mat[i][j]=0;
}
Matrix operator *(const Matrix &b)const{
Matrix ret=Matrix(n);
for(int i=0;i<n;i++){
for(int k=0;k<n;k++){
if(mat[i][k])
for(int j=0;j<n;j++){
ret.mat[i][j]+=(mat[i][k]*b.mat[k][j]+mod)%mod;
ret.mat[i][j]+=mod;
ret.mat[i][j]%=mod;
}
}
}
return ret;
}
ull pow_m(ull a,int n){
ull ret=1,tmp=a;
while(n){
if(n&1)ret*=tmp;
tmp*=tmp;
n>>=1;
}
return ret;
}
Matrix pow_M(Matrix a,ll n){
Matrix ret=Matrix(a.n);
for(int i=0;i<a.n;i++)ret.mat[i][i]=1;
Matrix tmp=a;
while(n){
if(n&1)ret=ret*tmp;
tmp=tmp*tmp;
n>>=1;
}
return ret;
}
};
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll n,m;
while(cin>>n>>m){
mod=m;
Matrix a=Matrix(2);
a.mat[0][0]=4;a.mat[0][1]=1;
a.mat[1][0]=0;a.mat[1][1]=1;
if(n&1){
a=a.pow_M(a,n/2);
cout<<((((a.mat[0][1]*2)%mod)*2%mod)+1)%mod<<endl;
}
else{
a=a.pow_M(a,n/2);
cout<<(a.mat[0][1]*2)%mod<<endl;
}
}
return 0;
}

E.HDU - 4965 Fast Matrix Calculation

题意

题意很简单,给你一个N×K的矩阵A,再给你一个K×N的矩阵B N<=1000,K<=6

1.求出矩阵C=A×B

2.求出矩阵C^n*n

3.求出矩阵C的和

题解

一开始直接模拟,于是很愉快的超时了,发现如果是A×B 是N×N的矩阵1000×1000

于是一个骚操作出现了A×B的N的平方的平方 可以才成A×B×A×B×A…×B 于是可以变成A×(B×A)^(n×n-1)×B 这里B×A是6×6的矩阵速度快的一批;长见识了!

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
50
51
52
53
54
55
56
57
58
59

using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=6;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int (int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
ll x,y;
typedef vector<ll>vec;
typedef vector<vec>mat;
mat mul(mat& A,mat &B){
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();i++)
for(int k=0;k<B.size();k++)
if(A[i][k])
for(int j=0;j<B[0].size();j++)
C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod+mod)%mod;
return C;
}
mat Pow(mat A,ll n){
mat B(A.size(),vec(A.size()));
for(int i=0;i<A.size();i++)B[i][i]=1;
for(;n;n>>=1,A=mul(A,A))
if(n&1)B=mul(B,A);
return B;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll n,k;
while(cin>>n>>k){
if(n==0&&k==0)break;
mat a(n,vec(k));
mat b(k,vec(n));
for(int i=0;i<n;i++)
for(int j=0;j<k;j++)
cin>>a[i][j];
for(int i=0;i<k;i++)
for(int j=0;j<n;j++)
cin>>b[i][j];
mat c=mul(b,a);
ll nn=n*n-1;
c=Pow(c,nn);
a=mul(a,c);
a=mul(a,b);
ll sum=0;
for(int i=0;i<a.size();i++){
for(int j=0;j<a[0].size();j++){
sum+=a[i][j];
}
}
cout<<sum<<endl;
}
return 0;
}

G.UVA - 10689 Yet another Number Sequence

水题不解释了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int t;
cin>>t;
while(t--){
ll n,m,a,b;
cin>>a>>b>>n>>m;
mod=1;
while(m--)mod*=10;
mat aa=mat(2,vec(2));
aa[0][0]=1;aa[0][1]=1;aa[1][0]=1;aa[1][1]=0;
if(n==0){cout<<a%mod<<endl;continue;}
if(n==1){cout<<b%mod<<endl;continue;}
aa=Pow(aa,n-1);
mat bb=mat(2,vec(1));
bb[0][0]=b%mod;bb[1][0]=a%mod;
bb=mul(aa,bb);
cout<<bb[0][0]%mod<<endl;
}

H.UVA - 11149 Power of Matrix

题意

计算矩阵A^1+A^2+A^3+…A^k

题解

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=10;
const int maxn=10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
ll x,y;
typedef vector<ll>vec;
typedef vector<vec>mat;
mat mul(mat& A,mat &B){
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();i++)
for(int k=0;k<B.size();k++)
if(A[i][k])
for(int j=0;j<B[0].size();j++)
C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod+mod)%mod;
return C;
}
mat Pow(mat A,ll n){
mat B(A.size(),vec(A.size()));
for(int i=0;i<A.size();i++)B[i][i]=1;
for(;n;n>>=1,A=mul(A,A))
if(n&1)B=mul(B,A);
return B;
}
mat add(mat& A,mat& B){
mat C(A.size(),vec(A[0].size()));
for(int i=0;i<A.size();i++){
for(int j=0;j<A[0].size();j++){
C[i][j]=(A[i][j]+B[i][j])%mod;
}
}
return C;
}
mat slove(mat& A,ll n){
if(n==1)return A;
mat B=slove(A,n/2);
mat er=Pow(A,n/2);
er=mul(B,er);
mat sum=add(B,er);//B+B*A(1/2)
er=Pow(A,n);
if(n&1)sum=add(sum,er);
return sum;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
ll k;
while(cin>>n>>k){
if(n==0)break;
mat a=mat(n,vec(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
a[i][j]%=mod;
}
}
a=slove(a,k);
for(int i=0;i<n;i++){
for(int j=0;j<n-1;j++){
cout<<a[i][j]<<" ";
}
cout<<a[i][n-1]<<endl;
}
cout<<endl;
}
return 0;
}

I.UVA - 10655 Contemplation! Algebra

题意

给出a+b的值和ab的值,求a^n+b^n的值

题解

令a+b=A,ab=B,S(n)=a^n+b^n。则S(n)=a^n+b^n=(a+b)(a^n-1+b^n-1)-abn-1-an-1b=(a+b)(a^n-1+b^n-1)-ab(a^n-2+b^n-2)=A×S(n-1)-B×S(n-2)  (n≥2)。

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>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
ll mod;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef vector<ll>vec;
typedef vector<vec>mat;
mat mul(mat &A,mat &B){
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();i++)
for(int k=0;k<B.size();k++)
if(A[i][k])
for(int j=0;j<B[0].size();j++)
C[i][j]=C[i][j]+A[i][k]*B[k][j];
return C;
}
mat Pow(mat A,ll n){
mat B(A.size(),vec(A.size()));
for(int i=0;i<A.size();i++)B[i][i]=1;
for(;n;n>>=1,A=mul(A,A))
if(n&1)B=mul(B,A);
return B;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll p,q,n;
while(cin>>p>>q>>n){
mat a(2,vec(2));
a[0][0]=p;a[0][1]=-q;
a[1][0]=1;a[1][1]=0;
if(n==0)cout<<2<<endl;
else if(n==1)cout<<p<<endl;
else{
a=Pow(a,n-1);
mat b(2,vec(1));
b[0][0]=p;b[1][0]=2;
a=mul(a,b);
cout<<a[0][0]<<endl;
}
}
return 0;
}

M.HDU - 4565 So Easy!

题意

a,b,n,m都是整数,Sn向上取整 并且(a-1)^2<b<a^2

题解

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
ll mod;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef vector<ll>vec;
typedef vector<vec>mat;
mat mul(mat &A,mat &B){
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();i++)
for(int k=0;k<B.size();k++)
if(A[i][k])
for(int j=0;j<B[0].size();j++)
C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod+mod)%mod;
return C;
}
mat Pow(mat A,ll n){
mat B(A.size(),vec(A.size()));
for(int i=0;i<A.size();i++)B[i][i]=1;
for(;n;n>>=1,A=mul(A,A))
if(n&1)B=mul(B,A);
return B;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll a,b,n,m;
while(cin>>a>>b>>n>>m){
mod=m;
mat AA=mat(2,vec(2));
AA[0][0]=2*a;AA[0][1]=-(a*a-b);
AA[1][0]=1;AA[1][1]=0;
AA=Pow(AA,n);
cout<<((((AA[1][0]*2)%mod)*a)%mod+(AA[1][1]*2)%mod+mod)%mod<<endl;
}
return 0;
}

R.HDU - 4549 M斐波那契数列

题意

中文题

题解

直接做做不来的,列举几个情况

1
2
3
4
5
6
7
8
0 a
1 b
2 a*b
3 a*b^2
4 a^2*b^3
5 a^3*b^5
6 a^5*b^8
7 a^8*b^13

很容易看出a和b的项数各自符合斐波那契数列 然后可以用矩阵求出各自的项数,再用快速幂求出结果

注意因为这里的项数太大 所以要使用费马小定理/欧拉降幂

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
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
ll x,y;
typedef vector<ll>vec;
typedef vector<vec>mat;
mat mul(mat& A,mat &B,ll mod){
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();i++)
for(int k=0;k<B.size();k++)
if(A[i][k])
for(int j=0;j<B[0].size();j++)
C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod+mod)%mod;
return C;
}
mat Pow(mat A,ll n){
mat B(A.size(),vec(A.size()));
for(int i=0;i<A.size();i++)B[i][i]=1;
for(;n;n>>=1,A=mul(A,A,mod-1))
if(n&1)B=mul(B,A,mod-1);
return B;
}
ll pow_m(ll a,int n){
ll ret=1,tmp=a;
while(n){
if(n&1)ret=(ret*tmp)%mod;
tmp=(tmp*tmp)%mod;
n>>=1;
}
return ret;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll a,b,n;
while(cin>>a>>b>>n){
mat A=mat(2,vec(2));
A[0][0]=1;A[0][1]=1;A[1][0]=1;A[1][1]=0;
if(n==0){cout<<a<<endl;continue;}
if(n==1){cout<<b<<endl;continue;}
mat B=Pow(A,n-2);
ll aa=B[0][0]%(mod-1);
//cout<<"aa="<<aa<<endl;
aa=pow_m(a,aa);
//cout<<"aa="<<aa<<endl;
ll bb=(B[0][0]+B[0][1])%(mod-1);
//cout<<"bb="<<bb<<endl;
bb=pow_m(b,bb);
//cout<<"bb="<<bb<<endl;
cout<<(aa*bb)%mod<<endl;

}
return 0;
}

S.HDU - 4686 Arc of Dream

题意

An Arc of Dream is a curve defined by following function:
img
where
a0 = A0
ai = ai-1×AX+AY
b0 = B0
bi = bi-1×BX+BY
What is the value of AoD(N) modulo 1,000,000,007?

题意太好理解了就不解释了

题解

kuangbin

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
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef vector<ll>vec;
typedef vector<vec>mat;
mat mul(mat &A,mat &B){
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();i++)
for(int k=0;k<B.size();k++)
if(A[i][k])
for(int j=0;j<B[0].size();j++)
C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod+mod)%mod;
return C;
}
mat Pow(mat A,ll n){
mat B(A.size(),vec(A.size()));
for(int i=0;i<A.size();i++)B[i][i]=1;
for(;n;n>>=1,A=mul(A,A))
if(n&1)B=mul(B,A);
return B;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll n,a0,AX,AY,b0,BX,BY;
while(cin>>n){
cin>>a0>>AX>>AY;
cin>>b0>>BX>>BY;
a0%=mod;AX%=mod;AY%=mod;
b0%=mod;BX%=mod;BY%=mod;
mat a=mat(5,vec(5));
a[0][0]=AX*BX%mod;a[0][1]=AX*BY%mod;a[0][2]=AY*BX%mod;a[0][3]=AY*BY%mod;a[0][4]=0;
a[1][0]=0;a[1][1]=AX%mod;a[1][2]=0;a[1][3]=AY%mod;a[1][4]=0;
a[2][0]=0;a[2][1]=0;a[2][2]=BX%mod;a[2][3]=BY%mod;a[2][4]=0;
a[3][0]=0;a[3][1]=0;a[3][2]=0;a[3][3]=1;a[3][4]=0;
a[4][0]=1;a[4][1]=0;a[4][2]=0;a[4][3]=0;a[4][4]=1;
a=Pow(a,n);
/* for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
cout<<a[i][j]<<'t';
}
cout<<endl;
}*/
mat b=mat(5,vec(1));
b[0][0]=a0*b0%mod;b[1][0]=a0%mod;b[2][0]=b0%mod;b[3][0]=1;b[4][0]=0;
b=mul(a,b);
cout<<b[4][0]<<endl;
//cout<<((a[4][0]*a0*b0)%mod+(a[4][1]*a0)%mod+(a[4][2]*b0)%mod+(a[4][3])%mod+mod)%mod<<endl;
}
return 0;
}