I have an intuition that re-casting the Poisson binomial distribution probability mass function in the following way might lead to a more elegant closed form than the DFT approach:

Sum the base 2 logs of the probabilities of each independent trial. The negation of that sum is equivalent to a new number of trials each of which has a p=1/2. Of course, if all the p's start as 1/2 the number of trials will be unchanged and one can degenerate the existing formulas accordingly to yield an O(n) solution. But if the p's differ, something else must be done (for example, because not every p=1/2 trial is independent).

My conjecture (or perhaps "wishful thinking" is more appropriate) is that there is an O(n) closed form which will tell how one must re-scale the desired number of successful trials (k) to yield the PBD's pmf if applied to the transform in which all p's are equal to 1/2 but are not independent.