Pretty much the title. Source: https://open.kattis.com/problems/classicalcounting
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Pretty much the title. Source: https://open.kattis.com/problems/classicalcounting
Name |
---|
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:
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:
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. ;)
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?
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.
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)
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.