题解 UVA11149 【Power of Matrix】

泠小毒 · 2019-04-22 11:48:50 · 题解

Power of Matrix

给一个n*n的矩阵A,求A^1+A^2+……+A^k

输出所得矩阵的个位

广告插入

在我的博客里看题解使用效果更佳哦QwQ

慕容琳的后花园

解法

个位就是将mod设为10

如果用矩阵快速幂暴力求解，复杂度是n^3×k×log(k)，显然无法接受

用到分治的思想，如果k是偶数，原式等同于(1+A^(k/2))×(A^1+A^2+……+A^(k/2))

如果k是奇数，原式等同于A+A×(A^1+A^2+……+A^(k-1))

显然可以用这个分治的方法达到log(k)的复杂度，所以总的复杂度是n^3×log(k)

ac代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m=10,kk;
struct node{int a[50][50];}f[50],ans;
inline node operator + (const node &x,const node &y)
{
    node res;
    memset(res.a,0,sizeof(res.a));
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)res.a[i][j]=(x.a[i][j]+y.a[i][j])%m;
    return res;
}
inline node operator * (const node &x,const node &y)
{
    node res;
    memset(res.a,0,sizeof(res.a));
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)
        res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j]%m)%m;
    return res;
}
inline void init(int x)
{
    int cnt=1;
    for(int i=0;cnt<=x;i++,cnt<<=1)f[i+1]=f[i]*f[i];
}
//预处理出快速幂时用到的那些玩意
inline node power(int x)
{
    node res;
    memset(res.a,0,sizeof res.a);
    for(int i=1;i<=n;i++)res.a[i][i]=1;
    int cnt=0;
    while(x)
    {
        if(x&1)res=res*f[cnt];
        x>>=1,cnt++;
    }
    return res;
}
inline node solve(int x)
{
    if(x==1)return f[0];
    node p=solve(x>>1);
    p=p+p*power(x>>1);
    if(x&1)p=p+power(x);
    return p;
}
inline void print(const node &ans)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<n;j++)printf("%lld ",ans.a[i][j]%m);
        printf("%lld\n",ans.a[i][n]%m);
    }
    puts("");//这道题输出好坑，气哭o(╥﹏╥)o
}
signed main()
{
    while(cin>>n>>kk&&n)
    {
        memset(f,0,sizeof(f)),memset(ans.a,0,sizeof(ans.a));
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&f[0].a[i][j]);
        init(kk),print(solve(kk));
    }
    return 0;
}