ACM 矩阵题目整理

2023-03-14 21:53:42

先从最基础的矩阵快速幂加速递推开始。

HDU 1005 Number Sequence

|f[n-2],f[n-1]|* |0 B| =|f[n-1], B*f[n-2]+A*f[n-1]|=|f[n-1],f[n]|

　　　　　　　 |1 A|

建立矩阵如上然后利用快速幂求解即可。答案是mat[0][1]。

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<set>
#include<string>
#define INF 1000000005
#define LL long long
using namespace std;
;
struct Matrix
{
    int n,m;
    int a[MAXN][MAXN];
    ,)
    {
        n=x;
        m=y;
        memset(a,,sizeof(a));
    }
    Matrix operator * (const Matrix &b)const
    {
        Matrix tmp;
        tmp.clear(n,b.m);
        ; i<n; ++i)
            ; j<b.m; ++j)
                ; k<m; ++k)
                {
                    tmp.a[i][j]+=a[i][k]*b.a[k][j];
                    tmp.a[i][j]%=;
                }
        return tmp;
    }
};
Matrix quickPow(Matrix mat,int n)
{
    Matrix res;
    res.clear(,);
    res.a[][]=res.a[][]=;
    while(n)
    {
        ) res=res*mat;
        mat=mat*mat;
        n=n>>;
    }
    return res;
}
int main()
{
    int A,B,n;
    while(scanf("%d%d%d",&A,&B,&n)!=EOF)
    {
        if(!A&&!B&&!n) break;
        ||n==)
        {
            puts(");
            continue;
        }
        Matrix mat;
        mat.clear(,);
        mat.a[][]=;
        mat.a[][]=B;
        mat.a[][]=;
        mat.a[][]=A;
        Matrix f;
        f.clear(,);
        f.a[][]=;
        f.a[][]=;
        n-=;
        Matrix s=f*quickPow(mat,n);
        printf(][])%);
    }
    ;
}

HDU 4920 Matrix multiplication

矩阵乘法，直接算会超时。由于是模3，所以0很多，也就是稀疏矩阵。可以优化。

参见下文：http://www.cnblogs.com/jackiesteed/articles/2021604.html

#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<string>
#define LL long long
using namespace std;
][],B[][];
][];
int n;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        ; i<=n; ++i)
            ; j<=n; ++j)
            {
                scanf("%d",&A[i][j]);
                A[i][j]%=;
            }
        ; i<=n; ++i)
            ; j<=n; ++j)
            {
                scanf("%d",&B[i][j]);
                B[i][j]%=;
            }
        memset(C,,sizeof(C));
        ; i<=n; ++i)
            ; j<=n; ++j)
            {
                ) continue;
                ; k<=n; ++k)
                    C[i][k]+=A[i][j]*B[j][k];
            }
        ; i<=n; ++i)
        {
            ; j<=n; ++j)
                ) printf();
                );
            printf("\n");
        }
    }
    ;
}

HDU 1575 Tr A

求矩阵的迹。直接快速幂即可。

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<set>
#include<string>
#define INF 1000000005
#define LL long long
using namespace std;
;
struct Matrix
{
    int n,m;
    int a[MAXN][MAXN];
    ,)
    {
        n=x;
        m=y;
        memset(a,,sizeof(a));
    }
    Matrix operator * (const Matrix &b)const
    {
        Matrix tmp;
        tmp.clear(n,b.m);
        ; i<n; ++i)
            ; j<b.m; ++j)
            {
                ; k<b.m; ++k)
                {
                    ==a[i][j]) continue;//优化！
                    tmp.a[i][k]+=a[i][j]*b.a[j][k];
                    tmp.a[i][k]%=;
                }
            }
        return tmp;
    }
    void setOne(int x)
    {
        clear(x,x);
        ; i<x; ++i)
            a[i][i]=;
    }
};
Matrix one;
Matrix quickPow(Matrix mat,int n)
{
    Matrix res=one;
    while(n)
    {
        ) res=res*mat;
        mat=mat*mat;
        n=n>>;
    }
    return res;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        one.setOne(n);
        Matrix mat;
        mat.clear(n,n);
        ;i<n;++i)
            ;j<n;++j)
            scanf("%d",&mat.a[i][j]);
        mat=quickPow(mat,k);
        ;
        ;i<n;++i)
        {
            ans+=mat.a[i][i];
            ans%=;
        }
        printf("%d\n",ans);
    }
    ;
}

HDU 1757 A Simple Math Problem

