# Cod sursa(job #2667229)

Utilizator Data 3 noiembrie 2020 09:28:03 Al k-lea termen Fibonacci 100 cpp-64 done Arhiva educationala 1.93 kb
#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const int MOD = 666013;

int K;

struct Matrix
{
int N, M;

int **A;
};

Matrix Special, I2;

{
f.tie(nullptr);

f >> K;

return;
}

static inline int ** Get_Matrix (int N, int M)
{
int ** ans = new int *[(N + 1)];

for(int i = 1; i <= N; ++i)
{
ans[i] = new int [(M + 1)];

for(int j = 1; j <= M; ++j)
ans[i][j] = 0;
}

return ans;
}

static inline void Initialize ()
{
Special.N = Special.M = 2, Special.A = Get_Matrix(2, 2);
Special.A[1][2] = Special.A[2][1] = Special.A[2][2] = 1;

I2.N = I2.M = 2, I2.A = Get_Matrix(2, 2);
I2.A[1][1] = I2.A[2][2] = 1;

return;
}

static inline void Multiply (Matrix &A, Matrix B)
{
///
Matrix ans;
ans.N = A.N, ans.M = B.M;
ans.A = Get_Matrix(ans.N, ans.M);
///

for(int i = 1; i <= A.N; ++i)
for(int j = 1; j <= B.M; ++j)
{
ans.A[i][j] = 0;

for(int k = 1; k <= A.M; ++k)
ans.A[i][j] = 1LL * (1LL * ans.A[i][j] + 1LL * A.A[i][k] * B.A[k][j]) % (1LL * MOD);
}

A = ans;

return;
}

static inline Matrix lgput (Matrix n, int p)
{
Matrix ans = I2, aux = n;

for(int i = 0; (1 << i) <= p; ++i)
{
if(p & (1 << i))
Multiply(ans, aux);

Multiply(aux, aux);
}

return ans;
}

static inline void Solve ()
{
Initialize();

Matrix now = lgput(Special, K - 1);

Matrix ans;
ans.N = 1, ans.M = 2, ans.A = Get_Matrix(1, 92);
ans.A[1][1] = 0, ans.A[1][2] = 1;

Multiply(ans, now);

g << ans.A[1][2] << '\n';

return;
}

int main()
{