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

Diposting di | Edited on

传送门

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
#include<bits/stdc++.h>
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 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);}
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
#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){
    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
#include<bits/stdc++.h>
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 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);}
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 i=0;i<n+2;i++){
                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
#include<bits/stdc++.h>
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 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 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
#include<bits/stdc++.h>
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 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;
}
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;
}