pabloskimg's blog

By pabloskimg, history, 5 years ago, In English
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

The problem can be cracked down as "Find the number of non-negative integer solutions for the equation $$$a_1 + a_2 + \ldots + a_n = k$$$, with $$$0 \le a_1, a_2, \ldots, a_n \le m$$$."

Without regarding the complexity, there is an inclusion-exclusion-based solution as of following:

  • Denote $$$S_{mask}$$$ ($$$0 \le mask < 2^n$$$) as the number of integer solutions for the above equation, with $$$mask$$$ being the bitmask saying which of the unknown variable $$$a_i$$$ would have the criteria $$$a_i \ge m+1$$$ considered. For example, if $$$n = 3$$$, $$$S_5$$$ will count the number of solutions with only $$$a_1$$$ and $$$a_3$$$ having their lower-bound limited.
  • The answer would be $$$\displaystyle \sum_{mask = 0}^{2^n - 1} (-1)^{bitcount(mask)} \times S_{mask}$$$, with $$$bitcount(mask)$$$ being the number of $$$1$$$ bit in the binary notation of $$$mask$$$.

One can obviously see that this solution is way too slow. However, the trick is that if a variable is bounded, no matter which one, the lower-bound limit would always be $$$m+1$$$. This makes all variables being equal, and without loss of generality, we can merge all the $$$mask$$$ value with the same $$$bitcount(mask)$$$ to calculate at one instance.

From here, our solution will become:

  • Iterate value $$$i$$$ — the number of variables having their lower-bound limited in the equation — from $$$0$$$ to $$$n$$$.
  • One can see that such equation can be transformed into such with no variables being bounded anyhow (except of the mandatory of being non-negative) by subtracting from both sides all the lowerbound values, thus, as a result, if $$$k - i(m+1) < 0$$$, obviously no solution would exist.
  • Otherwise, denote the number of solutions as $$$C_i$$$, we can see that $$$C_i = \binom{n+k-i(m+1)-1}{n-1} \times \binom{n}{i}$$$, with $$$\binom{n+k-i(m+1)-1}{n-1}$$$ being the number of solutions for each equation of our considering form, $$$\binom{n}{i}$$$ being the number of equations possible (in other words, the number of ways to pick $$$i$$$ variables to have their lower-bound raised to $$$m+1$$$).
  • Add $$$(-1)^i \times C_i$$$ to the final answer.

Last but not least, the module in this problem ($$$10^6+7$$$) is unusual — it is a compound of two primes, $$$29$$$ and $$$34483$$$. Therefore, we should calculate separately with each prime as a independent modulo (please take note that from $$$1$$$ to $$$10^5$$$ there might include some multiples of those primes as well), and merge the answer using either Chinese Remainder Theorem or brute force (since the final module is small, one can try out all possible values from $$$0$$$ to $$$10^6+6$$$).

Total complexity would be $$$\mathcal{O}(n \log(mod))$$$, or $$$\mathcal{O}(mod)$$$ if you decide to brute force the remainder after calculating the individual steps. ;)

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks @thuytrang12a2 for the answer. I couldn't follow your explanation because I didn't understand the definition of $$$S_{mask}$$$ to begin with. If the i-th bit in mask is 1, then $$$a_i \geq m + 1$$$, however, that contradicts the constraint that $$$0 \leq a_i \leq m$$$. In other words, it's impossible to satisfy $$$m+1 \leq a_i \leq m$$$. Therefore I couldn't understand $$$S_{mask}$$$ and consequently I didn't understand the summation formula either.

    I also didn't understand why you would need to use CRT or anything special to compute the operations modulo $$$10^6 + 7$$$ because it's not a prime number. Why can't we just compute everything modulo $$$10^6 + 7$$$ and that's it? Why do we need to do something special if the modulo is not prime?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      It's pretty hard to explain all at once, coz' in the comment she just assumed that you'd already known some concepts about discrete math and number theory, but I'll just try.

      If the i-th bit in mask is 1, then $$$a_i≥m+1$$$, however, that contradicts the constraint that $$$0≤a_i≤m$$$. In other words, it's impossible to satisfy $$$m+1≤a_i≤m$$$.

      First of all, in case you haven't already known:

      Given an equation $$$a_1 + a_2 + \ldots + a_n = k$$$ with all variables being non-negative (no upper-bound here), the number of distinct solutions for it would be $$$\binom{n+k-1}{n-1}$$$.

      This is a well-known theorem, you can read more about it here, or read an explanation here.

      The catch is, this theorem only works when the variables have no upper-bound limits. In fact, as far as I know, there's no "simple" solutions for such situations either. Therefore, she had to use "an inclusion-exclusion-based solution".

      By using those $$$S_{mask}$$$, she is not directly considering the subsets of the solution sets. All the $$$S_{mask}$$$, if portrayed geometrically, will be something similar to a Venn diagram, in which we need to figure out the area of $$$S_0$$$ that does not intersect with any other $$$S_{mask}$$$ with $$$1 \le mask < 2^n$$$.

      The process of finding such area is a basic concept in Inclusion-Exclusion principle. The blog post from the first commentator would help you with that.

      (Actually, if you get the idea and come back to her comment, I can say that all the formula she presented are just the consequences of those basic principles)

      I also didn't understand why you would need to use CRT or anything special to compute the operations modulo $$$10^6+7$$$ because it's not a prime number. Why can't we just compute everything modulo $$$10^6+7$$$ and that's it? Why do we need to do something special if the modulo is not prime?

      Because of the division, which is the only basic math operations that couldn't be done normally. Think of it, in normal circumstances, $$$15 \div 5 = 3$$$; yet with a modulo, for example, $$$mod = 6$$$, then $$$(15 \mod 6) \div (5 \mod 6)$$$ isn't even an integer, let alone being equal to $$$3 \mod 6$$$.

      It's even worse when it comes to the idea of modular multiplicative inverse. It's the way to perform the modular division right, but even that this is not a guaranteed-to-exist operation.

      Take this from the link I just cited: "Not every element of a complete residue system modulo m has a modular multiplicative inverse, for instance, zero never does.".

      Prime number modulo could guarantee the modular division to happen, as stated from the Euler's theorem.