The number of sequences in which specific \(i\) elements of the \(N\) elements is a square number (while the remaining \((N-i)\) can be or be not) can be expressed using formal power series as follows:

\(\displaystyle \prod_{j=1}^{K} [x^{E_j}] \frac{1}{(1-x^2)^{i}(1-x)^{N-i}}.\)

With inclusion-exclusion principle, the sought count can be expressed as follows:

\(\displaystyle \sum_{i=0}^{N} (-1)^i {N \choose i} \prod_{j=1}^{K} [x^{E_j}] \frac{1}{(1-x^2)^{i}(1-x)^{N-i}.}\)

Now we consider how to evaluate it.

Since \(\displaystyle \frac{1}{(1-x^2)^{i}(1-x)^{N-i}}\) is only dependent on \(i\), it is sufficient to evaluate this expression for each \(i=0,1,\dots,N\). Naive evaluation costs \(O(ND^2)\) time, where \(D\) is the degree to maintain (this time, about \(D=10000\) is sufficient), but we want to reduce it to about \(O(ND)\).

First of all, \(\displaystyle \frac{1}{(1-x)^{N}} = (1 + x + x^2 + \dots)^N\) can be found by computing cumulative sums \(N\) times.
Then we update the expression for \(i=k\) to \(i=k+1\). Several approaches are possible.

Approach \(1\): multiply by \(\displaystyle \frac{(1-x)}{(1-x^2)}\)

First, multiplying by \((1-x)\) is achieved by finding the differences of adjacent terms (this corresponds to undoing multiplication by \(\displaystyle \frac{1}{(1-x)} = 1 + x + x^2 + \dots\)).
Then, multiplying by \(\displaystyle \frac{1}{(1-x^2)} = 1 + x^2 + x^4 + \dots\) is achieved by taking the cumulative sums of every other terms.

Sample code (C++)

Approach \(2\): deform \(\displaystyle \frac{(1-x)}{(1-x^2)}\)

Since \(\displaystyle \frac{(1-x)}{(1-x^2)} = \frac{(1-x)}{(1-x)(1+x)} = \frac{1}{(1+x)}\), it is sufficient to multiply this.
Multiplying by \(\displaystyle \frac{1}{(1+x)} = 1 + (-x) + (-x)^2 + \dots = 1 - x + x^2 - \dots\) is achieved by swapping the sign while finding the cumulative sums.

Sample code (C++)

In summary, formal power series immediately reveals the equivalence between two approaches that seems difference at a glance.