Seja (i, j) o intervalo compreendido entre as posições i e j (inclusive) da fileira de quadradinhos. Note que a soma desse intervalo pode ser obtida se pegarmos a soma de todos os números até a posição j (1, j) e dela subtrairmos a soma de todos os números até a posição imediatamente anterior à posição i (1, i-1). Para ilustrar isso melhor, observe a imagem, onde fica claro que SOMA C = SOMA A - SOMA B
Desse modo, escolher duas posições i e j de modo que a soma dos números no intervalo compreendido entre elas seja congruente a zero (módulo 8) é o mesmo que escolher as posições i e j de modo que a diferença entre os intervalos (1, i-1) e (1, n) seja congruente a zero (módulo 8), ou seja, ambos os intervalos devem ter a mesma soma (módulo 8). Desse modo, basta olharmos, para cada posição j do vetor, quantas posições anteriores i têm a soma do intervalo (1, i) congruente à soma (1, j), pois a soma dos elementos de i+1 até j será congruente a zero (módulo 8).
Assim, vamos criar um vetor qtd. Para cada resto r,o valor de qtd[r] guardará quantas posições i da fileira apresentam a soma de todos os quadradinhos até tal posição (intervalo (1, i)) congruente a r (módulo 8), no momento em que lemos o valor de determinada posição. Desse modo vamos criar uma variável resposta com valor zero, e vamos declarar o vetor qtd global para que todos os seus valores recebam 0. A posição 0 d vetor deve receber valor 1, pois a soma do intervalo (0, 0) já começa antes de lermos qualquer número da fileira e é congruente a zero (módulo 8).
Vamos ler então cada um dos números da entrada. Vamos criar uma variável soma que representará a soma atual dos números da fileira, começando, portanto, com valor 0. Vamos agora ler os valores dos números. Para cada número x lido, atualizamos a soma da fileira adicionando o valor de x a soma. Agora, verificamos o resto de soma no módulo 8 ("soma%=8;") e olhamos quantas posições anteriores à que estamos são tais que a soma de todos os números até ela deixa resto soma na divisão por 8. Para cada uma dessas posições, podemos criar um novo intervalo de soma congruente a 0 (módulo 8), logo adicionamos essa quantidade (qtd[soma]) à resposta com o comando "resp+=qtd[soma];". Depois disso, deveos guardar que encontramos uma nova posição (a atual) em que a soma de todos os números até ela deixa resto soma na divisão por 8, com o comando "qtd[soma]++;" Quando tivermos lido todos os números da entrada, basta imprimirmos uma única linha com o valor de resposta. Como observação final, note que a resposta pode ser muito grande, bem maior que 2 bilhões (pois em uma análise bem simples, podemos somar n vezes as n posições da fileira, e n vai até 
, logo deve ser declarada como long long int). Segue o código comentado para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| int n, soma, qtd[10]; | |
| long long int resposta; | |
| int main(){ | |
| scanf("%d", &n); // leio o valor de n | |
| // no cmeço, só há um intervalo na fileira: o vazio(0, 0) | |
| qtd[0]=1; // e ele é congruente a 0(mod 8) | |
| for(int i=1; i<=n; i++){ // para cada posição da fileira | |
| // declar e elio o número da posição | |
| int num; | |
| scanf("%d", &num); | |
| soma+=num; // somo seu valor a soma | |
| soma%=8; // atualizo a congruência de soma (mod 8) | |
| // e para cada posiçõ anterior que a soma de todos os números | |
| // até tal posição era congruente a 8 (mod 0) | |
| resposta+=qtd[soma]; // adiciono uma possível resposta | |
| // e guardo que encontrei outra posição de soma congruente a 0 (mod 8) | |
| qtd[soma]++; | |
| } | |
| printf("%lld\n", resposta); // ao fim da leitura, imprimo o valor de resposta | |
| } |