Multiplications polynômes et comptage

Question

Je suis tombé sur le problème suivant. Étant donné un ensemble de $ n $ entiers positifs $ A $ Et un entier $ k $. Laisser $ S $ être l'ensemble des entiers qui sont la somme de $ k $ entiers distincts dans $ A $. Parlant mathématiquement$$ s = {s; text {il existe} p in {a choisissez k} text {tel que} s = sum_ {a in p} a }. $$L'objet du problème est de calculer $ S $ Et pour chaque entier $ s in s $, nous devons trouver le nombre de sous-ensembles de $ A $ de taille $ k $ il y a cette somme à $ s $.

Les contraintes: $ k $ est très petit (peut être considéré comme constant) et je recherche quelque chose de sous-quadratique dans $ n $.

---

J'ai essayé de formuler le problème en tant que problème de multiplication polynomiale et de le résoudre en utilisant FFT. Alors j'ai construit le polynôme $ rho $ comme suit. J'ai commencé avec $ rho = 0 $ Et pour chaque élément $ a dans un $, J'ai ajouté $ x ^ a $ à $ rho $. Maintenant pour chaque exposant $ r $ dans $ rho ^ k $, le coefficient représente le nombre de combinaisons de $ k $ éléments $ A $ cette résumé à $ r $. Cependant, ces combinaisons incluent l'utilisation du même élément plus d'une fois et des réorganisations de comptage du même sous-ensemble.

J'ai essayé les idées suivantes:

• Reconstruire mon polynôme pour mieux compter.
• Construisez et multipliez différents polynômes représentant chacun une partie du problème (avec une sorte de technique de division et de conquête).
• Modifiez le polynôme résultant de la multiplication avec un argument combinatoire (soustrayez les nombres résultant du comptage deux fois, etc.). Cela aide quand $ rho ^ 2 $ mais ne pouvait pas le faire fonctionner pour des valeurs plus élevées de $ k $.

J'apprécie toute pensée ou indice sur le problème :)