Number of $B\subset A$ with $s(B)$ divisible by $n$ I recently saw this IMO $1995$ problem:

How many subsets of $\{1,2,...,2p\}$ are there, with $p$ elements, such that the sum of the elements is divisible by $p$, given that $p$ is a prime, $p\geq 3$.

I solved this using the classical (well not really, but not unheard of) method of considering $a_i$ the number of subsets with $p$ elements whose sum is $\equiv i\pmod{p}$ and then constructing the following polynomial:
$$\sum_{i=0}^{p-1}a_i\cdot\epsilon^i$$
Where $\epsilon$ is the $p^{th}$ primitive root of unity $\big($i.e. $\epsilon=\cos{\frac{2\pi}{p}+i\cdot\sin{\frac{2\pi}{p}}}\big)$, and then using this lemma:

If $\epsilon$ is the $p^{th}$ primitive root of unity, $p\geq 3$ and $p$ is a prime, then: $$\sum_{i=0}^{p-1} a_i\cdot\epsilon^i=0\Leftrightarrow a_0=a_1=...=a_{p-1}$$

And a bit of interpretation, I get that there are $$2+\frac{1}{p}\bigg(\binom{2p}{p}-2\bigg)$$
such subsets. This can be easily generalized in many ways $\big($for example to count all subsets, or count subsets of $\{1,2,..,k\cdot p\}\big)$, as long as $p$ is a prime. However, what should we do with this problem?

How many subsets of $\{1,2,...,an\}$ are there, such that the sum of the elements is divisible by $n$, where $n$ is an arbirary positive integer.

Thank you!
 A: Here is a calculation using something similar to the polynomial you consider. Set $\epsilon = \cos(2\pi /n)+i\sin(2\pi /n)$. For every integer $k\geq 1$, there is a polynomial factorization
$$
\prod_{j=1}^{an} \left(x-\epsilon^{jk}\right) = \left(x^{n/(n,k)}-1\right)^{a(n,k)}.
$$
Also, we have
$$
\sum_{j=1}^{n}\epsilon^{jb}=\begin{cases}n&:n|b,\\0&n\nmid b.\end{cases}
$$
So, the number of subsets $B\subseteq \{1,\ldots,an\}$ with sum divisible by $n$ is
$$
\begin{align*}
\frac{1}{n}\sum_{B\subseteq\{1,\ldots,an\}}\sum_{j=0}^{n-1}\epsilon^{js(B)}&=\frac{1}{n}\sum_{j=1}^{n}\prod_{k=1}^{an}\left(1+\epsilon^{jk}\right)\\
&=\lim_{x\to 1}\frac{1}{n}\sum_{j=1}^{n}\prod_{k=1}^{an}\left(x+\epsilon^{jk}\right)\\
&=\lim_{x\to 1}\frac{1}{n}\sum_{j=1}^{n}\prod_{k=1}^{an}\left(\frac{x^2-\epsilon^{2jk}}{x-\epsilon^{jk}}\right)\\
&=\frac{1}{n}\sum_{j=1}^{n} \lim_{x\to 1}\frac{\left(x^{2n/(n,2j)}-1\right)^{a(n,2j)}}{\left(x^{n/(n,j)}-1\right)^{a(n,j)}}
\end{align*}.
$$
The $j$-th term in the sum is $0$ if $(n,2j)>(n,j)$ (equivalently, $n/(n,j)$ is even), and is $2^{a(n,j)}$ if $(n,2j)=(n,j)$ (equivalently, $n/(n,j)$ is odd). So, if we write $n=2^km$ with $m$ odd, the number of subsets in question is
$$
\begin{align*}
\frac{1}{n}\sum_{\substack{j=1\\n/(n,j)\text{ odd}}}^{n} 2^{a(n,j)}=\frac{1}{n}\sum_{j=1}^m 2^{a2^k(m,j)}=\frac{1}{n}\sum_{d|m}\varphi(m/d)2^{2^kad}.
\end{align*}
$$
I don't know if this sum can be further simplified.
