2385 - Multiplicação de Matrizes

Esse é um exemplo claro onde a descrição faz parecer que o problema é muito mais difícil do que ele realmente é.

Descrição

beecrowd Talent Cloudbeecrowd

Solução

Um bom jeito de começar a solucionar problemas é em vez de focar nas possibilidades de resolução, focar com quais limitações nossa solução vai ter que lidar. Por exemplo, neste problema, as matrizes envolvidas tem tamanho máximo 10000 x 10000, o que é impossível de representar nos computadores atuais. Logo, agora temos uma dica de que não será necessário construir as matrizes completas A e B para resolver o problema.

Com isso, vem a pergunta: ué, mas se não podemos construir as matrizes, como vamos calcular o resultado na matriz C? Daí podemos ver que o problema na verdade não pede para imprimirmos a matriz C, ele só pede para que imprimamos um elemento específico situado em uma coordenada específica da matriz C, o que torna nosso problema muito mais fácil.

Mas como que vamos descobrir o valor do elemento específico sem saber a matriz inteira? Basta lembrar de como multiplicação de matrizes funciona na prática. Para toda matriz A e B quadrada de dimensões iguais, podemos calcular um elemento da matriz C na posição (i, j) da seguinte forma:

$$C_{ij} = \sum\limits_{k = 1}^{N} A_{ik} \times B_{kj}$$

Com isso, basta apenas calcularmos este somatório para todos os valores de k para conseguirmos nossa resposta, só prestando atenção a dois detalhes importantes:

• A resposta pode dar overflow, então utilize inteiros com capacidade maior para armazenar a resposta;

• Os índices vão de 1 até N.

C99

#include <stdio.h>

int main(){
    long long int resposta;
    int N, P, Q, R, S, X, Y, I, J;

    scanf("%d\n", &N);
    scanf("%d %d %d %d %d %d\n", &P, &Q, &R, &S, &X, &Y);
    scanf("%d %d", &I, &J);

    resposta = 0;
    for(int k = 1; k <= N; ++k){
        resposta += ((P * I + Q * k) % X) * ((R * k + S * J) % Y);
    }

    printf("%lld\n", resposta);

    return 0;
}

C++17

Python 3.9