首页 > 代码库 > UVA - 1386 Cellular Automaton
UVA - 1386 Cellular Automaton
题目:点击打开链接
题意:一个细胞自动机包含n个格子,每个格子的值都会变成它距离不超过d的所有格子的值,求最后的结果
思路:这个是循环矩阵,可以用O(n^2)的时间过掉
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int maxn = 505; int n, m, d, k; ll ans[maxn], matrix[maxn]; ll c[maxn+5]; void mul(ll a[], ll b[]) { memset(c, 0, sizeof(c)); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) c[i] += a[j] * b[(i-j+n) % n]; for (int i = 0; i < n; i++) b[i] = c[i] % m; } int main() { while (scanf("%d%d%d%d", &n, &m, &d, &k) != EOF) { memset(ans, 0, sizeof(ans)); memset(matrix, 0, sizeof(matrix)); for (int i = 0; i < n; i++) cin>>ans[i]; matrix[0] = 1; for (int i = 1; i <= d; i++) matrix[i] = matrix[n - i] = 1; while (k) { if (k & 1) mul(matrix, ans); mul(matrix, matrix); k >>= 1; } for (int i = 0; i < n - 1; i++) printf("%lld ", ans[i]); printf("%lld\n", ans[n-1]); } return 0; }
UVA - 1386 Cellular Automaton
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。