I think these comments may be helpful.

I will assume that we have some polynomial or multinomial (perhaps with monomials from some restricted set) and an oracle which instantly returns the value at any given point (perhaps from a restricted domain). We wish to find a specific coefficient and wonder how many queries we need to make and how hard the calculation would be. Each query gives a linear combination of the various coefficients so we wonder how small a system of equations (drawn from the restricted class available to us) suffices. I would expect that in general (but not always) $m$ queries would be required where $m$ is the potential number of monomials. So it (often) takes as many queries to get one particular coefficient as to get them all.

Consider first this problem: Given a polynomial $\sum_0^na_nx^n$ find $a_i.$ Then $a_0=f(0).$ But it would take $n+1$ queries to specify any other coefficient or even to find $a_0$ if we were not allowed to ask about $f(0).$ At that point we could find them all. If we had an upper bound $\max_i(|a_i|)\lt B$ and wanted $a_n$ then $|a_n-\frac{f(N)}{N^n}| \lt \varepsilon$ for $N \gt \frac{nB}{\varepsilon}.$ If the coefficients were know to be integers this might be effective.This isn't the given problem so I will not discuss finding $f(e^{2j\pi/n}),$ precomputing the inverse of a Vandermonde matrix or doing successive differences.

Next suppose that we know in advance that the vector of variables is $\mathbf{x}=(x_1,\cdots,x_n)$ and $f(\mathbf{x})=\sum_Sa_S\prod_{i \in S}x_i$ where $S$ varies over the subsets of $[n]=\{1,\cdots ,n\}.$ Then there are $2^n$ coefficients. If our queries need are restricted to $0-1$ vectors then to find $a_S$ would could do $2^{|S|}$ queries (setting all irrelevant variable to $0$) and use inclusion exclusion. If done correctly we could have all $a_T$ for $T \subseteq S$ for the same work. This would seem best possible.

**Minimality** Suppose I tell you in advance that $f=\prod_1^n z_i$ where either $z_i=x_i$ or $z_i=1-x_i.$ Then the coefficient of $x_1x_2\cdots x_n$ is $\pm 1$ and we wish to determine which it is. Then each of the $2^n$ possible queries will return $0$ except a particular one which will tell us everything. If we are lucky we find out in a few queries, but it could take $2^n$ queries.

In this rather restricted case one can technically do it with one evaluation: Set $$x_i=\frac{2^{2^i}}{1+2^{2^i}}.$$

Then the result is a fraction with an odd denominator and numerator $2^{2^k}$ where the bits of $k$ tell us which $z_i=x_i.$

The question as asked concerns linear combinations of monomials in $n$ variables all of degree at most $n.$ There are $\binom{n+k-1}k$ such monomials of degree $k$ so potentially $\binom{2n}n \approx \frac{4^n}{\sqrt{\pi n}}$ summands. In this case, for each $T \subseteq [n]$, $2^{|T|}$ queries suffice to determine the sum of all the coefficients for monomials using positive powers of exactly $\{x_t \mid t \in T\}.$ For $T=[n]$ this sum is, as remarked above, just what we want.

I suspect that if we can't use $0-1$ vectors , for example all the $x_i$ in a query need to be integers at least $2$, then $2^n$ queries would not be enough. Maybe then it would take $\binom{2n}n$ queries.

Here is an interesting case I wondered about. Suppose we explicitly see that $$f=\prod_{i=1}^n\left(\sum_{j=1}^na_{ij}x_j+c_i\right).$$ Then the finding the coefficient in question amounts to computing the permanent of the matrix $A={\huge(}a_{ij}{\huge)}.$ Naively that takes $n!n$ operations. This can perhaps be sped up to $2^nn^2$ or $2^nn.$ Much more than for the determinant. Of course each of our allowed queries instantly gives us the result of many arithmetic operations so it is not contradictory that $2^n$ suffice.

For that matter, we don’t need the information about where $f$ came from. I was just emphasizing that knowing that was no real help. The method here merely uses that $f$ is some linear combination of $\binom{2n}{n}$ monomials.