adaptatron's blog

By adaptatron, 2 months ago, In English

The editorial of problem ABC370G: Divisible by 3 from last Atcoder Beginner Contest contains an interesting subproblem : How to count the number of arrays of length $$$L$$$ where product of all elements is $$$P$$$? The editorial mentions that this is a good exercise for Blue/Yellow coders, so I created a blog talking about this idea.

https://cfstep.com/training/tutorials/math/count-arrays-with-fixed-product/

To help you verify correctness, I also created a practice problem : https://codeforces.net/group/7Dn3ObOpau/contest/549784

The problems are untested, if you see any issues with the model solution, do let me know in the comments.

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

Haven't read the question nor the solution, but based on title:
prime factorize the number, let it be $$${p_1}^{a_1} \cdot {p_2}^{a_2} \cdot {p_3}^{a_3} ... \cdot {p_m}^{a_m}$$$.
The answer of the question is the number of ways to distribute $$$a_1$$$ number of $$$p_1$$$ into $$$L$$$ integers, then $$$a_2$$$ $$$p_2$$$s etc. which is the product of the number of ways to solve this equation $$$x_1 + x_2 + x_3 + \cdots + x_L = a_i$$$ for each i from 1 to m, where all $$$x_i$$$s are non-negative integers which has the solution of $$$C(a_i + L-1, L-1)$$$ where $$$C(n, r)$$$ denotes the number of ways to choose r out of n objects, unordered
So the general answer is:

$$$\prod_{i=1}^{m} {C(a_i + L - 1, L - 1)}$$$