UVa

Luogu

Vjudge

分析

直接暴力求的话是 $O(n^3k\log k)$ 或者 $O(n^3k)$ 的,显然过不去。

可以考虑分治。令

$$ F_i=\sum_{i=1}^iA^i $$

容易得到

$$ F_i=\begin{cases}(I+A^{i/2})F_{i/2},&i\bmod 2=0\\A^i+F_{i-1},&i\bmod 2=1\end{cases} $$

递归计算即可。

注意一些比较坑的地方:输入的数会爆 int 、卡输出。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=40+10;
const int mod=10;

int n,k;

struct Matrix {
    int s[N][N];
    inline void init() {
        for (re int i=0;i<n;++i)
            for (re int j=0;j<n;++j) s[i][j]=0;
    }
    int* operator [](int i) { return s[i]; }
} A,I,pw[20];
Matrix operator +(Matrix a,Matrix b) {
    Matrix c; c.init();
    for (re int i=0;i<n;++i)
        for (re int j=0;j<n;++j)
            c[i][j]=(a[i][j]+b[i][j])%mod;
    return c;
}
Matrix operator *(Matrix a,Matrix b) {
    Matrix c; c.init();
    for (re int i=0;i<n;++i)
        for (re int j=0;j<n;++j) {
            for (re int k=0;k<n;++k) c[i][j]+=a[i][k]*b[k][j];
            c[i][j]%=mod;
        }
    return c;
}
inline Matrix qpow(Matrix a,int b) {
    Matrix c; c.init();
    for (re int i=0;i<n;++i) c[i][i]=1;
    for (re int i=0;b;b>>=1,++i) if (b&1) c=c*pw[i];
    return c;
}

inline Matrix solve(int k) {
    if (k==1) return A;
    if (k&1) return qpow(A,k)+solve(k^1);
    else return (qpow(A,k>>1)+I)*solve(k>>1);
}

int main() {
    while (n=read()) { k=read();
        I.init(); for (re int i=0;i<n;++i) I[i][i]=1;
        for (re int i=0;i<n;++i)
            for (re int j=0;j<n;++j) A[i][j]=read()%mod;
        pw[0]=A; for (re int i=1;i<20;++i) pw[i]=pw[i-1]*pw[i-1];
        Matrix B=solve(k);
        for (re int i=0;i<n;++i)
            for (re int j=0;j<n;++j)
                printf("%d%c",B[i][j]," \n"[j==n-1]);
        puts("");
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 53 PM