Poj 3150 Cellular Automaton

题解

---

提交地址：https://vjudge.net/problem/POJ-3150

slove

将 $t$ 次操作后的各格子写成矩阵 $v_t$, 那么 $v_{t+1}$ 的每一维都是 $v_t$ 中的各

维的线性组合，可以利用矩阵乘法，设 $v_{t+1} = Av_t$, 当 $d = 1$ 时，有

$$A = \left[ \begin{matrix} 1 & 1 & 0 & \dots & 0 & 1 \\ 1 & 1 & 1 & 0 & \dots & 0 \\ 0 & 1 & 1 & 1 & 0 & \dots \\ \dots & 0 & 1 & 1 & 1 & 0 \\ 1 & \dots & 0 & 0 & 1 & 1 \\ 1 & 1 & \dots & 0 & 0 & 1 \\ \end{matrix} \right]$$

最终答案 $v_k = A^kv_0$, $v_0$ 为初始矩阵，时间复杂度为 $O(n^3logk)$,显然这样的

时间复杂度是无法承受的，观察矩阵 $A$, $A$ 的一个特征是知道该矩阵的第一行就可以知

道该矩阵，这是一个循环矩阵,循环矩阵的矩阵乘法的时间复杂度为 $O(n^2logk)$,这样的时

间复杂度是可以接受的。
这里做矩阵乘法时运用数组的 $0$ 位置方便理解。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
const int N = 510;
#define LL long long
LL A[N], B[N], C[N], T[N];
int n, M, d, k;
void Mul(LL *a, LL *b, LL *c) {
    memset(T, 0, sizeof T);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++) {
            if(i - j >= 0) T[i] = (T[i] + (a[j] * b[i - j]) % M) % 
M;
            else T[i] = (T[i] + (a[j] * b[i - j + n]) % M) % M; 
        }
    for(int i = 0; i < n; i ++) c[i] = T[i];
}
void Ksm() {
    while(k) {
        if(k & 1) Mul(B, A, B); // B = B * A;
        Mul(A, A, A); // A = A * A;
        k >>= 1;
    }
}
int main() {
    std:: cin >> n >> M >> d >> k;
    for(int i = 0; i < n; i ++) std:: cin >> C[i];
    for(int i = 0; i <= d; i ++) A[i] = 1;
    for(int i = n - 1; i >= n - d; i --) A[i] = 1;
    B[0] = 1;
    Ksm();  
    Mul(B, C, C);
    for(int i = 0; i < n; i ++) std:: cout << C[i] << " ";
    return 0;
}