Cod sursă (job #304212)

#include <stdio.h>
#include <stdlib.h>
#define MOD 100003
#define ULL unsigned long long
ULL a[3][3]={
  { 0, 1, 0 },
  { 0, 0, 1 },
  { 1, 1, 1 }
}, e[3][3]={
  { 1, 0, 0 },
  { 0, 1, 0 },
  { 0, 0, 1 }
}, t[3][1]={ {1}, {1}, {2} }, aux[3][3];

void mult(ULL *c, ULL *d, int n, int m, int p){
  int i, j, k;
  for(i=0; i<n; i++)
    for(j=0; j<p; j++)
      for(k=0; k<m; k++){
        aux[i][j]+=(*(c+i*m+k))*(*(d+k*p+j));
      }
  for(i=0; i<n; i++)
    for(j=0; j<m; j++){
      (*(c+i*m+j))=aux[i][j]%MOD;
      aux[i][j]=0;
    }
}

int main(){
  int k;
  ULL n, p;
  FILE *fin, *fout;
  fin=fopen("2sah.in", "r");
  fout=fopen("2sah.out", "w");
  fscanf(fin, "%llu%llu%d", &p, &n, &k);
  if(p==1){
    k=(k-1)%(MOD-1);
    n=3;
    while(k){
      if(k&1){
        p*=n;
        if(p>MOD)
          p%=MOD;
      }
      n*=n;
      if(n>MOD) n%=MOD;
      k>>=1;
    }
    fprintf(fout, "%llu", p);
    return 0;
  }
  k=n+1-k;
  while(k){
    if(k&1)
      mult(e[0], a[0], 3, 3, 3);
    mult(a[0], a[0], 3, 3, 3);
    k>>=1;
  }
  mult(e[0], t[0], 3, 3, 1);
  fprintf(fout, "%llu", e[0][0]);
  fclose(fin);
  fclose(fout);
    return 0;
}