Number of Cubes
Contest: Codeforces Round 992 (Div. 2)
Difficulty rating: 2700
Tags: combinatorics, dp, math, number theory

Consider a rectangular parallelepiped with sides $$$a$$$, $$$b$$$, and $$$c$$$, that consists of unit cubes of $$$k$$$ different colors. We can apply cyclic shifts to the parallelepiped in any of the three directions any number of times$$$^{\text{∗}}$$$.

There are $$$d_i$$$ cubes of the $$$i$$$-th color ($$$1 \le i \le k$$$). How many different parallelepipeds (with the given sides) can be formed from these cubes, no two of which can be made equal by some combination of cyclic shifts?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains four integers: $$$a$$$, $$$b$$$, $$$c$$$, and $$$k$$$ ($$$1 \le a, b, c \le 3 \cdot 10^6$$$; $$$a \cdot b \cdot c \le 3 \cdot 10^6$$$; $$$1 \le k \le 10^6$$$) — three sides of the parallelepiped and the number of colors of unit cubes.

The second line of each test case contains $$$k$$$ integers $$$d_1, d_2, \ldots, d_k$$$ ($$$1 \le d_1 \le d_2 \le \ldots \le d_k \le 3 \cdot 10^6$$$) — the elements of the array $$$d$$$: the number of cubes of a given color.

It is guaranteed that in each test case the sum of the elements of the array $$$d$$$ is equal to $$$a \cdot b \cdot c$$$.

It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$10 ^ 6$$$.

Output format:
For each test case, print one integer — the number of different parallelepipeds modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first test case, there is only one parallelepiped, which consists of one unit cube.

Possible parallelepipeds in the second test case

Example input:
6
1 1 1 1
1
6 1 1 3
1 2 3
12 1 1 3
2 4 6
3 3 1 2
3 6
2 3 3 2
6 12
72 60 96 4
17280 86400 120960 190080

Example output:
1
10
1160
12
1044
231490207

