[原创]UVA 1386 cellular automaton [循环矩阵+矩阵快速幂]【数学】

2016-09-01 14:02:59 Tabris_ 阅读数：1031

博客爬取于2020-06-14 22:43:33
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52399129

------------------------------------.
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 denvironment
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 input file contains several test cases, each of them consists of two lines, as described below.
The first line of the input contains four integer numbers n, m, d, and k (1 ≤ n ≤ 500, 1 ≤ m ≤
1000000, 0 ≤ d < n
2
, 1 ≤ k ≤ 10000000). The second line contains n integer numbers from 0 to m − 1
— initial values of the automaton’s cells.
Output
For each test case, write to the output, on a line by itself, the values of the n, m-automaton’s cells after
k d-steps.
Sample Input
5 3 1 1
1 2 2 1 2
5 3 1 10
1 2 2 1 2
Sample Output
2 2 2 2 1
2 0 0 2 2

------------------------------------------------.
题目大意 :
就是有一个N这么大的环现在有这样的操作每次选取每个数及其左右d个距离内的所有数的和对m取模之后作为这个数的新值问你K次操作后每个数都是多少

解题思路 :
首先根据题中的图片观察了一下发现这道题用矩阵快速幂能够解决
以题目图片为例能构造出如下的矩阵
[1 1 0 0 1] 这 [1] = [2]
[1 1 1 0 0] 里 [2] = [2]
[0 1 1 1 0] 是 [2] = [2]
[0 0 1 1 1] 乘 [1] = [2]
[1 0 0 1 1] 号 [2] = [1]

然后写了一发矩阵快速幂
写完了发现程序根本运行不了
找了N久BUG 最后在Q巨的指导下才知道因为数组太大500*500 导致爆栈了
然后把函数改成引用就能运行了但是还是不能A掉题

然后又找了N久的BUG 换了下思路发现越来越乱

最后看了一波题解才知道(如下)这玩意叫做循环矩阵
[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]

它的性质可以看着篇文章后面的部分目录里找矩阵快速幂就行了
http://blog.csdn.net/qq_33184171/article/details/51488462

然后终于优化到了N^2
结果最后的结果莫名的PE PE PE!!! PE 了5 发我也是醉了最醉了的是到最后我也没明白为什么PE
然后找了一发大神的代码直接AC了。。。
格式没问题啊，，，

然后就没有然后了这题做的太闹心了在群里问问题的时候还被菊菊们讽刺了一波。。。

算了最后附上本题代码
-------------------------.

# 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;
}