Народ, может кто знает, как определить априорную и апостериорную временную и ёмкостную сложность программы? и как это реализовать в с++?
код программы следующий:
[CODE]#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

ll f[16];
ll a[16];

int d,n,m;

ll m1[16][16];
ll m2[16][16];
ll m3[16][16];

void umnmat(ll m1[16][16],ll m2[16][16]) {
int i,j,k;
ll z;
for (i=0;i<d;++i) {
for (j=0;j<d;++j) {
m3[i][j] = 0;
for (k=0;k<d;++k) {
z = (m1[i][k]*m2[k][j])%m;
m3[i][j] = (m3[i][j]+z)%m;
}
}
}
for (i=0;i<d;++i)
for (j=0;j<d;++j)
m1[i][j] = m3[i][j];
}

int main() {

while (1) {
scanf("%d %d %d",&d,&n,&m);
if (!d && !n && !m)
break;

int i;
int x;
for (i=0;i<d;++i) {
scanf("%d",&x);
x %= m;
a[d-i-1] = x;
}
for (i=0;i<d;++i) {
scanf("%d",&x);
x %= m;
f[i] = x;
}

if (n<=d) {
printf("%d\n",int(f[n-1]));
continue;
}

n -= d;
memset(m1,0,sizeof(m1));
for (i=0;i<d;++i)
m1[i][i] = 1;

int j;
for (i = 1; i < d; ++i) {
for (j = 0; j < d; ++j) {
m2[j][i-1] = (j==i);
}
}
for (i=0;i<d;++i)
m2[i][d-1] = a[i];

while (n) {
if (n%2) {
umnmat(m1,m2);
}
umnmat(m2,m2);
n /= 2;
}

ll ans = 0;
ll xx;
for (i=0;i<d;++i) {
xx = (f[i]*m1[i][d-1])%m;
ans = (ans+xx)%m;
}

printf("%d\n",int(ans));
}

return 0;
}

 
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

ll f[16];
ll a[16];

int d,n,m;

ll m1[16][16];
ll m2[16][16]; 
ll m3[16][16];

void umnmat(ll m1[16][16],ll m2[16][16]) {
        int i,j,k;
        ll z;
        for (i=0;i<d;++i) {
                for (j=0;j<d;++j) {
                        m3[i][j] = 0;
                        for (k=0;k<d;++k) {
                                z = (m1[i][k]*m2[k][j])%m;
                                m3[i][j] = (m3[i][j]+z)%m;
                        }
                }
        }
        for (i=0;i<d;++i)
                for (j=0;j<d;++j)
                        m1[i][j] = m3[i][j];
}

int main() {

        while (1) {
                scanf("%d %d %d",&d,&n,&m);
                if (!d && !n && !m)
                        break;

                int i;
                int x;
                for (i=0;i<d;++i) {
                        scanf("%d",&x); 
                        x %= m;
                        a[d-i-1] = x;
                }
                for (i=0;i<d;++i) {
                        scanf("%d",&x);
                        x %= m;
                        f[i] = x;
                }

                if (n<=d) {
                        printf("%d\n",int(f[n-1]));
                        continue;
                }

                n -= d;
                memset(m1,0,sizeof(m1));
                for (i=0;i<d;++i)
                        m1[i][i] = 1;

                int j;
                for (i = 1; i < d; ++i) {
                        for (j = 0; j < d; ++j) {
                                m2[j][i-1] = (j==i);
                        }
                }
                for (i=0;i<d;++i)
                        m2[i][d-1] = a[i];

                while (n) {
                        if (n%2) {
                                umnmat(m1,m2);
                        }
                        umnmat(m2,m2);
                        n /= 2;
                }

                ll ans = 0;
                ll xx;
                for (i=0;i<d;++i) {
                        xx = (f[i]*m1[i][d-1])%m;
                        ans = (ans+xx)%m;
                }

                printf("%d\n",int(ans));
        }

        return 0;
}