Cod sursă (job #135325)

#include <iostream>
#include <fstream>
#define MOD 100003
using namespace std;
long long n,k;
int a[4][4],b[4][4],c[4][4];
void inm()
{
    int i, j, k=0;
    for(i=0; i<4; i++){
        k=0;
        for(j=0; j<4; j++)
        {
            c[i][j] = a[i][k] + b[k][j];
            k++;
        }
    }
    for(i=0; i<4; i++)
        for(j=0; j<4; j++)
            b[i][j] = c[i][j];
}
int putere2(int exp2)
{
    if( exp2 == 0)  inm();
    else{
        long long y;
        y = putere2(exp2/2);
        y%=MOD;
        if(exp2&1)
        {
            return (int)(y*y)%MOD;
        }
    }

}
int putere1(int base, int exp)
{
    if( exp == 0) return 1;
    long long x;
    x = putere1(base,exp/2);
    x%=MOD;
    if(exp&1)
    {
        return (int)(x*x*base)%MOD;
    }
    else return (int)(x*x)%MOD;

}
int main()
{
    int t;
    ifstream in("2sah.in");
    ofstream out("2sah.out");
    in>>t;
    if(t == 1)
    {
        in>>n>>k;
        out<<putere1(3,k-1);
    }
    else
    {
        a[0][1] = 1;
        a[1][2] = 1;
        a[2][0] = 1;
        a[2][1] = 1;
        a[2][2] = 1;
        b[0][0] = 1;
        b[1][1] = 1;
        b[2][2] = 1;

    }
    return 0;
}