一个简单的递推，建立矩阵后，快速幂。

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<set>
#include<string>
#define INF 1000000005
#define LL long long
using namespace std;
;
int M;
struct Matrix
{
    int n,m;
    int a[MAXN][MAXN];
    ,)
    {
        n=x;
        m=y;
        memset(a,,sizeof(a));
    }
    Matrix operator * (const Matrix &b)const
    {
        Matrix tmp;
        tmp.clear(n,b.m);
        ; i<n; ++i)
            ; j<b.m; ++j)
            {
                ; k<b.m; ++k)
                {
                    ==a[i][j]) continue;//优化！
                    tmp.a[i][k]+=a[i][j]*b.a[j][k];
                    tmp.a[i][k]%=M;
                }
            }
        return tmp;
    }
    void setOne(int x)
    {
        clear(x,x);
        ; i<x; ++i)
            a[i][i]=;
    }
};
Matrix one;
Matrix quickPow(Matrix mat,int n)
{
    Matrix res=one;
    while(n)
    {
        ) res=res*mat;
        mat=mat*mat;
        n=n>>;
    }
    return res;
}
int main()
{
    int k;
    one.setOne();
    while(scanf("%d%d",&k,&M)!=EOF)
    {
        Matrix mat;
        mat.clear(,);
        ; i<; ++i)
            mat.a[i+][i]=;
        ; i<; ++i)
            scanf(-i][]);
        ) printf("%d\n",k%M);
        else
        {
            Matrix f;
            f.clear(,);
            ; i<; ++i)
                f.a[][i]=i;
            k-=;
            f=f*quickPow(mat,k);
            printf(][]);
        }
    }
    ;
}

UVa 10870 Recurrences

与上面类型相似的题，建立矩阵，再快速幂加速。注意会超int。

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<set>
#include<string>
#define INF 1000000005
#define LL long long
using namespace std;
;
int M;
struct Matrix
{
    int n,m;
    LL a[MAXN][MAXN];
    ,)
    {
        n=x;
        m=y;
        memset(a,,sizeof(a));
    }
    Matrix operator * (const Matrix &b)const
    {
        Matrix tmp;
        tmp.clear(n,b.m);
        ; i<n; ++i)
            ; j<b.m; ++j)
            {
                ; k<b.m; ++k)
                {
                    ==a[i][j]) continue;//优化！
                    tmp.a[i][k]+=a[i][j]*b.a[j][k];
                    tmp.a[i][k]%=M;
                }
            }
        return tmp;
    }
    void setOne(int x)
    {
        clear(x,x);
        ; i<x; ++i)
            a[i][i]=;
    }
};
Matrix one;
Matrix quickPow(Matrix mat,LL n)
{
    Matrix res=one;
    while(n)
    {
        ) res=res*mat;
        mat=mat*mat;
        n=n>>;
    }
    return res;
}
int main()
{
    int d,n;
    while(scanf("%d%d%d",&d,&n,&M)!=EOF)
    {
        if(!d&&!n&&!M) break;
        one.setOne(d);
        Matrix mat;
        mat.clear(d,d);
        ; i<d; ++i)
            mat.a[i+][i]=;
        ; i<d; ++i)
            scanf(-i][d-]);
        Matrix f;
        f.clear(,d);
        ; i<d; ++i)
            scanf(][i]);
        if(n<=d)
            printf(][n-]%M);
        else
        {
            n-=d;
            f=f*quickPow(mat,n);
            printf(][d-]%M);
        }
    }
    ;
}

POJ 3734 Blocks

递推+矩阵快速幂。

设计状态的时候要考虑所有可能的情况，保证无重复无遗漏，再考虑转移。最后用矩阵加速。

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<set>
#include<string>
#define INF 1000000005
#define LL long long
using namespace std;
;
;
struct Matrix
{
    int n,m;
    int a[MAXN][MAXN];
    Matrix(,):n(x),m(y)
    {
        memset(a,,sizeof(a));
    }
    ,)
    {
        n=x;
        m=y;
        memset(a,,sizeof(a));
    }
    Matrix operator * (const Matrix &b)const
    {
        Matrix tmp;
        tmp.clear(n,b.m);
        ; i<n; ++i)
            ; j<b.m; ++j)
            {
                ; k<b.m; ++k)
                {
                    ==a[i][j]) continue;//ÓÅ»¯£¡
                    tmp.a[i][k]+=a[i][j]*b.a[j][k];
                    tmp.a[i][k]%=M;
                }
            }
        return tmp;
    }
    void setOne(int x)
    {
        clear(x,x);
        ; i<x; ++i)
            a[i][i]=;
    }
};
Matrix one;
Matrix quickPow(Matrix mat,int n)
{
    Matrix res=one;
    while(n)
    {
        ) res=res*mat;
        mat=mat*mat;
        n=n>>;
    }
    return res;
}
int main()
{
    one.setOne();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        Matrix mat(,);
        mat.a[][]=,mat.a[][]=,mat.a[][]=;
        mat.a[][]=,mat.a[][]=,mat.a[][]=;
        mat.a[][]=,mat.a[][]=,mat.a[][]=;
        Matrix f(,);
        f.a[][]=;
        Matrix ans=f*quickPow(mat,n);
        printf(][]);
    }
    ;
}

