Skip to Content
CTRL K

Subarray Divisibility

Problema

Nos piden hallar el número de subarreglos que son divisibles por NN. En otras palabras, debemos hallar el número de subarreglos con suma igual a 0(modN)0 \pmod N.

Explicación

Nótese que cualquier suma de un subarreglo se puede representar como la diferencia de dos prefijos.

Primero, sea sum\texttt{sum} la suma de prefijos del arreglo aa módulo NN.

Con nuestro conocimiento de sumas de prefijos,

sum(i,j)=sum(0,j)−sum(0,i−1) \texttt{sum}(i, j) = \texttt{sum}(0, j) - \texttt{sum}(0, i-1)

Como queremos calcular el número de sum(i,j)\texttt{sum}(i, j) que es igual a 0(modN)0\pmod N, sum(0,j)\texttt{sum}(0, j) debe ser igual a sum(0,i−1)\texttt{sum}(0, i-1) para que su diferencia sea 00.

Ahora calculamos pmod[i]\texttt{pmod}[i], el número de prefijos con resto equivalente a i(modN)i\pmod{N}. Entonces el número de pares que aporta ii es

(pmod[i]2)=pmod[i]⋅(pmod[i]−1)/2 {\texttt{pmod}[i]\choose{2}} = \texttt{pmod}[i] \cdot (\texttt{pmod}[i] - 1) / 2

La respuesta es simplemente la suma de esta cantidad sobre todo ii.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <iostream>
#include <vector>
 
using namespace std;
 
/**
 * @author Qi Wang
 * (detemplifying courtesy of Kevin Sheng)
 */
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int N;
	cin >> N;
 
	vector<long long> M(N);
	long long psums = 0;
	M[psums] = 1;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		psums += a;
		// Remember to account for negative sums
		M[(psums % N + N) % N]++;
	}
 
	long long ans = 0;
	for (long long x : M) {
		/*
		 * Calculating the # of pairs.
		 * This calculates the pairs without
		 * duplicates and reverse groups.
		 */
		ans += x * (x - 1) / 2;
	}
	cout << ans << endl;
}
import java.io.*;
import java.util.*;
 
public class subarrayDivisibility {
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
 
		long[] M = new long[n];
		long prefixSums = 0;
		M[0] = 1;
 
		for (int i = 0; i < n; i++) {
			int a = io.nextInt();
			prefixSums += a;
			// remember to account for negative sums
			M[((int)(prefixSums % n) + n) % n]++;
		}
 
		long answer = 0;
		for (long x : M) {
			/*
			 *  calculating the # of pairs, this calculates the pairs without
			 *  duplicates and reverse groups
			 */
 
			answer += x * (x - 1) / 2;
		}
 
		io.println(answer);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
n = int(input())
arr = map(int, input().split())
 
residue_counts = [0] * n
partial_sum = 0
residue_counts[partial_sum] = 1
for a in arr:
	partial_sum += a
	partial_sum = partial_sum % n
	residue_counts[partial_sum] += 1
 
# each subarray with sum divisible by n corresponds to
# a pair of indices that have the same residue
print(sum(r * (r - 1) // 2 for r in residue_counts))
Fundamentos