poj-3150-Cellular Automation
|
Cellular Automaton
Description A cellular automaton is a collection of cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules that describe the new state of a cell based on the states of neighboring cells. The order of the cellular automaton is the number of cells it contains. Cells of the automaton of order n are numbered from 1 to n. The order of the cell is the number of different values it may contain. Usually, values of a cell of order m are considered to be integer numbers from 0 to m − 1. One of the most fundamental properties of a cellular automaton is the type of grid on which it is computed. In this problem we examine the special kind of cellular automaton — circular cellular automaton of order n with cells of order m. We will denote such kind of cellular automaton as n,m-automaton. A distance between cells i and j in n,m-automaton is defined as min(|i − j|, n − |i − j|). A d-environment of a cell is the set of cells at a distance not greater than d. On each d-step values of all cells are simultaneously replaced by new values. The new value of cell i after d-step is computed as a sum of values of cells belonging to the d-enviroment of the cell i modulo m. The following picture shows 1-step of the 5,3-automaton.  The problem is to calculate the state of the n,m-automaton after k d-steps. Input The first line of the input file contains four integer numbers n, m, d, and k (1 ≤ n ≤ 500, 1 ≤ m ≤ 1 000 000, 0 ≤ d < n⁄2 , 1 ≤ k ≤ 10 000 000). The second line contains n integer numbers from 0 to m − 1 — initial values of the automaton’s cells. Output Output the values of the n,m-automaton’s cells after k d-steps. Sample Input sample input #1 5 3 1 1 1 2 2 1 2 sample input #2 5 3 1 10 1 2 2 1 2 Sample Output sample output #1 2 2 2 2 1 sample output #2 2 0 0 2 2 Source |
|||||||||
| 17861637 | 3150 | Accepted | 408K | 3579MS | G++ | 1036B | 2017-11-19 20:48:11 |
元宝自动机。
经典的矩阵快速计算方法。
将有规律的矩阵简化为向量，由原来的 n^3 复杂度减小到 n^2 。
首先来看一下Sample里的第一组数据。
1 2 2 1 2
经过一次变换之后就成了
5 5 5 5 4
它的原理就是
a0 a1 a2 a3 a4
->(a4+a0+a1) (a0+a1+a2) (a1+a2+a3) (a2+a3+a4) (a3+a4+a0)
如果用矩阵相乘来描述，那就可以表述为1xN和NxN的矩阵相乘，结果仍为1xN矩阵
b = 1 2 2 1 2
a =
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
b * a = 5 5 5 5 4
所以最终结果就是：a * (b^k)
复杂度是n^3logk，过不了
于是我们发现这个矩阵长得很奇葩，每一行都是上一行后移一位得到
所以我们每个矩阵可以变成一行
参考： https://www.cnblogs.com/iwtwiioi/p/3946211.html
// poj-3150
#include <cstdio>
#include <cstring>
const int MAXN = 500 + 10;
long long n, m, d, k, num[MAXN], a[MAXN], b[MAXN], tmp[MAXN], ans[MAXN];
void MultiPle(long long *aa, long long *bb, long long *cc, int len){
for(int i=0; i<len; ++i){
tmp[i] = 0;
for(int j=0; j<len; ++j){
if(i - j >= 0){
tmp[i] += (aa[j] * bb[i - j]) % m;
}else{
tmp[i] += (aa[j] * bb[i - j + n]) % m;
}
tmp[i] %= m;
}
}
for(int i=0; i<len; ++i){
cc[i] = tmp[i];
}
}
int main(){
freopen("in.txt", "r", stdin);
while(scanf("%lld %lld %lld %lld", &n, &m, &d, &k) != EOF){
for(int i=0; i<n; ++i){
scanf("%lld", &num[i]);
}
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for(int i=0; i<=d; ++i){
a[i] = 1;
}
for(int i=n-1; i>n-1-d; --i){
a[i] = 1;
}
b[0] = 1;
while(k){
if(k % 2 == 1){
MultiPle(b, a, b, n);
}
k /= 2;
MultiPle(a, a, a, n);
}
MultiPle(num, b, ans, n );
for(int i=0; i<n-1; ++i){
printf("%lld ", ans[i]);
}
printf("%lld
", ans[n-1] );
}
return 0;
}