JDOJ-3114: 越狱

Description

通过递推可知有两种状态a[],b[]：

a[i]表示第I个房间时可发生越狱的数量;b[i]表示第I个房间时不能发生越狱的数量；

a[i]=a[i-1]*m+b[i-1];b[i]=b[i-1]*(m-1);

因此构造一个矩阵满足公式

m 0
1 m-1

由此进行矩乘快速幂

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MOD 100003
using namespace std;
long long n,m;
long long a[3][3],b[3],k1,k2,k3,k4;
int main()
{
        scanf("%lld%lld",&m,&n);
        m%=MOD;
        a[1][1]=m;
        a[1][2]=0;
        a[2][1]=1;
        a[2][2]=m-1;
        b[1]=0;
        b[2]=m;
        n--;
        while(n)
        {
            if(n&1)
            {
                k1=b[1]*a[1][1]+b[2]*a[2][1];
                k2=b[1]*a[1][2]+b[2]*a[2][2];
                b[1]=k1%MOD;
                b[2]=k2%MOD;
            }
            n/=2;
            k1=a[1][1]*a[1][1]+a[1][2]*a[2][1];
            k2=a[1][1]*a[1][2]+a[1][2]*a[2][2];
            k3=a[2][1]*a[1][1]+a[2][2]*a[2][1];
            k4=a[2][1]*a[1][2]+a[2][2]*a[2][2];
            a[1][1]=k1%MOD;
            a[1][2]=k2%MOD;
            a[2][1]=k3%MOD;
            a[2][2]=k4%MOD;
        }
        printf("%lld\n",b[1]);
    return 0;
}