Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2439
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2439
Cachecol da Vovó Vitória
Por OBI - Olimpíada Brasileira de Informática 2013 
Brazil
Timelimit: 1
Vovó Vitória possui muitos netinhos; como toda boa avó, ela se preocupa constantemente com a saúde de seus netos, e quer garantir que eles estejam sempre bem agasalhados o tempo todo.
Vovó Vitória dispõe de um saco com vários retalhos quadrados de mesmo tamanho, em três cores diferentes, e quer usá-los para costurar cachecóis para seus netos. Ela quer que cada cachecol tenha três retalhos de largura por N de comprimento e, além disso, retalhos adjacentes devem ter cores diferentes. Por exemplo, a figura abaixo mostra três cachecóis que Vovó Vitória pode costurar.
Entrada
A entrada consiste de uma única linha contendo um único inteiro N(1 ≤ N ≤ 1018), indicando o número de retalhos no comprimento do cachecol.
Saída
Imprima uma única linha contendo um único número inteiro, indicando o número de cachecóis distintos que a Vovó Vitória pode costurar. Como este número pode ser muito grande, imprima o resto que este número deixa quando dividido por 1.000.000.007 (109 + 7).
| Exemplos de Entrada | Exemplos de Saída |
|
1 |
12 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#define REP(A, B) for (long long A = 0; A < B; A++)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll MAXK = 2;
typedef struct matrix {
ll mat[MAXK][MAXK];
} matrix;
matrix base, identidade;
matrix multiplication(matrix A, matrix B) {
matrix C;
REP(i, MAXK) REP(j, MAXK) C.mat[i][j] = 0;
REP(i, MAXK)
REP(j, MAXK)
REP(k, MAXK) C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
return C;
}
matrix exponentiation(ll expo) {
if (expo == 0) return identidade;
if (expo == 1) return base;
if (expo % 2 == 0) {
matrix temp = exponentiation(expo / 2);
return multiplication(temp, temp);
}
return multiplication(base, exponentiation(expo - 1));
}
int main() {
ll n;
scanf("%lld", &n);
if (n == 1) {
printf("12\n");
return 0;
}
if (n == 2) {
printf("54\n");
return 0;
}
REP(i, MAXK) REP(j, MAXK) identidade.mat[i][j] = (i == j);
base.mat[0][0] = 0;
base.mat[0][1] = 1;
base.mat[1][0] = -2;
base.mat[1][1] = 5;
matrix t = exponentiation(n - 1);
ll resp = (t.mat[0][0] * 12 + t.mat[0][1] * 54) % MOD;
resp = (resp + MOD) % MOD;
printf("%lld\n", resp);
return 0;
}
Input
Output