POJ 3420 Quad Tiling

这个题的关键是在求递推式。

设dp[i]表示填满前i个方块的种数。那么从dp[i-1]转移有1种情况，从dp[i-2]转移有4种情况，在之后从dp[i-a]，如果a是奇数有2种情况，a是偶数有3种情况。

这样最终化简得dp[i]=dp[i-1]+5dp[i-2]+dp[i-3]-dp[i-4]

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<set>
#include<string>
#define INF 1000000005
#define LL long long
using namespace std;
;
int M;
struct Matrix
{
    int n,m;
    int a[MAXN][MAXN];
    Matrix(,):n(x),m(y)
    {
        memset(a,,sizeof(a));
    }
    ,)
    {
        n=x;
        m=y;
        memset(a,,sizeof(a));
    }
    Matrix operator * (const Matrix &b)const
    {
        Matrix tmp;
        tmp.clear(n,b.m);
        ; i<n; ++i)
            ; j<b.m; ++j)
            {
                ; k<b.m; ++k)
                {
                    ==a[i][j]) continue;//优化
                    tmp.a[i][k]+=a[i][j]*b.a[j][k];
                    tmp.a[i][k]%=M;
                }
            }
        return tmp;
    }
    void setOne(int x)
    {
        clear(x,x);
        ; i<x; ++i)
            a[i][i]=;
    }
};
Matrix one;
Matrix quickPow(Matrix mat,int n)
{
    Matrix res=one;
    )
    {
        ) res=res*mat;
        mat=mat*mat;
        n=n>>;
    }
    return res;
}
int main()
{
    int n;
    one.setOne();
    while(scanf("%d%d",&n,&M)!=EOF)
    {
        if(!n&&!M) break;
        Matrix mat(,);
        ; i<; ++i)
            mat.a[i+][i]=;
        mat.a[][]=-,mat.a[][]=,mat.a[][]=,mat.a[][]=;
        Matrix f(,);
        f.a[][]=,f.a[][]=,f.a[][]=,f.a[][]=;
        ) printf(][n]%M);
        else
        {
            n-=;
            Matrix s=f*quickPow(mat,n);
            printf(][]);
        }
    }
    ;
}

ZOJ 3690 Choosing number

a[i]表示第i个人选小于等于k的数字的合法种数，a[i]=(k-1)*a[i]+k*b[i]

b[i]表示第i个人选大于等于k的数字的合法种数，b[i]=(m-k)*a[i]+(m-k)*b[i]

a[0]=0,b[0]=1,答案是a[n]+b[n]

建立矩阵快速幂计算即可。

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<set>
#include<string>
#define INF 1000000005
#define LL long long
using namespace std;
;
;
struct Matrix
{
    int n,m;
    LL a[MAXN][MAXN];
    Matrix(,):n(x),m(y)
    {
        memset(a,,sizeof(a));
    }
    ,)
    {
        n=x;
        m=y;
        memset(a,,sizeof(a));
    }
    Matrix operator * (const Matrix &b)const
    {
        Matrix tmp;
        tmp.clear(n,b.m);
        ; i<n; ++i)
            ; j<m; ++j)
            {
                ; k<b.m; ++k)
                {
                    ==a[i][j]) continue;//优化！
                    tmp.a[i][k]+=a[i][j]*b.a[j][k];
                    tmp.a[i][k]%=M;
                }
            }
        return tmp;
    }
    void setOne(int x)
    {
        clear(x,x);
        ; i<x; ++i)
            a[i][i]=;
    }
};
Matrix one;
Matrix quickPow(Matrix mat,int n)
{
    Matrix res=one;
    while(n)
    {
        ) res=res*mat;
        mat=mat*mat;
        n=n>>;
    }
    return res;
}
int main()
{
    int n,m,k;
    one.setOne();
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        Matrix mat(,);
        mat.a[][]=k-,mat.a[][]=k;
        mat.a[][]=m-k,mat.a[][]=m-k;
        Matrix f(,);
        f.a[][]=,f.a[][]=;
        Matrix s=quickPow(mat,n)*f;
        printf(][]+s.a[][])%M);
    }
    ;
}

码农公寓

相关文章