soj2385三阶矩阵分治.cpp

一些ACM题目的解答,主要是soj和poj的

#include<stdio.h>

int p = 10000;

typedef struct
{
    int a;
    int b;
    int c;
    int d;
    int e;
    int f;
    int g;
    int h;
    int i;
}matrix;

matrix mult(matrix a,matrix b,int p)
{
    matrix result;
    result.a = (a.a * b.a + a.b * b.d + a.c * b.g)%p;
    result.b = (a.a * b.b + a.b * b.e + a.c * b.h)%p;
    result.c = (a.a * b.c + a.b * b.f + a.c * b.i)%p;
    result.d = (a.d * b.a + a.e * b.d + a.f * b.g)%p;
    result.e = (a.d * b.b + a.e * b.e + a.f * b.h)%p;
    result.f = (a.d * b.c + a.e * b.f + a.f * b.i)%p;
    result.g = (a.g * b.a + a.h * b.d + a.i * b.g)%p;
    result.h = (a.g * b.b + a.h * b.e + a.i * b.h)%p;
    result.i = (a.g * b.c + a.h * b.f + a.i * b.i)%p;
    return result;
}

matrix mamod(matrix unit,long n,int p)
{
    matrix t;

    if(n==0)
    {
        t.a=1;
        t.b=0;
        t.c=0;
        t.d=0;
        t.e=1;
        t.f=0;
        t.g=0;
        t.h=0;
        t.i=1;
        return t;
    }
    if(n<0)
    {
        t.a=0;t.b=0;t.c=0;t.d=0;t.e=0;t.f=0;t.g=0;t.h=0;t.i=0;
        return t;
    }
    matrix result = mamod(mult(unit,unit,p),n/2,p);

    if(n%2==1)
    {
        result = mult(unit,result,p);
    }

    return result;
}


int main(void)
{
    int a,b;
    matrix base;
    base.a=1;base.b=1;base.c=0;base.d=0;base.e=1;base.f=1;base.g=0;base.h=1;base.i=0;
    while(scanf("%d%d",&a,&b)==2&&(a||b))
    {
        matrix result1 = mamod(base,a-1,p);
        int r1 = (result1.a+result1.b+result1.c)%p;
        matrix result2 = mamod(base,b,p);
        int r2 = (result2.a+result2.b+result2.c)%p;
        int result = (r2+p-r1)%p;;
        printf("%d\n",result);
    }
    return 0;
}