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

时间：2022-05-31 04:14:57

layout: post

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

author: "luowentaoaa"

catalog: true

tags:

mathjax: true

- kuangbin

- 矩阵

传送门

A.CodeForces - 450B Jzzhu and Sequences

题意

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

题解

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

#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;

}
#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[i][j]=A[i-1][j]+A[i][j-1]
\]

题解

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

\[A[a][b]=A[a-1][b]+A[a][b-1]\\=A[a][b-1]+A[a-1][b-1]+A[a-2][b]\\...
\]

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

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

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

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

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

#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)所以很可能会超时，所以只能用加速算法

现在我们考虑只有偶数项

\[A[n]=A[n-1]*2;\\A[n-1]=A[n-2]*2+1; \\A[n]=4*A[n-2]+2
\]

如果是偶数就直接求n/2次方，如果是奇数就求出二次方后再*2+1；

#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的矩阵速度快的一批；长见识了！

#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

水题不解释了

    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

题意

计算矩阵A1+A2+A3+...Ak

题解

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

#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的值，求an+bn的值

题解

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

#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!

题意

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

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

题解

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

#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斐波那契数列

题意

中文题

题解

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

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的项数各自符合斐波那契数列 然后可以用矩阵求出各自的项数，再用快速幂求出结果

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

#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:

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

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带你飞」专题十九 矩阵

#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;

}

相关文章