题目：

矩阵快速幂模板。mod写到乘法的定义部分就行了。

别忘了 I ( ) 和 i n i t ( ) 要传引用！

#include
     
      #include
      
       #include
       
        using namespace std;int n,p=10000;struct Matrix{    int a[2][2];    Matrix operator *(const Matrix &b)const    {        Matrix c;        c.a[0][0]=c.a[1][0]=c.a[0][1]=c.a[1][1]=0;        for(int i=0;i<=1;i++)            for(int j=0;j<=1;j++)                for(int k=0;k<=1;k++)                    (c.a[i][j]+=a[i][k]*b.a[k][j])%=p;//                        printf("i=%d j=%d c=%d\n",i,j,b.a[i][j]);        return c;    }};Matrix r,u;void I(Matrix &k){    k.a[0][0]=k.a[1][1]=1;    k.a[0][1]=k.a[1][0]=0;}void init(Matrix &k){    k.a[0][0]=k.a[0][1]=k.a[1][0]=1;    k.a[1][1]=0;}int main(){    while(1)    {        scanf("%d",&n);if(n==-1)return 0;        if(!n){printf("0\n");continue;}        n--;I(r);init(u);        while(n)        {            if(n&1)r=r*u;            n>>=1;u=u*u;        }        printf("%d\n",(r.a[1][0]+r.a[1][1])%p);    }}