numero conte di sottosequenze con proposta k modulo somma

Question

Dato un array a di n interi, contare quante sottosequenze (non consecutive pure) ha sum % k = 0:

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

Una soluzione O(n^2) è facilmente possibile, tuttavia un modo più veloce è necessario O(n log n) o O(n).

Answer 1

Questo è il problema subset sum.

Una soluzione semplice è questa:

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]] 

Poi si può semplicemente restituire la somma di tutto dp[x] tale che x % k == 0. Questo ha una grande complessità però: circa O(n*S), dove S è la somma di tutti i tuoi elementi. L'array dp deve anche avere la dimensione S, che probabilmente non puoi nemmeno permetterti di dichiarare per i tuoi vincoli.

Una soluzione migliore è quella di non iterare su somme maggiori o uguali a k in primo luogo. Per fare questo, useremo 2 dp array:

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] 

la cui complessità è O(n*k), ed è ottimale per questo problema.

Answer 2

C'è un algoritmo O(n + k^2 lg n) -time. Calcola un istogramma c(0), c(1), ..., c(k-1) della matrice di input mod k (ad esempio, ci sono elementi c(r)r mod). Quindi computare

k-1 
product (1 + x^r)^c(r) mod (1 - x^k) 
    r=0 

come segue, dove il termine costante del polinomio ridotto è la risposta.

Anziché valutare ciascun fattore con un metodo di esponenziazione veloce e quindi moltiplicare, invertiamo le cose. Se tutti gli c(r) sono zero, la risposta è 1. Altrimenti, ricorsivamente valutare

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

e quindi calcolare

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

in tempo O(k^2) per quest'ultimo calcolo sfruttando la scarsità dei fattori. Il risultato è P^2 Q mod (1 - x^k), calcolato nel tempo O(k^2) tramite convoluzione ingenua.

Answer 3

Attraversare a e contare a[i] mod k; ci dovrebbero essere k tali conteggi.

Recurse e memoize sulle partizioni distinte di k, 2*k, 3*k...etc. con parti inferiori o uguali a k, aggiungendo i prodotti dei conteggi appropriati.

Ad esempio, se k erano 10, alcune delle partizioni sarebbero 1+2+7 e 1+2+3+4; ma durante la memoizzazione, dovremmo calcolare solo una volta quante coppie mod k nella matrice producono (1 + 2).

Ad esempio, 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}