### MS1908's blog

By MS1908, history, 18 months ago,

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.

• +13

 » 18 months ago, # |   0 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.
•  » » 13 months ago, # ^ |   0 Just a small question: 500^3 seems to be greater than 10^9. Is it possible that the run time exceeds one second?
•  » » » 13 months ago, # ^ |   +8 500^3 = 1.25e8
•  » » » » 13 months ago, # ^ | ← Rev. 3 →   0 I think there exists an $O(M*N)$ solution that uses the same technique for unbounded knapsack. Let's $M' = M - \sum_{i} a_i$ And $S(i, j)$ be the number of tuples $(k_1, ..., k_i)$ that $\sum_{t=1}^{i} a_t * k_t = j$ We have: $S(i, j) = S(i - 1, j) + S(i - 1, j - w_i)$The answer is $S(N, M')$. Reference: An FPTAS for #Knapsack and Related Counting Problems
•  » » » » 13 months ago, # ^ |   0 Oops that is a silly mistake.
 » 13 months ago, # | ← Rev. 5 →   0 Edit: I am talking about finding number of non-negative tuples. A little modification of the above problem. A long time ago, I found an $O(S * n + S * logS * logM), S = \sum_{i} a_i$ solution for this problem. The idea is to represent $f(x)$, the number of tuples when $M = x$, as a linear recursive sequence: $f(x) = \mathop{{\sum_{i} f(x - a[i])}} - \mathop{\sum_{i < j} f(x - a[i] - a[j])} + \mathop{\sum_{i < j < k} f(x - a[i] - a[j] - a[k])} - ...$Then use companion matrix to calculate $M-th$ element fast. P/S: If the terms companion matrix or Cayley Hamilton are strange to you. You should read an article in codechef here to understand how to do fast calculation for recursive sequence.My implementation that works in $O(S * n + S^2 * logM)$: ideone Use FFT instead of simple polynomial multiplication will make it $O(S * n + S * logS * logM)$I don't recall much, but there's exist an algorithm that uses something like $dp[0..a_0 - 1][0..a_1 - 1]...[0..log10(M)]$ and works in about $O(log_{10}(M) * \mathop{{\prod_{i} a_i}})$.These solution are pretty good but do not satisfy me. I try searching for an improvement but couldn't. So I want to ask: - Is there exist a better solution for $1 \leq S \leq 10^5$. Something like $O(S * n + S * logM)$?
 » 13 months ago, # |   0 I've added a harder version of this problem to SPOJ: COUNTDIO where $1 \leq M \leq 10^{18}$ and $1 \leq \sum_{i} a_i \leq 60 000$. Enjoy solving.