Problema 1: Questão Matemática Simples

Enunciado: Dado um inteiro positivo n, calcular a soma da expressão a seguir, módulo 10^9+7:

\[ S = \sum_{i=1}^{n} i \cdot \sum_{j=i}^{n} \binom{j}{i} \]

Ideia de Solução: Utilizando a identidade combinatória \(\sum_{i=m}^{k} \binom{i}{m} = \binom{k+1}{m+1}\), simplificamos a expressão para \(S = (n-1) \cdot 2^n + 1\). A implementação requer exponenciação rápida para cálculo eficiente de \(2^n\) módulo M.

Código de Exemplo:

#include <iostream>
using namespace std;

typedef long long ll;
const ll MOD = 1e9 + 7;

ll exp_rapida(ll base, ll expo) {
    ll resultado = 1;
    base %= MOD;
    while (expo > 0) {
        if (expo & 1) resultado = (resultado * base) % MOD;
        base = (base * base) % MOD;
        expo >>= 1;
    }
    return resultado;
}

int main() {
    ll n;
    while (cin >> n) {
        ll potencia = exp_rapida(2, n);
        ll resposta = ((n - 1) * potencia % MOD + 1) % MOD;
        cout << resposta << endl;
    }
    return 0;
}

Problema 2: Contagem Sequencial

Enunciado: Dada uma sequência definida pela recorrência \(f_n = f_{n-1} + 2f_{n-2} + n^3\), com condições iniciais fornecidas, caluclar \(f_n\) para grandes valores de n módulo 123456789.

Ideia de Solução: A recorrência pode ser represetnada por uma matriz de transição 6x6. Os termos auxiliares incluem potências de n para tratar o termo \(n^3\). A solução utiliza exponenciação rápida de matrizes para calcular \(f_n\) em tempo logarítmico.

Matriz de Transição:

\[ A = \begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 3 & 0 & 3 & 1 & 0 & 0 \\ 3 & 0 & 3 & 2 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} \]

Código de Exemplo:

#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll;
const ll MOD = 123456789;
const int DIM = 6;

void multiplicar_matrizes(ll A[DIM][DIM], ll B[DIM][DIM], ll C[DIM][DIM]) {
    ll temp[DIM][DIM] = {0};
    for (int i = 0; i < DIM; i++) {
        for (int j = 0; j < DIM; j++) {
            for (int k = 0; k < DIM; k++) {
                temp[i][j] = (temp[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    memcpy(C, temp, sizeof(temp));
}

void potencia_matriz(ll base[DIM][DIM], ll expo, ll resultado[DIM][DIM]) {
    ll temp[DIM][DIM];
    memset(resultado, 0, sizeof(ll) * DIM * DIM);
    for (int i = 0; i < DIM; i++) resultado[i][i] = 1;
    memcpy(temp, base, sizeof(ll) * DIM * DIM);
    while (expo > 0) {
        if (expo & 1) multiplicar_matrizes(resultado, temp, resultado);
        multiplicar_matrizes(temp, temp, temp);
        expo >>= 1;
    }
}

int main() {
    int casos;
    cin >> casos;
    while (casos--) {
        ll n;
        cin >> n;
        ll valor_inicial[] = {2, 1, 8, 4, 2, 1};
        ll matriz_trans[DIM][DIM] = {
            {1, 1, 0, 0, 0, 0},
            {2, 0, 0, 0, 0, 0},
            {1, 0, 1, 0, 0, 0},
            {3, 0, 3, 1, 0, 0},
            {3, 0, 3, 2, 1, 0},
            {1, 0, 1, 1, 1, 1}
        };
        if (n <= 2) {
            cout << valor_inicial[n] << endl;
            continue;
        }
        ll expo = n - 2;
        ll resultado_mat[DIM][DIM];
        potencia_matriz(matriz_trans, expo, resultado_mat);
        ll resposta = 0;
        for (int i = 0; i < DIM; i++) {
            resposta = (resposta + valor_inicial[i] * resultado_mat[i][0]) % MOD;
        }
        cout << resposta << endl;
    }
    return 0;
}