【UVA-11149】Power of Matrix【矩阵快速幂】

【UVA-11149】Power of Matrix【矩阵快速幂】

问题链接:https://vjudge.net/problem/UVA-11149

Solution:

二分,对于偶数k,表达式

\(A + A^2 + A^3 + … + A^k = (A + A^2 + … + A^{k / 2})(E + A^{k / 2})\)

当k是奇数的时候,上式k / 2向下取整,并且上式在右侧补加\(A ^ k\)项。

递归处理就好。

需要注意的是,n = 0结束,不一定会有k = 0输入。

输入不一定只有一位,要对输入先取模,不然会WA。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int MOD = 10;
const int LIM = 40 + 10;
struct Matrix {
    int v[LIM][LIM];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}};
        ret.size = size;
        for (int i = 0; i < size; i++) {
            for (int k = 0; k < size; k++) {
                if (v[i][k])
                    for (int j = 0; j < size; j++) {
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
                    }
            }
        }
        return ret;
    }
    Matrix operator + (const Matrix & m) const {
        Matrix ret = {{0}};
        ret.size = size;
        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
                ret.v[i][j] = (v[i][j] + m.v[i][j]) % MOD;
        return ret;
    }
};
int n;
Matrix iden, base;

inline void init() {
    memset(&iden, 0, sizeof iden);
    for (int i = 0; i < n; i++) iden.v[i][i] = 1;
    iden.size = n;
    memset(&base, 0, sizeof base);
    base.size = n;
}

Matrix fastPow(int p, Matrix m) {
    Matrix ret = {{0}};
    ret.size = m.size;
    for(int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret = ret * m;
        if (p) m = m * m;
        p >>= 1;
    }
    return ret;
}

Matrix binarySum(int k) {
    if (k == 1) return base;
    else if (k & 1) return binarySum(k >> 1) * (iden + fastPow(k >> 1, base)) + fastPow(k, base);
    else return binarySum(k >> 1) * (iden + fastPow(k >> 1, base));
}

int main() {
    int k;
    while (~scanf("%d", &n) && n) {
        scanf("%d", &k);
        init();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                scanf("%d", &base.v[i][j]);
                base.v[i][j] %= MOD;
            }
        Matrix ans = binarySum(k);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) putchar(' ');
                printf("%d", ans.v[i][j]);
            }
            putchar('\n');
        }
        putchar('\n');
    }
    return 0;
}