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 $\log_2$'s 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-number the desired number of successful trials ($k$) so it can be applied to the new number of trials where each has a $p$ of $1/2$, but not all are independent, yielding the same result as one would get from the ordinary PBD pmf.