距阵的乘法，关键是要熟悉距阵乘法的结合率，可以用N*LOGN的算法过。
#include <stdio.h>
typedef struct
{
int a11, a12;
int a21, a22;
}type;
void Mul ( type *a, type *b, type *c )//a*b->c
{
c->a11 = ( a->a11*b->a11 + a->a12*b->a21 ) % 10000;
c->a12 = ( a->a11*b->a12 + a->a12*b->a22 ) % 10000;
c->a21 = ( a->a21*b->a11 + a->a22*b->a21 ) % 10000;
c->a22 = ( a->a21*b->a12 + a->a22*b->a22 ) % 10000;
}
void Cpy ( type *a, type *b )//a=b
{
a->a11 = b->a11;
a->a12 = b->a12;
a->a21 = b->a21;
a->a22 = b->a22;
}
type sum, count, temp, t;
type e = { 1, 0, 0, 1 };
type s = { 1, 1, 1, 0 };
int main ()
{
int n;
while ( scanf ( "%d", &n ) != EOF && n >= 0 )
{
if ( n == 0 )
{
printf ( "0\n" );
continue;
}
if ( n == 1 )
{
printf ( "1\n" );
continue;
}
n = n-2;
Cpy ( &sum, &e );
Cpy ( &count, &s );
while ( n )
{
if ( n & 1 )
{
Mul ( &sum, &count, &temp );
Cpy ( &sum, &temp );
}
n >>= 1;
Cpy ( &t, &count );
Mul ( &count, &t, &temp );
Cpy ( &count, &temp );
}
printf ( "%d\n", ( sum.a11 + sum.a12 ) % 10000 );
}
return 0;
}