1. Análise do Prolbema

Objetivo: contar o número de manieras de cobrir uma parede de dimensões 2×N usando dois tipos de tijolos:

• Tijolo 1: retangular 2×1, que pode ser girado;
• Tijolo 2: em forma de L, cobrindo três células, com quatro orientações possíveis.

O resultado deve ser calculado módulo 10^4. Os limites são 1 ≤ N ≤ 10^6, exigindo uma solução linear ou melhor.

Exemplos:

• N = 3 → resposta 5;
• N = 13 → resposta 3465.

2. Solução 1: DP com Máscara de Estado (Enumeração de Estados)

Definimos dp[i][mask] como o número de formas de cobrir as primeiras i colunas, onde mask representa o padrão de preenchimento na coluna i, codificado em 2 bits:

• 00 → ambas as células não cobertas;
• 01 → célula inferior coberta, superior não;
• 10 → célula superior coberta, inferior não;
• 11 → ambas cobertas.

Estado inicial:

• dp[1][0] = dp[1][1] = dp[1][2] = 0;
• dp[1][3] = 1 (tijolo vertical na primeira coluna);
• dp[2][0] = 1;
• dp[2][1] = dp[2][2] = 1;
• dp[2][3] = 2 (duas opções: dois tijolos verticais ou um par horizontal).

Transições:

• dp[i][0] = dp[i-1][3];
• dp[i][1] = (dp[i-1][2] + dp[i-1][0]) % MOD;
• dp[i][2] = (dp[i-1][1] + dp[i-1][0]) % MOD;
• dp[i][3] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]) % MOD.

Código implementado:

#include <cstdio>
const int MAXN = 1000000 + 10;
const int MOD = 10000;

int dp[MAXN][4];

int main() {
    int n;
    scanf("%d", &n);

    dp[1][0] = dp[1][1] = dp[1][2] = 0;
    dp[1][3] = 1;

    dp[2][0] = 1;
    dp[2][1] = dp[2][2] = 1;
    dp[2][3] = 2;

    for (int i = 3; i <= n; ++i) {
        dp[i][0] = dp[i-1][3] % MOD;
        dp[i][1] = (dp[i-1][2] + dp[i-1][0]) % MOD;
        dp[i][2] = (dp[i-1][1] + dp[i-1][0]) % MOD;
        dp[i][3] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]) % MOD;
    }

    printf("%d\n", dp[n][3] % MOD);
    return 0;
}

Análise: Embora a complexidade seja O(N) e aceitável para N=1e6, o uso de matriz 2D ocupa espaço adicional. A abordagem é intuitiva, mas pouco eficiente em termos de memória.

3. Solução 2: Recursão com Soma Prefixada (Otimização Matemática)

Definimos F[n] como o número total de formas de cobrir 2×n. A ideia central é expressar F[n] com base em padrões finais:

• Colocar um tijolo vertical → F[n-1];
• Colocar dois tijolos horizontais → F[n-2];
• Usar dois tijolos em L (formando um bloco de 3 colunas) → 2 × Σ_{i=0}^{n-3} F[i].

Assim, temos:

F[n] = F[n-1] + F[n-2] + 2 × Σ_{i=0}^{n-3} F[i]

Introduzimos preF[n] = F[0] + F[1] + ... + F[n]. Então:

Σ_{i=0}^{n-3} F[i] = preF[n-3]

Substituindo:

F[n] = preF[n-1] + preF[n-3]

E atualizamos:

preF[n] = preF[n-1] + F[n]

Implementação eficiente:

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000000 + 10;
const int MOD = 10000;

int F[MAXN], preF[MAXN];

int main() {
    int n;
    cin >> n;

    F[0] = 1;
    preF[0] = 1;

    for (int i = 1; i <= n; ++i) {
        int term1 = (i - 1 >= 0) ? preF[i - 1] : 0;
        int term2 = (i - 3 >= 0) ? preF[i - 3] : 0;
        F[i] = (term1 + term2) % MOD;
        preF[i] = (preF[i - 1] + F[i]) % MOD;
    }

    cout << F[n] << endl;
    return 0;
}

Vantagens: código mais conciso, tempo linear, fácil de adaptar. A chave está na transformação de uma soma iterativa em uma operação constante via prefixo.

4. Comparação das Abordagens

5. Reflexão para Concursos

A resolução deste problema exemplifica um fluxo comum em algoritmos competitivos:

1. Modelar estados de forma direta (como no DP com máscara);
2. Derivar transições com base em casos;
3. Identificar padrões repetidos (como somas acumuladas);
4. Optimizar com matemática (prefixos, diferenças, fórmulas fechadas).

Esta abordagem é transferível para problemas como:

• P1896 - Não se Invasor (DP com máscara);
• P3865 - ST Table (Template) (uso de prefixos);
• P1028 - Cálculo de Números (otimização de recursão).

6. Conclusão

O problema P1990 serve como excelente exemplo de como uma solução inicial "bruta" pode ser refinada por meio de insights matemáticos. Enquanto a DP com máscara ajuda a visualizar os estados, a técnica de soma prefixada demonstra como simplificar fórmulas complexas — essencial em competições onde cada milissegundo conta.

Domine esse ciclo de pensamento: estado → transição → otimização — e você estará bem preparado para enfrentar desafios avançados de programação dinâmica.