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

题意：m表示m秒

下面一行表示n个灯（灯是排成环的，也就是说头尾相接）

灯亮暗由 1 0表示

对于任意一盏灯，当左边灯亮时，下一秒该灯将变换状态

问：输出m秒后灯的状态

因为每盏灯都由前一秒的该灯和该灯左边那盏灯的状态决定，所以可以写出一个矩阵

当有5盏灯时：

1 0 0 0 1

1 1 0 0 0

0 1 1 0 0

0 0 1 1 0

0 0 0 1 1

原来的n乘上上面的矩阵就可以得到下一秒的状态，然后就是矩阵快速幂

#include
#include
#include
#include
#include

#define ll int
#define MOD 2
#define Matr 105 //矩阵大小
using namespace std;
inline ll Max(ll a,ll b){return a>b a:b;}
inline ll Min(ll a,ll b){return a>b b:a;}
//矩阵快速幂 +++ 

struct mat//矩阵结构体，a表示内容，size大小 
{
    int a[105][105],size;
    mat()
    {
        size=0;
        memset(a,0,sizeof(a));
    }
};
void print(mat m)//输出矩阵信息，debug用 
{
    int i,j;
    printf("%d\n",m.size);
    for(i=0;i>=1;
    }
    return ans;
}

int main(){
	int n,i,mul,m[Matr],ans[Matr];
	char s[Matr];
	while(~scanf("%d",&mul)){
		scanf("%s",s);
		int n=strlen(s);
		for(i=1;i<=n;i++)m[i]=s[i-1]-'0';

		mat a=mat(); a.size=n; 
		for(i=1;i<=n;i++)a.a[i][i]=a.a[i][i+1]=1;		a.a[n][1]=1;

		a=quickmulti(a,mul,MOD);
		memset(ans,0,sizeof(ans));
		for(i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				ans[i]=(ans[i]+m[j]*a.a[j][i])%MOD;

		for(i=1;i<=n;i++)printf("%d",ans[i]);	printf("\n");
	}
	return 0;
}