So I'm having the following problem, which appeared in my university programming contest.
Problem: Given positive integers $$$M$$$ and $$$N$$$ $$$(1\le M\le 500,\,1\le N\le 100)$$$ and a $$$N$$$-tuple of positive integers $$$(a_1,a_2,...,a_N)$$$ $$$(1\le a_i\le 10,\, 1\le i\le N)$$$. Find the number of positive integers $$$N$$$-tuple $$$(k_1,k_2,...,k_N)$$$ such that $$$a_1k_1+a_2k_2+\cdots+a_Nk_N=M$$$.
Input: First line will be $$$N$$$ and $$$M$$$ $$$(1\le M\le 500,\,1\le N\le 100)$$$. Second line will be the tuple $$$(a_1,a_2,...,a_N)$$$ $$$(1\le a_i\le 10,\, 1\le i\le N)$$$.
Output: The number of solutions of the equation.
At the very first step just subtract the sum of all the coefficients from M, since this will allow us to use zeroes in the tuple, which is very helpful.
First precompute number of ways to sum up to a given value after using a certain number of numbers (dp[sum][count_numbers_used]). Should be M^3. Include zeroes. This is also helpful because it takes order into account already.
Group the coefficients into bins of 10, since each coefficient is from 1 to 10. Then do a dp with [current_coefficient][sum]. At each step of the current_coefficient find number of ways to get every value from 0 to 500 using only numbers with that certain coefficient. This is obtainable from the precomputation in constant time (just divide the target sum you're adding by the coefficient). The end result will just be dp[N][M]. This step will take NM^2.
Total complexity is M^3.
Just a small question: 500^3 seems to be greater than 10^9. Is it possible that the run time exceeds one second?
500^3 = 1.25e8
Oops that is a silly mistake.