POJ 3150 / Uva 1386 Cellular Automation 문제 풀이 보고서 (순환 행렬)

제목: 세포 에 있 는 숫자 는 주위 의 숫자 에 따라 달라 지 며 k 라운드 이후 의 숫자 를 구 하 는 경우.
    문제 풀이 보고서: 행렬 곱셈 을 쉽게 생각 할 수 있다.빠 른 속도 로 확실히 k 제곱 을 빠르게 계산 할 수 있다.
    그러나 n 은 최대 500 이 고 행렬 곱셈 의 복잡 도 는 n ^ 3 이 며 일반 알고리즘 은 반드시 시간 을 초과 할 것 입 니 다.
    이 럴 때 는 행렬 의 성질 을 봐 야 한다.자세히 살 펴 보면 행렬 의 모든 줄 이 대칭 적 이 고 다음 줄 에서 한 명 을 왼쪽으로 옮 기 는 것 이 바로 이전 줄 이라는 것 을 알 수 있다.이런 행렬 을 순환 행렬 이 라 고 한다.
    순환 행렬 의 성질: 순환 행렬 A, 행렬 B, A * B 와 여전히 순환 행렬 입 니 다.
    성질 에 따라 우 리 는 행렬 곱셈 을 할 때 첫 줄 만 계산 할 수 있다.물론 첫 줄 은 전체 행렬 의 정 보 를 포함 하고 있 기 때문에 우 리 는 첫 줄 만 기록 할 수 있다.
    빠 른 속도 로 답 을 빠르게 계산 해 낼 수 있다.그리고 계산 이 끝 날 때마다 모델 링 이 훨씬 빨 라 집 니 다.POJ 위 아래 코드 는 500 MS 입 니 다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long Array[555];

int mod;
int n;

Array a, b, c;

void mul(Array& a, Array& b)
{
    memset(c,0,sizeof(c));
    for(int i=0;i<n;i++)
        for(int k=0;k<n;k++)
            c[i]+=a[k]*b[k>=i?(k-i):(n+k-i)];
    for(int i=0;i<n;i++)
        a[i]=c[i]%mod;
}

void powArray(Array& a, int b)
{
    Array res={1};
    while(b)
    {
        if(b&1)
            mul(res, a);
        mul(a, a);
        b>>=1;
    }

    memcpy(a, res, sizeof(res));
}

int main()
{
    int d, k;
    while(~scanf("%d%d%d%d", &n, &mod, &d, &k))
    {
        memset(a, 0, sizeof(a));
        for(int i=0;i<=d;i++)
            a[i]=a[(n-i)%n]=1;
        powArray(a, k);

        for(int i=0;i<n;i++)
            scanf("%lld", b+i);
        mul(b, a);
        printf("%d", b[0]);
        for(int i=1;i<n;i++)
            printf(" %lld", b[i]);
        puts("");
    }
}

    올해 항 저 우 초청 경기 의 첫 번 째 문제 도 이런 유형 이 었 다. 당시 에는 행렬 곱셈 도 알 아 볼 수 없 었 기 때문이다.오늘 이 문 제 를 단숨에 A 로 풀 었 다.
    제목 링크: HDU 4576
    이 문 제 는 매우 재미있다.문제 풀이 보고서: 문제 풀이 보고서