Cod sursă (job #691812)

#include <bits/stdc++.h>
#define MOD 100003
using namespace std;
ifstream fin("2sah.in");
ofstream fout("2sah.out");
int PowNumber(int x,int n)
{
    int p=1;
    while(n)
    {
        if(n&1) p*=x,p%=MOD;
        x*=x;x%=MOD;
        n>>=1;
    }
    return p;
}
void ProductMatrix(int a[3][3],int b[3][3] )
{
    int i,j,k,c[3][3];
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
    {
        c[i][j]=0;
        for(k=0;k<3;k++) c[i][j]+=a[i][k]*b[k][j],c[i][j]%=MOD;
    }
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
        a[i][j]=c[i][j];
}
void PowMatrix(int x[3][3],int n)
{
    int p[3][3]={{1,0,0},{0,1,0},{0,0,1}};
    while(n)
    {
        if(n&1) ProductMatrix(p,x);
        ProductMatrix(x,x);
        n>>=1;
    }
    fout<<p[2][2];
}
int main()
{
    int task,n,k;
    fin>>task>>n>>k;
    if(task==1)
    {
        fout<<PowNumber(3,k-1);
    }
    else
    {
        int x[3][3]={{0,1,0},{0,0,1},{1,1,1}};
        PowMatrix(x,k);
    }
    return 0;
}