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

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

Solution:

#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;
}


#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;
}