BZOJ2510: 弱题（循环矩阵+矩阵快速幂）

95 阅读 0 评论 63 点赞

我是靠谱客的博主温暖眼神，最近开发中收集的这篇文章主要介绍BZOJ2510: 弱题（循环矩阵+矩阵快速幂），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

大神题解

循环矩阵相乘还是循环矩阵，所以每次乘法求第一行就行了，时间复杂度 $O(n^2log K)$

（代码XJB写的。）

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();int i=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=getchar();}
    return i*f;
} 
const int Maxn=1e3+50; 
int n,m,t;
double e[Maxn][Maxn],c[Maxn][Maxn],(*now)[Maxn]=e,(*now2)[Maxn]=c,rest[Maxn][Maxn],res2t[Maxn][Maxn],(*nowres)[Maxn]=rest,(*nowres2)[Maxn]=res2t;
double a[Maxn];
inline void mul(){
    for(int i=1;i<=n;i++){
        double res=0.0;
        for(int k=1;k<=n;k++)
        res+=now[1][k]*now[k][i];
        now2[1][i]=res;
    }
    for(int j=2;j<=n;j++)
        for(int k=1;k<=n;k++)
            now2[j][k]=now2[j-1][(k-1)?(k-1):n];
    swap(now,now2); 
}
inline void mul2(){
    for(int i=1;i<=n;i++){
        double res=0.0;
        for(int k=1;k<=n;k++)
        res+=nowres[1][k]*now[k][i];
        nowres2[1][i]=res;
    }
    for(int j=2;j<=n;j++)
        for(int k=1;k<=n;k++)
            nowres2[j][k]=nowres2[j-1][(k-1)?(k-1):n];
    swap(nowres,nowres2); 
}
int main(){
    n=read();m=read();t=read();
    for(int i=1;i<=n;i++)
        now[i][i]=-1.0/m+1.0,now[(i-1?i-1:n)][i]=1.0/m,nowres[i][i]=1.0;
    for(;t;t>>=1,mul()){
        if(t&1)mul2();
    }
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++){
        double ans=0;
        for(int j=1;j<=n;j++){
            ans+=a[j]*nowres[j][i];
        }
        printf("%.3fn",ans);
    }
}