poj3150-Cellular Automaton（矩阵优化）

poj3150--Cellular Automaton（矩阵优化）

题目链接：点击打开链接

题目大意：有n个数围成一个环，现在有一种变换，将所有距离第i(1<=i<=n)个数小于等于d的数加起来，对m取余，现在要求将所有的数都变换k次，得到的n个数的值。

一看到那么多数字同时变换，还要变换那么多次，首先想到了用矩阵相乘表示变换后的结果，然后用矩阵快速幂来快速计算，事实告诉我想简单了，，，（PS：一直到敲完才发现，数据太大，根本无法编译）。

可以用一组样例解释怎么做：

样例1

5 3 1 1
1 2 2 1 2

给出了5个数。a[1 2 2 1 2]，那么求一次变换后的结果就是a1+a2+a5，a1+a2+a3，a2+a3+a4，a3+a4+a5，a4+a5+a1,然后对5个数取余，这样就可以看出相乘的矩阵

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

最终矩阵是这样的，经过k次变换，只要让原始数据乘以k次这个矩阵就可以，但是n的大小是500，复杂度是n*n*nlog(m),一定会超时，而且内存放不下。

最后发现，对于每一行来说，值是在不断的移动，每次都移动1个格，所以我们可以可以可以只计算一行或者一列，在用到其它行(列)的时候，有计算的这个行(列)进行推导，就可以计算出结果。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;
#define LL __int64
#pragma comment(linker, "/STACK:102400000,102400000")
struct node{
    LL a[510] ;
}p , q ;
LL a[510] , n , m , d , mod , ans[510] ;
node mul(node p,node q) {
    node s ;
    int i , j , k , l ;
    for(i = 1 ; i <= n ; i++) {
        s.a[i] = 0 ;
        j = i ;
        for(k = 0 ; k < n ; k++) {
            l = j+k > n ? j+k-n : j+k ;
            s.a[i] = (s.a[i] + p.a[k+1]*q.a[ l ]) % mod ;
        }
    }
    return s ;
}
void pow() {
    memset(q.a,0,sizeof(q.a)) ;
    q.a[1] = 1 ;
    while( m ) {
        if( m%2 )
            q = mul(q,p) ;
        m /= 2 ;
        p = mul(p,p) ;
    }
}
int main() {
    int i , j , k , l ;
    while( scanf("%I64d %I64d %I64d %I64d", &n, &mod, &d, &m) != EOF ) {
        for(i = 1 ; i <= n ; i++)
            scanf("%I64d", &a[i]) ;
        memset(p.a,0,sizeof(p.a)) ;
        for(j = 1 ; j <= n ; j++) {
            if( abs(j-1) <= d || n-abs(j-1) <= d)
                p.a[j] = 1 ;
        }
        pow() ;
        for(i = 1 ; i <= n ; i++) {
            ans[i] = 0 ;
            j = i ;
            for(k = 0 ; k < n ; k++) {
                l = j+k > n ? j+k-n : j+k ;
                ans[i] = (ans[i] + q.a[ l ]*a[ k+1 ])%mod ;
            }
        }
        for(i = 2 ; i <= n+2-i ; i++)
            swap(ans[i],ans[n+2-i]) ;
        for(i = 1 ; i <= n ; i++) {
            if( i < n )
                printf("%I64d ", ans[i]) ;
            else
                printf("%I64d\n", ans[i]) ;
        }
    }
    return 0 ;
}