Kiki & Little Kiki 2

1
0101111
10
100000001

1111000
001000010

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define bug printf("hihi\n")

#define eps 1e-8
typedef __int64 ll;

using namespace std;

#define INF 0x3f3f3f3f
#define N 101
int n;

struct mat{
   mat(){memset(a,0,sizeof(a));}
   int a[N][N];
   mat operator *(mat b)
   {
       mat c;
       for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
             for(int k=0;k<n;k++)
                 c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%2;
       return c;
   }
};

mat fdd(mat s,int m)
{
    mat ss;
    for(int i=0;i<n;i++) ss.a[i][i]=1;
    while(m)
    {
        if(m&1) ss=ss*s;
        s=s*s;
        m>>=1;
    }
    return ss;
}

int main()
{
    int i,j;
    char c[1000];
    int m;
    while(~scanf("%d",&m))
    {
        scanf("%s",c);
        mat s;
        n=strlen(c);
        for(i=0;i<n;i++)
            s.a[i][0]=c[i]-'0';
        mat ss;
        ss.a[0][0]=ss.a[0][n-1]=1;
        for(i=1;i<n;i++)
            ss.a[i][i]=ss.a[i][i-1]=1;
        ss=fdd(ss,m);
        s=ss*s;
        for(i=0;i<n;i++)
            printf("%d",s.a[i][0]);
      printf("\n");
    }
    return 0;
}

HDU 2276 Kiki & Little Kiki 2（矩阵快速幂）

原文：http://blog.csdn.net/u014737310/article/details/47981129