poj 3150 Cellular Automation (매트릭스 쾌속 멱)

http://poj.org/problem?id=3150
대체로 n 개의 수 를 제시 하고 K 차 를 거 쳐 각 위치 에 있 는 수 를 얼마나 바 꾸 느 냐 고 물 었 다.i 위치 상의 수 는 한 번 의 변환 을 거 쳐 모든 만족 min (abs (i - j), n - abs (i - j) < = d 의 j 위치 상의 숫자 와 m 에 대한 나머지 로 정의 된다.
생각:
우 리 는 먼저 상술 한 정 의 를 행렬 로 표시 한다.
B = 
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 [i] [j] = i 와 j 가 상기 관 계 를 만족 시 키 는 것 을 나타 내 고 B [i] [j] = 0 은 i 와 j 가 상기 관 계 를 만족 시 키 지 않 는 다 는 것 을 나타 낸다.이 행렬 에 따 르 면 샘플 1 중 1, 2, 1, 2 는 한 번 에 55554 로 바 뀌 었 다.
사실 이것 도 행렬 의 상승 문제 이다. 령 A = 1, 2, 1, 2, 그러면 A * B = 55, 55, 54.그러면 K 차 변환 을 거 쳐 야 한다. 답 은 의심 할 여지없이 A * (B ^ k) mod m 이다.
행렬 쾌속 멱 의 복잡 도 는 O (n ^ 3 * log k) 이 고 n 은 최대 500 이 며 K 도 크 므 로 반드시 TLE 가 될 것 입 니 다.logk 는 변 하지 않 습 니 다. 최적화 는 n ^ 3 에 있 습 니 다.B 행렬 을 자세히 살 펴 보면 그것 은 규칙 적 인 것 이 고 모든 줄 은 그의 이전 줄 에서 오른쪽으로 한 사람 이 얻 은 것 이다.그러면 행렬 을 곱 할 때 우 리 는 첫 번 째 줄 만 계산 한 다음 에 전체 행렬 이 나 온 셈 이다. 이렇게 복잡 도 는 O (n ^ 2 * log k) 로 떨어진다.
A. 이 문 제 는 정말 기구 하 다.행렬 을 곱 할 때 제 가 전달 한 두 개의 매개 변 수 는 구조 체 입 니 다. 그 안에 500 * 500 의 배열 입 니 다. 운행 하 자마자 무 너 졌 습 니 다. 원인 을 찾 지 못 했 습 니 다. 마지막 에 전 삼 의 문 제 를 발 견 했 습 니 다. 이 는 두 개의 구조 체 를 직접 전달 하 는 것 과 같 습 니 다. 분명히 너무 큽 니 다. 그 다음 에 지침 전 삼 으로 바 꾸 었 습 니 다. 나중에 메모리 가 방출 되 지 않 았 기 때문에 1MLE 는 나중에 k 와 d 를 반대로 졌 습 니 다. 1WA.마침내 2000 + ms 가 지 났 다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 510;

_LL b[maxn],ans[maxn];
int n,m,k,d;
int mod;

struct matrix
{
    _LL mat[maxn][maxn];
}a,*res;

matrix *matrixMul(matrix *x, matrix *y)
{
    matrix *tmp;
    tmp = (matrix *)malloc(sizeof(matrix));
    memset((*tmp).mat,0,sizeof((*tmp).mat));
    for(int i = 0; i < 1; i++)
    {
        for(int k = 0; k < n; k++)
        {
            if( (*x).mat[i][k] == 0) continue;
            for(int j = 0; j < n; j++)
            {
                (*tmp).mat[i][j] += (*x).mat[i][k] * (*y).mat[k][j];
                if((*tmp).mat[i][j] >= mod)
                    (*tmp).mat[i][j] %= mod;
            }
        }
    }

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(i == 0) (*x).mat[i][j] = (*tmp).mat[i][j];
			else (*x).mat[i][j] = (*x).mat[i-1][(j-1+n)%n];
		}
	}
	free(tmp);
    return x;
}

matrix *Mul(matrix *x, int k)
{
    matrix *tmp;
	tmp = (matrix *)malloc(sizeof(matrix));
	memset((*tmp).mat,0,sizeof((*tmp).mat));
	for(int i = 0; i < n; i++)
        (*tmp).mat[i][i] = 1;

    while(k)
    {
        if(k&1)
            tmp = matrixMul(tmp,x);
        x = matrixMul(x,x);
        k >>= 1;
    }
    return tmp;
}

int main()
{
	while(~scanf("%d %d %d %d",&n,&m,&d,&k))
	{
		mod = m;
		for(int i = 0; i < n; i++)
			scanf("%I64d",&b[i]);

		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(min (abs(i-j),n-abs(i-j)) <= d)
					a.mat[i][j] = 1;
				else a.mat[i][j] = 0;
			}
		}

		res = Mul(&a,k);

		memset(ans,0,sizeof(ans));

		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				ans[i] += b[j] * ((*res).mat[j][i]);
				if(ans[i] >= mod)
					ans[i] %= mod;
			}
		}
		for(int i = 0; i < n-1; i++)
			printf("%I64d ",ans[i]);
		printf("%I64d
",ans[n-1]);
   }
    return 0;
}