Cod sursă (job #178298)

#include<cstdio>
using namespace std;
#define mod 100003
#define type long long
type n,k,i,j,q,A[3][3],B[3][3],C[3][3]; 
FILE *f=freopen("2sah.in","r",stdin),*g=freopen("2sah.out","w",stdout);
void sol1(),sol2(); 
int main()
{unsigned short t;
scanf("%hu%d%d",&t,&n,&k);
if(t==1)
	sol1();
	else sol2();
}
void sol1()
{type r=1,p=3;
for(i=0,--k;(1<<i)<=k;++i)
	{if((1<<i)&k)
		r=(r*p)%mod;
	p=(p*p)%mod;
	}
printf("%lld",r);
}
void sol2()
{k=n+1-k;
for(i=0;i<3;++i)
	{B[i][i]=1;A[2][i]=1;
	}
A[0][1]=A[1][2]=1;
for(;k;k>>=1)
	{if(k%2)
		{for(i=0;i<3;++i)
			for(j=0;j<3;++j)
				{C[i][j]=0;
				for(q=0;q<3;++q)
					C[i][j]=(C[i][j]+B[i][q]*A[q][j])%mod;
				}
		for(i=0;i<3;++i)
			for(j=0;j<3;++j)
				B[i][j]=C[i][j];
		}
	for(i=0;i<3;++i)
		for(j=0;j<3;++j)
			{C[i][j]=0;
			for(q=0;q<3;++q)
				C[i][j]=(C[i][j]+A[i][q]*A[q][j])%mod;
			}
	for(i=0;i<3;++i)
		for(j=0;j<3;++j)
			A[i][j]=C[i][j];
	}
C[0][0]=0;
for(i=0;i<3;++i)
	C[0][0]=(C[0][0]+B[0][i])%mod;
C[0][0]=(C[0][0]+B[0][2])%mod;
printf("%lld",C[0][0]);
}