H: Let's say $$$g(a) = \displaystyle \prod_{i=1}^{q} (a_i + i) + \sum a_i 2^{i-1}$$$

Call the frequency sequence of $$$a$$$ to be the sequence $$$f$$$, where $$$f_i$$$ is the frequency of $$$i$$$ in $$$a$$$. We'll prove that for some frequency sequence $$$f$$$ with all values < $$$q$$$, the sum of $$$g(a)$$$ over all permutations $$$a$$$ with frequency sequence $$$f$$$ is $$$0$$$ and hence, it is enough to just consider arrays with all values same to solve the problem.

To find the sum, we can consider all values different and divide by $$$\prod f_i!$$$.

$$$ \displaystyle \sum_{\sigma} \prod_{i=1}^{q} (a_{\sigma_i} + i)$$$ = $$$\displaystyle \sum_{S \subseteq [q]} \prod_{i \in S} i \prod_{j \notin S} a_{\sigma_j} $$$

= $$$\displaystyle \sum_{S \subseteq [q]} \left( \prod_{i \in S} i \right) \left( \sum_{\sigma} \prod_{j \notin S} a_{\sigma_j} \right) $$$

= $$$\displaystyle \sum_{S \subseteq [q]} \left( \prod_{i \in S} i \right) \left( F_{q-|S|} |S|! (q-|S|)! \right)$$$, where $$$F_i$$$ is sum of $$$a$$$ taken $$$i$$$ at a time.

Now, we can iterate on $$$|S|$$$. And our sum becomes:

$$$\displaystyle \sum_{k=0}^{q} F_{q-k} k! (q-k)! \sum_{S \subset q, |S| = k} \prod_{i \in S} i $$$

The final summand is sum taken $$$k$$$ at a time from $$${1, 2, \ldots q}$$$, which is non-zero only for $$$k=0$$$ and $$$k=q-1$$$, as $$$(x+1)(x+2) \ldots (x+q) = x^q - x$$$.

So, our sum becomes $$$F_q 0! q! - F_1 (q-1)! 1! = F_1$$$ = sum of the array $$$a$$$.

Also, $$$\displaystyle \sum_{\sigma} \sum_{i=1}^{q} a_i 2^{i - 1} = \sum_{i} a_i (2^0 + \ldots 2^{q-1}) (q-1)! = F_1 (2^q-1) (q-1)! = -F_1$$$

So, the total sum becomes $$$0$$$ for any $$$f$$$ with all values < $$$q$$$.

J: We can find the expected value of max(0, bacteria inside — bacteria outside) for one petri-dish and multiply by $$$n$$$.

Let $$$x$$$ be the bacteria inside and $$$y$$$ outside. We have a simple process. We go from $$$(x, y) \rightarrow (x, y+1)$$$ with probability $$$y/(x+y)$$$ and $$$(x +1, y)$$$ with probability $$$x / (x + y)$$$.

Initially we have $$$(x, y) = (1, n - 1)$$$. Say in $$$r$$$ minutes $$$a$$$ bacteria were added inside and $$$r-a$$$ outside. The probability of this happening is:

$$$ \displaystyle \dfrac{\binom{r}{a} (n-1) n \ldots (n-1 + r - a - 1) a!}{n (n + 1) \ldots (n + r)} = \dfrac{\binom{n - 2 + r - a}{r - a}}{\binom{n - 1 + r}{r}}$$$.

So, the value after $$$r$$$ minutes is $$$\displaystyle \sum_{a} \dfrac{\binom{n - 2 + r - a}{r - a}}{\binom{n - 1 + r}{r}} \max(0, 2a - n - r + 2)$$$.

We can store prefix sums of $$$\binom{n-2+i}{i}$$$ and $$$i \binom{n-2+i}{i}$$$ (or use hockey stick identity) to find the answer for each $$$r$$$ in $$$O(1)$$$

UPD: Sorry I didn't realize that jtnydv25 had posted the solution above :(

H: The main observation is if the multiset of the digits $$$A = { a_1, a_2, \cdots, a_q }$$$ contains two different numbers, the sum of luckiness over all permutations of these digits will be equal to zero. So you only need to take all numbers with equal digits and add them to the answer. In the contest, I simply guessed the conclusion and used a brute force solution to verify it.

Proof: Note that $$$X = \sum_{\sigma} \prod_{i=1}^q (a_{\sigma(i)} + i) = \sum_{S \subseteq A} f(A) f(S \setminus A) \cdot \left([z^{q-|A|}] \prod_{i=1}^q (z+i)\right) \cdot \prod_{z \in A} z$$$, where $$$f(A)$$$ equals to the number of the permutations of the multiset $$$A$$$ (i.e. $$$f(A) = \binom{|A|}{c_0,c_1,\cdots,c_{n-1}}$$$ ). Since $$$q$$$ is prime, the polynomial $$$\prod_{i=1}^q (z+i) \equiv z^q - z \pmod q$$$, so we have $$$X = f(S)f(\varnothing) \prod_{z \in S} z - \sum_{z \in S} f({z})f(S \setminus {z})\cdot z $$$. For the first term, $$$f(S) = \binom{q}{c_0,\cdots,c_{n-1}} \equiv 0 \pmod q$$$ since the $$$S$$$ contains at least two different numbers. For the second term, note that $$$\sum_{i=0}^{q-1} 2^i = 2^q - 1 \equiv 1 \pmod q$$$, so the overall sum equals to $$$0$$$.

By the way, I don't think this task is suitable for a contest. It's more like a work based on the existing proof, and I didn't do anything in the contest except guess the conclusion...

and how to do that with fft?

You can use the same approach but with sqrt decomposition on queries. It becomes relatively easy to implement.