Editorial:
Recall Burnside's lemma — the number of elements up to an action group is:
$$$$$$\frac{1}{|G|} \cdot \sum_{g \in G} {\sum_{x \in X}{[g x = x]}}$$$$$$
, where $$$[x] = 1$$$ if $$$x = true$$$ and $$$[x] = 0$$$ if $$$x = false$$$.
Let's try to iterate over the elements of the action group — all triplets of numbers $$$[0, a)$$$, $$$[0, b)$$$, $$$[0, c)$$$. When applying a fixed action $$$(i, j, l)$$$, the element moves to this vector. Let's choose a cell and add a vector to it until we reach it again. We have drawn a cycle — all cells on it must be of the same type. An example of such a traversal for $$$(a, b, c) = (9, 4, 1)$$$, $$$(i, j, k) = (3, 2, 0)$$$ (each different number in the table corresponds to a cycle):
You can count the cycles by traversal, or you can derive formula: the length of all cycles is the same and equals $$$N = lcm(\frac{a}{gcd(a, i)}, \frac{b}{gcd(b, j)}, \frac{c}{gcd(c, l)})$$$.
What's good about the equal lengths of the cycles? Because the formula for calculating the number of stationary parallelepipeds is simple. First, all $$$d_i$$$ must be divisible by $$$N$$$. Then we distribute them among the cycles. This is the multinomial coefficient for $$$(\frac{d_1}{N}, \frac{d_2}{N}, \dots, \frac{d_k}{N})$$$.
Current total time $$$O(a \cdot b \cdot c \cdot k)$$$: iterated over $$$a \cdot b \cdot c$$$ vector triplets, calculated $$$N$$$, checked divisibility for all $$$k$$$ numbers, and if successful, calculated the multinomial coefficient of size $$$k$$$.
Let's speed up the solution. Let's calculate $$$G = gcd(d_1, d_2, \dots, d_k)$$$. Since all $$$d_i$$$ are divisible by $$$N$$$, then $$$G$$$ is also divisible by $$$N$$$. There are no more different $$$N$$$ than the number of divisors of $$$a \cdot b \cdot c$$$. Let's calculate the number of triplets that give each value of $$$N$$$, and at the end we will calculate the multinomial coefficient for all identical values of $$$N$$$ at once.
The total time is $$$O(a \cdot b \cdot c \cdot \log C + d(a \cdot b \cdot c) \cdot k)$$$, where $$$d(x)$$$ — is the number of divisors of $$$x$$$, and $$$\log$$$ appears due to the calculation of $$$gcd$$$.
Let's continue to speed up the solution. There are two solutions further.
Solution 1.
Let's look again at the formula $$$N = lcm(\frac{a}{gcd(a, i)} \dots)$$$. For convenience, we will focus on the first element. Let's say we want the first element to be $$$x = \frac{a}{gcd(a, i)}$$$. Then $$$x$$$ is divisible by $$$a$$$ and $$$\frac{a}{x} = gcd(a, i)$$$. $$$i$$$ is divisible by $$$gcd(i, \dots)$$$, so $$$i$$$ is divisible by $$$\frac{a}{x}$$$. Then the possible $$$i$$$ are of the form $$$p \cdot \frac{a}{x}$$$, where $$$1 \le p \le x$$$, and the equality $$$gcd(a, \frac{a}{x}) = \frac{a}{x}$$$ is exactly satisfied. $$$p$$$ is coprime to $$$x$$$, otherwise the value of $$$gcd$$$ will be multiplied by their common divisor and the equality will be violated. Therefore the number of suitable $$$x$$$ is equal to $$$phi(x)$$$, where $$$phi(x)$$$ — Euler's function.
So, let's enumerate triplets of divisors of $$$a$$$, $$$b$$$ and $$$c$$$. The number of ways to obtain a triple $$$(x, y, z)$$$ is equal to $$$phi(x) \cdot phi(y) \cdot phi(z)$$$. Let's calculate $$$phi(x)$$$ using the Sieve of Eratosthenes.
We get a solution in $$$O(d(a) \cdot d(b) \cdot d(c) \cdot \log C + d(a \cdot b \cdot c) \cdot k)$$$ and $$$O(a \cdot b \cdot c \cdot \log \log (a \cdot b \cdot c))$$$ for pre-calculation.
Solution 2.
Let's calculate the same $$$N$$$ using dynamic programming. For convenience, we denote the dimensions of $$$a$$$, $$$b$$$, and $$$c$$$ by the array $$$a_i$$$. Let $$$dp[i][j]$$$ be the number of ways, having passed $$$i$$$ dimensions, to obtain $$$lcm$$$ equal to $$$j$$$. The transitions will be as follows: we will iterate over the pairs of the previous $$$lcm$$$ $$$t_1$$$ and the next divisor $$$t_2$$$ of the size of the next dimension $$$a_i$$$. Then the new $$$lcm$$$ will be equal to $$$lcm(t_1, t_2)$$$ and we make the transition $$$dp[i + 1][lcm(t_1, t_2)] += dp[i][t_1] \cdot cnt[i][t_2]$$$, where $$$cnt[i][j]$$$ — the number of such $$$x$$$ that $$$\frac{a_i}{gcd(a_i, x)} = j$$$.
How to calculate the array $$$cnt[i][j]$$$. We cannot calculate it trivially in $$$O((a + b + c) \cdot \log C)$$$, since it is too long time. For simplicity, we calculate the array $$$cnt2[i][j]$$$ equal to the number of $$$x$$$ such that $$$gcd(a_i, x) = j$$$. We iterate over the divisors of $$$a_i$$$ in ascending order. Let the current divisor be $$$d_1$$$. Add $$$\frac{a_i}{d_1}$$$ to $$$cnt2[i][d_1]$$$, since that many $$$x$$$ will be divisible by $$$d_1$$$. Those $$$x$$$ that are divisible by $$$d_1$$$ but are not equal to it, we will subtract later. We iterate over the divisors $$$d_2$$$ of $$$d_1$$$. We subtract $$$cnt2[i][d_1]$$$ from $$$cnt2[i][d_2]$$$, since their $$$gcd$$$ is actually not $$$d_2$$$, but $$$d_1$$$ or a number that $$$d_1$$$ divides. Let's calculate $$$cnt[i][j] = cnt2[i][\frac{a_i}{j}]$$$.
If we pre-calculate the divisors of all numbers and compress their "coordinates", we get a solution in $$$O(d(a \cdot b \cdot c)^2 \cdot \log C + d(a \cdot b \cdot c) \cdot k)$$$.