Cod sursă (job #378504)

#include <fstream>

using namespace std;

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

int p,n,k,l,c,s;

int tabla[2][1000001];

int lgput(int b,int p)
{
    int put=1;
    while(p!=1){
        if(p%2==0)
        {
            p=p/2;
            b=b*b%100003;
        }else{
            p=p-1;
            put=put*b%100003;
        }
    }
    b=b*put%100003;
    return b%100003;
}

int main()
{
    in>>p>>n>>k;
    if(p==1)
        out<<lgput(3,k-1);
    else
    {
        tabla[1][1]=1;
        if(k>n+1)
            out<<0;
        else if(k==n+1)
            out<<1;
        else
        {
            c=k;
            l=1;
            while(c<n+1-l)
            {
                c+=2;
                l++;
            }
            while(c-n-1+l<=2*l-1)
            {
                swap(tabla[0],tabla[1]);
                tabla[1][1]=tabla[0][1];
                tabla[1][2]=tabla[0][2]+tabla[0][1];
                for(int i = 3;i<=2*l-1;i++)
                    tabla[1][i]=tabla[0][i]+tabla[0][i-1]+tabla[0][i-2];
                s+=tabla[1][c-n-1+l];
                s=s%100003;
                c+=2;
                l++;
            }
            out<<s;
        }
    }
    return 0;
}