For the first subtask, dynamic programming suffices. More specifically, let ~dp[n][m]~ be the number of sequences with ~n~ elements and sum to exactly ~m~. It is easy to see that ~dp[n][m]=\sum_{i=1}^K dp[n-1][m-a_i]~. So transition can be done in ~\mathcal{O}(K)~.

Time Complexity: ~\mathcal{O}(NMK)~

For the second subtask, some math (e.g. generating functions, stars and bars) yields a closed form. It is well-known that the number of ways to add ~n~ non-negative numbers to sum to ~s~ is ~\binom{s+n-1}{s}~. So the final answer is going to be:

$$\displaystyle -N+\sum_{s=0}^M \binom{s+N-1}{s}$$

The ~-N~ is because ~M~ is not in the set. Then by the hockey-stick identity, this sum becomes:

$$\displaystyle -N+\binom{M+N}{M}$$

This can be easily calculated in ~\mathcal{O}(M \log M)~.

Time Complexity: ~\mathcal{O}(M \log M)~

For the third subtask, note that there are at most ~M~ non-zero elements in the sequence. Using the dynamic programming solution from the first subtask, we can compute the number of sequences without using any ~0~'s using a certain number of terms in ~\mathcal{O}(M^2K)~. Then with a little math, we can find the number of sequences which have a certain number of non-zero terms and the rest ~0~.

Time Complexity: ~\mathcal{O}(M^2K)~

For the final subtask, we use the ~\times 2, +1~ trick mentioned here. If ~dp1[i]~ is the number of sequences of length ~n~ which sum to exactly ~i~ and ~dp2[m]~ is the number of sequences of length ~2n~ which sum to exactly ~m~, then

$$\displaystyle dp2[m] = \sum_{i=0}^m dp1[i] \times dp1[m-i]$$

A similar formula can be found to calculate the number of sequences of length ~n+1~. So instead of checking all ~n~'s, only ~\mathcal{O}(\log_2N)~ are necessary. Note that this is equivalent to exponentiation by squaring and is much more obvious if this problem is interpreted as a matrix multiplication problem or interpreted with its generating function.

Time Complexity: ~\mathcal{O}((M^2+MK) \log N)~