Nk 1430 Fibonacci(二分矩阵乘幂)

AC代码：

#include<iostream>
using namespace std;
int a[3][3];
int d[3][3];
int t[3][3];
int temp[3][3];

void binary(int n)
{
    int i,j,k;
    while(n)
    {
        if(n%2)
        {
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    temp[i][j]=d[i][j];
                for(i=1;i<=2;i++)
                {    
                    for(j=1;j<=2;j++)
                    {
                        int sum=0;
                        for(k=1;k<=2;k++)
                            sum+=temp[i][k]*t[k][j];
                        d[i][j]=sum%10000;
                    }        
                }
        }
        n/=2;
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)
                temp[i][j]=t[i][j];
            for(i=1;i<=2;i++)
            {    
                for(j=1;j<=2;j++)
                {
                    int sum=0;
                    for(k=1;k<=2;k++)
                        sum+=temp[i][k]*temp[k][j];
                    t[i][j]=sum%10000;
                }        
            }
    }
}
int main()
{
    int n;
    while(cin>>n,n+1)
    {
        if(!n)
        {
            cout<<0<<endl;
            continue;
        }
        memset(a,0,sizeof(a));
        memset(d,0,sizeof(a));
        memset(t,0,sizeof(a));
        a[1][1]=a[1][2]=a[2][1]=1;
        d[1][1]=d[2][2]=1;
        t[1][1]=t[1][2]=t[2][1]=1;
        binary(n);
        cout<<d[2][1]<<endl;
    }
    return 0;
}