Not just skip counting

First, we claim that, if $z = e^{2\pi i/p}$ , for some prime number $p$ , and, for some real numbers $a_0, a_1, a_2, \dots, a_{p - 1}$ ,

$a_0 z^0 + a_1 z^1 + a_2 z^2 + \cdots + a_{p - 1} z^{p - 1} = 0,$

then $a_0 = a_1 = a_2 = \cdots = a_{p - 1}$ . To prove this, just note that the polynomials $a_{p - 1} x^{p - 1} + a_{p - 2} x^{kp- 2} + \cdots + a_1 x + a_0$ and $x^{p - 1} + x^{p - 2} + \cdots + x + 1$ share a common root, so that the second polynomial is a factor of the first. Since $x^{p - 1} + x^{p - 2} + \cdots + x + 1$ is irreducible in real numbers, this can only occur if $a_0 = a_1 = \cdots = a_{p - 1}$ .

Now for the main proof. Let $a_n$ be the number of subsets of $A$ such that the sum of the elements of each subset is $\equiv n \pmod{31}$ , and let $z = e^{2\pi i/31}$ . It is not difficult to see that

$\begin{aligned} \sum_{n = 0}^{30} a_n z^n &= 1 + \sum_{1 \leq k \leq 2015} z^k + \sum_{1 \leq k_1 < k_2 \leq 2015} z^{k_1 + k_2} + \cdots \\ & \quad \quad \quad + \sum_{1 \leq k_1 < k_2 < \cdots < k_{2015} \leq 2015} z^{k_1 + k_2 + \cdots + k_{2015}}. \end{aligned}$

(The large summations just mean that, for each subset of $A$ , take $z$ to the power of the sum of the elements of that subset e.g. for $\{1, 2, 3\}$ , there is a $z^6$ term

Now, notice that the crazy summation we got is actually equal to the sum of the coefficients of the polynomial

$(x + z)(x + z^2)(x + z^3) \cdots (x + z^{2015}),$

which, after simplifying using $z^{31} = 1$ , is

$[(x + 1)(x + z)(x + z^2) \cdots (x + z^{30})]^{65}.$

The expression can then be factored as $(x^{31} + 1)^{65}$ , which has sum of coefficients $2^{65}$ . Thus,

$\sum_{n = 0}^{30} a_n z^n = 2^{65},$

and, by our lemma, we have $a_0 - 2^{65} = a_1 = a_2 = \cdots = a_{30}.$ The total number of subsets is $2^{2015}$ , which is the sum of all the $a_n$ s. Finally, we get

$\begin{aligned} a_0 + a_1 + a_2 + \cdots + a_{30} &= 2^{2015} \\ a_0 + 30(a_0 - 2^{65}) &= 2^{2015} \\ 31a_0 - 30(2^{65}) &= 2^{2015} \\ a_0 &= \frac{2^{2015} + 30(2^{65})}{31} \\ a_0 &= \frac{2^{66}(2^{1949} + 15)}{31}, \end{aligned}$

and $p + q + r = 66 + 1949 + 15 = 2030 \equiv \boxed{30} \pmod{100}$ .