【UVA-1386】Cellular Automaton【循环矩阵的矩阵快速幂】

【UVA-1386】Cellular Automaton【循环矩阵的矩阵快速幂】

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

Solution:

这道题的材料很有意思,是关于元胞自动机的【说到元胞自动机自然能够想到那个很有意思的康威的生命游戏 (Conwey’s Game of LIfe)了】,不过。。和这道题关系不大。

元胞自动机,给定一个演化规则,每个单位时间将根据演化规则更新所有的单元,这道题的演化规则就是将每个单元更新为在d-enviroment【也就是在这个环上对于每个单元的距离小于等于d的“邻居”了】之内的数量和,使用矩阵快速幂来解决。

但是。。。n最大是500,事情显然没有顺利到直接就可以解决,遇到两个问题:\(n^3\)复杂度会超时,以及500*500的long long矩阵能不能开成都是个问题。

这时我们注意到这道题的变换矩阵是一个循环矩阵,循环矩阵与循环矩阵相乘仍然是一个循环矩阵,利用这个性质,我们可以只维护一行的数据,同时将空间由\(O(n^2)\)降到\(O(n)\)以及时间由\(O(n^3)\)降到\(O(n^2)\),具体做法我们可以通过写出矩阵,来观察一下这个循环矩阵列上的元素能够对应到哪一行。

如果还不放心可以写个小demo试验一下:

#include <iostream>


using namespace std;

struct Matrix {
    int v[10];
    int size;
    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] += v[j] * m.v[(size - i + j) % size];
            }
        }
        return ret;
    }
};

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

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int n, k;
    while (cin >> n && n) {
        Matrix input;
        input.size = n;
        for (int i = 0; i < n; i++)
            cin >> input.v[i];
        while (cin >> k && k) {
            Matrix output = fastPow(k, input);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (j) cout << ' ';
                    cout << output.v[(n - i + j) % n];
                }
                cout << endl;
            }
        }
    }
    return 0;
}

下面是AC的代码:

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

using namespace std;

typedef long long LL;
int n, mod, d, k;
const int LIM = 500 + 10;
struct Matrix {
    LL v[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++) {
                ret.v[i] = (ret.v[i] + v[k] * m.v[(size - i + k) % size]) % mod;
            }
        }
        return ret;
    }
};
Matrix build() {
    Matrix ret = {{0}};
    ret.size = n;
    for (int i = 0; i <= d; i++)
        ret.v[i] = ret.v[(n - i) % n] = 1;
    return ret;
}
Matrix fastPow(int p, Matrix m) {
    Matrix ret = {{0}};
    ret.size = m.size;
    ret.v[0] = 1;
    while (p) {
        if (p & 1) ret = ret * m;
        p >>= 1;
        if (p) m = m * m;
    }
    return ret;
}
LL input[LIM], output[LIM];

int main() {
    while (~scanf("%d%d%d%d", &n, &mod, &d, &k)) {
        memset(output, 0, sizeof output);
        for (int i = 0; i < n; i++)
            scanf("%d", &input[i]);
        Matrix trans = build();
        trans = fastPow(k, trans);
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                output[i] = (output[i] + trans.v[(n - i + k) % n] * input[k]) % mod;
            }
        }
        for (int i = 0; i < n; i++) {
            if (i) putchar(' ');
            printf("%d", output[i]);
        }
        putchar('\n');
    }
    return 0;
}

注意:如果这题数组开int会WA。