UVA 1386 - Cellular Automaton
题意：给定一个n格的环，如今有个距离d。每次变化把环和他周围距离d以内的格子相加，结果mod m，问经过k次变换之后，环上的各个数字
思路：矩阵非常好想，每一个位置相应周围几个位置为1。其余位置为0，可是这个矩阵有500。有点大，直接n^3去求矩阵不太合适。然后观察发现这个矩阵是个循环矩阵，循环矩阵相乘的话，仅仅须要保存一行就可以。然后用n^2的时间就足够计算了
代码：
#include <stdio.h>
#include <string.h> const int N = 505; long long n, m, d, k, a[N]; struct mat {
long long v[N];
mat() {memset(v, 0, sizeof(v));}
mat operator * (mat c) {
mat ans;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ans.v[i] = ((ans.v[i] + v[j] * c.v[(j - i + n) % n]) % m + m) % m;
}
}
return ans;
}
}; mat pow_mod(mat x, long long k) {
if (k == 1) return x;
mat sb = x * x;
mat ans = pow_mod(sb, k>>1);
if (k&1) ans = ans * x;
return ans;
} int main() {
while (~scanf("%lld%lld%lld%lld", &n, &m, &d, &k)) {
mat start;
for (int i = 0; i <= d; i++)
start.v[i] = 1;
for (int i = n - 1; i > n - 1 - d; i--)
start.v[i] = 1;
start = pow_mod(start, k);
for (int i = 0; i < n; i++)
scanf("%lld", &a[i]);
for (int i = 0; i < n; i++) {
long long ans = 0;
for (int j = 0; j < n; j++)
ans = ((ans + a[j] * start.v[(j - i + n) % n]) % m + m) % m;
printf("%lld%c", ans, (i == n - 1 ? '\n' : ' '));
}
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。