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<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<queue>

#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<m.size;i++)
    {
        for(j=0;j<m.size;j++)printf("%d ",m.a[i][j]);
        printf("\n");
    }
}

mat multi(mat m1,mat m2,int mod)//兩個相等矩陣的乘法，對於稀疏矩陣，有0處不用運算的優化 
{
    mat ans=mat();    ans.size=m1.size;
    for(int i=1;i<=m1.size;i++)
        for(int j=1;j<=m2.size;j++)
            if(m1.a[i][j])//稀疏矩陣優化 
                for(int k=1;k<=m1.size;k++)
                    ans.a[i][k]=(ans.a[i][k]+m1.a[i][j]*m2.a[j][k])%mod;

    return ans;
}
mat quickmulti(mat m,int n,int mod)//二分快速冪 
{
    mat ans=mat();
    int i;
    for(i=1;i<=m.size;i++)ans.a[i][i]=1;
    ans.size=m.size;
    while(n)
    {
        if(n&1)ans=multi(m,ans,mod);
        m=multi(m,m,mod);
        n>>=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;
}