Cod sursa(job #2581709)

Utilizator andreea.nica1602Andreea Nica andreea.nica1602 Data 15 martie 2020 17:48:42
Problema Iepuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
/* exemplut problema exponentiere logaritmica pe matrici 
	https://infoarena.ro/problema/iepuri
	*/

#include <bits/stdc++.h>
#include <fstream>
#define KMAX 3
#define kMod 666013
using namespace std;


void inmultireMatrici (unsigned long long A[KMAX][KMAX], unsigned long long B[KMAX][KMAX], unsigned long long C[KMAX][KMAX]) {
	unsigned long long tmp[KMAX][KMAX];

	for (int i = 0; i < KMAX; ++i) {
		for (int j = 0; j < KMAX; ++j) {
			unsigned long long aux = 0LL;
			for (int l = 0; l < KMAX; ++l) {
				aux = (aux + A[i][l] * B[l][j]) %kMod;
			}
			tmp[i][j] = aux;
		}
	}

	memcpy(C, tmp, sizeof(tmp));
}

void putereMatrici (unsigned long long A[KMAX][KMAX], int n, unsigned long long R[KMAX][KMAX]) {
	unsigned long long tmp[KMAX][KMAX];

	for (int i = 0; i < KMAX; ++i) {
		for (int j = 0; j < KMAX; j++) {
			tmp[i][j] = (i == j) ? 1LL : 0LL;
		}
	}

	while (n != 1) {
		if ( n % 2 == 0) {
			inmultireMatrici(A, A, A);
			n /= 2;
		}
		else {
			inmultireMatrici(tmp, A, tmp);
			n--;
		}
	}

	inmultireMatrici(tmp, A, A);
}

int main () {

	ifstream fin ("iepuri.in");
	ofstream fou ("iepuri.out");

	int T;
	int x, y, z, a, b, c,n ;
	int i;


	fin >> T;

	for (i = 0; i < T; ++i) {
		fin >> x >> y >> z >> a >> b >> c >> n;

		unsigned long long init[KMAX][KMAX] = { {0LL, 0LL, 0LL}, 
												{0LL, 0LL, 0LL},
												{0LL, 0LL,0LL}};
		init[0][0] = x, init[0][1] = y, init [0][2] = z;

		unsigned long long  A[KMAX][KMAX] = { {0LL, 0LL, 0LL}, 
											{1LL, 0LL, 0LL},
											{0LL, 1LL, 0LL}};
		A[0][2] = c, A[1][2] = b, A[2][2] = a;

		
		putereMatrici(A, n - 2, A);
		inmultireMatrici(init, A, init);
		fou << init[0][2] << endl;



	}
	fin.close();
	fou.close();

	return 0;
}