Zählzahl von Subsequenzen mit gegebenen k modulo Summe

Question

ein Array a von n ganzen Zahlen gegeben, zählen, wie viele Subsequenzen (nicht aufeinander folgenden auch) haben sum % k = 0:

1 <= k < 100 
1 <= n <= 10^6 
1 <= a[i] <= 1000 

Eine O(n^2) Lösung ohne weiteres möglich ist, jedoch eine schneller Weg O(n log n) oder O(n) wird benötigt.

Answer 1

Dies ist das subset sum Problem.

Eine einfache Lösung ist folgende:

s = 0 
dp[x] = how many subsequences we can build with sum x 
dp[0] = 1, 0 elsewhere 
for i = 1 to n: 
    s += a[i] 
    for j = s down to a[i]: 
     dp[j] = dp[j] + dp[j - a[i]] 

Dann können Sie einfach die Summe aller dp[x] so dass x % k == 0 zurückzukehren. Dies hat jedoch eine hohe Komplexität: etwa O(n*S), wobei S die Summe aller Ihrer Elemente ist. Das Array dp muss auch die Größe S haben, die Sie wahrscheinlich nicht einmal für Ihre Einschränkungen deklarieren können.

Eine bessere Lösung besteht darin, nicht über Summen, die größer oder gleich k sind, zu iterieren. Um dies zu tun, werden wir 2 dp Arrays verwenden:

dp1, dp2 = arrays of size k 
dp1[0] = dp2[0] = 1, 0 elsewhere 
for i = 1 to n: 
    mod_elem = a[i] % k 
    for j = 0 to k - 1: 
     dp2[j] = dp2[j] + dp1[(j - mod_elem + k) % k] 

    copy dp2 into dp1 

return dp1[0] 

deren Komplexität ist O(n*k) und ist optimal für dieses Problem.

Answer 2

Es gibt einen O(n + k^2 lg n) -Zeitalgorithmus. Berechnen eines Histogramms c(0), c(1), ..., c(k-1) des Eingangsarrays mod k (d. H. Es gibt c(r) Elemente, die r mod k sind). Dann berechne

wie folgt, wobei der konstante Ausdruck des reduzierten Polynoms die Antwort ist.

Anstatt jeden Faktor mit einer schnellen Exponentiationsmethode zu bewerten und dann zu multiplizieren, drehen wir die Dinge um. Wenn alle c(r) Null sind, lautet die Antwort 1. Andernfalls bewerten rekursiv

 k-1 
P = product (1 + x^r)^(floor(c(r)/2)) mod (1 - x^k). 
     r=0 

und dann

 k-1 
Q = product (1 + x^r)^(c(r) - 2 floor(c(r)/2)) mod (1 - x^k), 
     r=0 

in Zeit O(k^2) für die letztere Berechnung berechnen, indem die Spärlichkeit der Faktoren nutzen. Das Ergebnis ist P^2 Q mod (1 - x^k), berechnet in der Zeit O(k^2) über naive Faltung.

Answer 3

Traverse a und zählen a[i] mod k; es sollte k solche Zählungen geben.

Recurse und Memoize über die verschiedenen Partitionen von k, 2*k, 3*k...etc. mit Teilen kleiner oder gleich k, die Produkte der entsprechenden Zählungen hinzufügen.

Wenn beispielsweise k10 wären, wären einige der Partitionen 1+2+7 und 1+2+3+4; aber während des Memoisierens müssten wir nur einmal berechnen, wie viele Paare mod k im Array (1 + 2) produzieren.

Zum Beispiel k = 5, a = {1,4,2,3,5,6}:

counts of a[i] mod k: {1,2,1,1,1} 

products of distinct partitions of k: 
    5 => 1 
    4,1 => 2 
    3,2 => 1 

products of distinct partitions of 2 * k with parts <= k: 
    5,4,1 => 2 
    5,3,2 => 1 
    4,1,3,2 => 2 

products of distinct partitions of 3 * k with parts <= k: 
    5,4,1,3,2 => 2 

answer = 11 

    {1,4} {4,6} {2,3} {5} 
    {1,4,2,3} {1,4,5} {4,6,2,3} {4,6,5} {2,3,5} 
    {1,4,2,3,5} {4,6,2,3,5}