Moltiplicazioni polinomiali e conteggio

Question

Mi sono imbattuto nel seguente problema. Dato un insieme di $ n $ interi positivi $ A $ e un numero intero $ k $. Permettere $ S $ essere l'insieme di numeri interi che sono la somma di $ k $ numeri interi distinti in $ A $. Matematicamente parlando$$ s = {s; text {esiste} p in {a scegli k} text {tale che} s = sum_ {a in p} a }. $$L'oggetto del problema è calcolare $ S $ e per ogni intero $ s in s $, dobbiamo trovare quanti sottoinsiemi di $ A $ di dimensioni $ k $ ci sono quel somma fino a $ s $.

I vincoli: $ k $ è molto piccolo (può essere considerato costante) e sto cercando qualcosa di subquadratico in $ n $.

---

Ho provato a formulare il problema come problema di moltiplicazione polinomiale e risolverlo usando FFT. Quindi ho costruito il polinomio $ rho $ come segue. Ho iniziato con $ rho = 0 $ e per ogni elemento $ a in un $, Ho aggiunto $ x^a $ a $ rho $. Ora per ogni esponente $ r $ in $ rho^k $, il coefficiente rappresenta il numero di combinazioni di $ k $ elementi in $ A $ quella somma fino a $ r $. Tuttavia, queste combinazioni includono l'utilizzo dello stesso elemento più di una volta e contano riordini dello stesso sottoinsieme.

Ho provato le seguenti idee:

• Ricostruire il mio polinomio per contare meglio.
• Costruire e moltiplicare diversi polinomi che rappresentano ciascuno una parte del problema (con una sorta di tecnica di divisione e conquista).
• Modifica il polinomio risultante dalla moltiplicazione con alcuni argomenti combinatori (sottrarre i numeri derivanti dal conteggio due volte ecc.). Questo aiuta quando $ rho^2 $ ma non è riuscito a farlo funzionare per valori più elevati di $ k $.

Apprezzo qualsiasi pensiero o suggerimento sul problema :)