HDU 2276 Kiki & Little Kiki 2 (매트릭스 쾌속 멱)

제목: HDU 2276
이 문제 의 행렬 구조 방식 은 그다지 보고 싶 지 않다.보고 풀 어야 지.원래 fn = (fn - 1 + fn)% 2 의 방법 을 사용 합 니 다.
그래서 하나의 행렬 을 만 들 었 다. 1, 0, 0, 1.
1,1,0,0
0,1,1,0
0,0,1,1
그리고 행렬 의 빠 른 속도 로 구 합 니 다.
그러나 나머지 연산 은 시간 이 많이 걸 리 고 매번% 2 가 시간 을 초과 하기 때문에 이때 비트 연산 으로 전환 할 수 있다.
참고 로 이 문제 의 구조 행렬 은 순환 행렬 이 고 순환 행렬 과 순환 행렬 의 곱 은 여전히 순환 행렬 이기 때문에 첫 줄 만 계산 하고 나머지 는 전달 할 수 있다.이렇게 시간 복잡 도 는 n ^ 3 logm 에서 n ^ 2 logm 으로 바 뀌 면 시간 이 많이 절약 된다.제 제출 테스트 에서 일반적인 곱셈 은 464 ms 이 고 순환 행렬 을 이용 한 방법 은 46ms 입 니 다. 원래 의 10 분 의 1 밖 에 없습니다!!
코드 는 다음 과 같 습 니 다:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

using namespace std;
int n;
struct matrix
{
    int ma[110][110];
}init, res;
matrix Mult(matrix x, matrix y)
{
    int i, j, k;
    matrix tmp;
    for(i=0;i<n;i++)
    {
        tmp.ma[0][i]=0;
        for(j=0;j<n;j++)
        {
            tmp.ma[0][i]^=x.ma[0][j]&y.ma[j][i];
        }
    }
    for(i=1;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            tmp.ma[i][j]=tmp.ma[i-1][(j-1+n)%n];
        }
    }
    return tmp;
}
matrix Pow(matrix x, int k)
{
    matrix tmp;
    int i, j;
    for(i=0;i<n;i++) for(j=0;j<n;j++) tmp.ma[i][j]=(i==j);
    while(k)
    {
        if(k&1) tmp=Mult(tmp,x);
        x=Mult(x,x);
        k>>=1;
    }
    return tmp;
}
int main()
{
    int k, i, j, x;
    char s[200];
    while(scanf("%d",&k)!=EOF)
    {
        scanf("%s",s);
        n=strlen(s);
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                init.ma[i][j]=(i==j||j==(i+n-1)%n);
            }
        }
        res=Pow(init,k);
        for(i=0;i<n;i++)
        {
            x=0;
            for(j=0;j<n;j++)
            {
                x^=(s[j]-'0')&res.ma[i][j];
            }
            printf("%d",x);
        }
        puts("");
    }
    return 0;
}