Cod sursă (job #196725)

#include <iostream>
#include <fstream>
using namespace std;

ifstream in("2sah.in");
ofstream out("2sah.out");

const int mod = 100003;

int T, N, K;

/*CALCULAM a x b , PUNAND REZULTATUL IN a, FOLOSIND c CA SPATIU DE MANEVRA*/
void inm(long long a[3][3], long long b[3][3], long long c[3][3])
{
    int i, j, k;

    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];
        }

    for(i = 0; i < 3; i++)
        for(j = 0; j < 3; j++)
            a[i][j] = c[i][j] % mod;
}

int main()
{
    in >> T;

    in >> N >> K;

    if(T == 1)
    {
        //CALCULAM 3 ^ (K - 1) PRIN EXPONENTIERE LOGARITMICA

        long long answer = 1;
        long long x, y;

        x = 3;
        y = K - 1;

        while(y)
        {
            if(y % 2 == 1) answer = ( answer * x ) % mod;

            x = ( x * x ) % mod;

            y = y/2;
        }

        out << answer;
    }
    else
    {
        //CALCULAM A ^ (N - K + 1) PRIN EXPONENTIERE LOGARITMICA

        long long A[3][3] = { {0, 1, 0}, {0, 0, 1}, {1, 1, 1} };

        long long ans[3][3] = { {1, 0, 0}, {0, 1, 0}, {0, 0, 1} };

        long long rez[3][3];

        int k = N - K + 1;

        while(k)
        {
            if(k % 2 == 1) inm(ans, A, rez);

            inm(A, A, rez);

            k = k/2;
        }

        out << ans[2][2];
    }

    return 0;
}