POJ 3150 Cellular Automaton 题解

题目大意:给出一个包含\(n(n\le 500)\)个点的环形数字串,每单位时间后每一位上的数字变为与它距离不超过\(d(d\le \frac{n}{2})\)的位上各个数字之和\(mod\ m\),问\(k(k\le 10,000,000)\)单位时间后各个位上的数字变成了什么。

考虑矩阵乘法

很容易写出转移矩阵(下图为\(n=5,d=1\)时的转移矩阵)

\(\begin{matrix}1&1&0&0&1\\1&1&1&0&0\\0&1&1&1&0\\0&0&1&1&1\\1&0&0&1&1\end{matrix}\)

设初始矩阵(即\(1\times n\)的一个矩阵,包含一行初始的数)为\(a\),转移矩阵为\(b\),那么答案为\(a\times b^k\)。用矩阵快速幂,复杂度为\(O(n^3\ log\ k)\),过不了。

我们发现,转移矩阵除了第一行,都是由上一行循环右移一位得到的。这样的矩阵称为循环矩阵。有一个很重要的性质:两个循环矩阵相乘依然是循环矩阵。那么我们算矩阵乘法时只需要算出第一行,第\(i+1\)行由第\(i\)行递推得到就行了。

矩阵乘法复杂度降为\(O(n^2)\),总复杂度\(O(n^2\ log\ k)\),可以过了

#include<cstdio>
#include<cstring>
const int MAXN = 500 + 5;
typedef long long LL;

struct Matrix {
	int n, m;
	int A[MAXN][MAXN];
	Matrix(int n, int m):n(n), m(m) { memset(A, 0, sizeof A); }
};

int MOD;
Matrix operator*(Matrix A, Matrix B) {
	int n = A.n, m = A.m, p = B.m;
	Matrix ans(n, p);
	if(n == m && n == p) {
		for (int j = 0; j < p; ++j)
			for (int k = 0; k < m; ++k)
				(ans.A[0][j] += (LL)A.A[0][k] * B.A[j][k] % MOD) %= MOD;
		for (int i = 1; i < n; ++i)
			for (int j = 0; j < p; ++j) {
				if (j == 0) ans.A[i][j] = ans.A[i - 1][n - 1];
				else ans.A[i][j] = ans.A[i - 1][j - 1];
			}
	}
	else {
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < p; ++j)
				for(int k = 0; k < m; ++k)
					(ans.A[i][j] += (LL)A.A[i][k] * B.A[k][j] % MOD) %= MOD;
	}
	return ans;
}

Matrix base(int n) {
	Matrix ans(n, n);
	for (int i = 0; i < n; ++i) ans.A[i][i] = 1;
	return ans;
}

Matrix Mpow(Matrix A, int b) {
	Matrix ans = base(A.n);
	for(; b; b >>= 1, A = A * A)
		if (b & 1) ans = ans * A;
	return ans;
}

int n, d, k;
int main() {
	scanf("%d%d%d%d", &n, &MOD, &d, &k);
	Matrix A(n, n);
	for (int i = 0; i < n; ++i) {
		for (int j = i; j <= i + d; ++j)
			A.A[i][j % n] = 1;
		for (int j = i - 1; j >= i - d; --j)
			A.A[i][(j + n) % n] = 1;
	}
	A = Mpow(A, k);
	Matrix B(1, n);
	for (int i = 0; i < n; ++i) scanf("%d", &B.A[0][i]);
	B = B * A;
	for (int i = 0; i < n; ++i)
		printf("%d%c", B.A[0][i], i == n - 1 ? '\n' : ' ');
	return 0;
}

 

发表评论

电子邮件地址不会被公开。