UVA 1386 - Cellular Automaton

option=com_onlinejudge&Itemid=8&page=show_problem&category=489&problem=4132&mosmsg=Submission+received+with+ID+13911770" target="_blank" style="">题目链接

题意：给定一个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;

}