题目链接:uva 1386 - Cellular Automaton
题目大意:一个细胞自动机,有n个格子,每个格子的取值为0~m-1。给定距离d,每次操作后每个格子的值将变为到它距离不超过d的所有格子在操作之前的值之和除以m的余数。
解题思路:矩阵快速幂,因为矩阵是循环矩阵,所以记录并处理第一行即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 505;
int N, M, D, K;
struct Mat {
ll arr[maxn];
};
Mat ceil, x;
Mat mul_mat (const Mat& a, const Mat& b) {
Mat ans;
memset(ans.arr, 0, sizeof(ans.arr));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
ans.arr[i] = (ans.arr[i] + a.arr[j] * b.arr[(i-j+N)%N]) % M;
}
return ans;
}
void pow_mat (int n) {
Mat ans = x;
while (n) {
if (n&1)
ans = mul_mat(ans, x);
x = mul_mat(x, x);
n >>= 1;
}
x = ans;
}
int main () {
while (scanf("%d%d%d%d", &N, &M, &D, &K) == 4) {
for (int i = 0; i < N; i++)
scanf("%lld", &ceil.arr[i]);
memset(x.arr, 0, sizeof(x.arr));
for (int i = -D; i <= D; i++)
x.arr[(i+N)%N] = 1;
pow_mat(K-1);
for (int i = 0; i < N; i++) {
if (i)
printf(" ");
ll ret = 0;
for (int j = 0; j < N; j++)
ret = (ret + ceil.arr[j] * x.arr[(j-i+N)%N]) % M;
printf("%lld", ret);
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
matlab 元胞自动机计算车道被占用仿真情况
2007年美国大学生数学建模竞赛,MCM优秀论文。 A Cellular Automaton Approach to Optimising Aircraft Boarding Time
celluler automation 的程序,有助于初学者了解什么是元胞自动机。图文并茂。学习手册式的好程序
自动元胞机,可以模拟仿真天气、洪水、 交通 、网络舆情等情况。
Expression and sub-cellular localization of leucine-rich repeats and immunoglobulin-like domain 1 is related to antioxidant enzymes in human ependymoma and oligodendroglioma,易伟,刘琳,The current ...
快速开始 大多数(如果不是全部)程序都可以使用大多数C ++编译器来构建,因此这里没有什么特别的。 指示 游戏人生: 'e' ->退出 'r' ->重新启动(创建新的随机板) Any other key ->“模拟”中的前移 Rule101 / ...
Qualcomm-Cellular-V2X-AESIN-Oct-2016
us-18-Shattuck-Snooping-on-Cellular-Gateways-and-Their-Critical-Role-in-ICS 解决方案 威胁情报 安全研究 应急响应 安全架构
Final-report-for-5GAA-on-cellular-V2X-socio-economic-benefits-051217_FINAL.pdf
Qualcomm-Cellular-V2X-AESIN-Oct-2016.pptx
Qualcomm-Cellular-V2X-AESIN-Oct-2016.pdf
三个简单的c语言元胞自动机代码,cellular automaton
数学建模-cellular programm.zip
数学建模-cellular paradingms.zip
A Modified Cellular Automaton Model for the Simulation of Dendritic Growth in Solidification,李青松,,A modified cellular automaton model (mCA) was developed in order to simulate the evolution of ...
关于Qualcomm-Cellular-V2X-AESIN-Oct-2016的介绍说明.rar
数学建模-Cellular Automata in Matlab.zip