First, since all sequences of choices have same probability to occur, we can turn it into a counting problem and divide the answer by the number of possibility, that is

where $$$ope_m$$$ represent the sequence of operation done to the array $$$b_n$$$($$$ope_i \in [1, n] \text{ }\forall i$$$).

At first glance, the problem seems to have too much stuff going on, so let's try to solve a more constrained version(invent subtasks) and see if we can generalize the solution back to the original problem later.

Subtask: $$$v = 1, a_i = 0 \text{ }\forall i \in [1, n]$$$, operations are point add rather than suffix add

Since constraints on $$$a_n$$$ and $$$v$$$ feel like a "noise" and not related to the core of the problem, also doing suffix add feels a bit annoying, let's get rid of them first. How can we solve this problem?

Assume we label element added at the $$$i$$$-th operation with $$$i$$$, then by the product trick, we can think of $$$\prod_\limits{i = 1}^n b_i$$$ as counting the number of ways to pick one element from each entry of sequence $$$b_n$$$, then we can further enumerate all possible choices of elements, that is

where $$$c_i$$$ represents the label of element chosen in $$$i$$$-th entry, and we only need to consider sequences satisfy $$$c_i \in [1, m] \text{ }\forall i, c_i \neq c_j \forall i \neq j$$$

Then using contribution to the sum trick (or swapping sigma/double counting...), we get

Which boils down to a simple combinatoric problem, for a fixed $$$c_n$$$, we can freely distribute elements not in $$$c_n$$$, and there are $$$\frac{m!}{(m-n)!}$$$ possible $$$c_n$$$ we need to consider, thus the answer will be

Now, let's lift the constraints one by one, trying to generalize the solution back to the original problem.

Subtask: $$$v = 1, a_i = 0 \text{ }\forall i \in [1, n]$$$

I decide to lift the suffix add constraint first because it feels more related to the core of the problem. How is this modification change our solution?

Since adding suffix $$$[i, n]$$$ should be equivalent to adding elements of same label to all entries in $$$[i, n]$$$, the condition $$$[\text{element }c_i\text{ belongs to i-th entry }\forall i]$$$ should be equivalent to $$$[ope_{c_i} \leq i \text{ }\forall i]$$$ rather than the above one, and it is possible to pick element of same label from different entries, thus condition for $$$c_n$$$ become just $$$c_i \in [1, m]$$$, so we can no longer assume the number of free elements is $$$m - n$$$. Which give us

Now the stuffs start to get complicated and can't be dealt with a simple formula, so instead of deriving a formula, let try to use the following DP to handle this.

About the transition, since we can let $$$c_{i + 1}$$$ be either an already appeared element or a new one, and if it is a new one, we should also determine the choice of respective operation, which have $$$(i + 1)$$$ possibility by the new condition we just stated above, so the transitions should be

and we consider the choices of free elements and permute elements in $$$c_n$$$ by multiplying some factor afterward, which gives us the answer

the original problem

Finally, let try to deal with constraint on $$$v$$$ and $$$a_n$$$, for $$$v$$$, the only change is that there are $$$v$$$ elements of same label added to a single entry rather then one element, thus we can choose $$$1$$$ elements out of $$$v$$$ elements from every entry. And for $$$a_n$$$, we can just let there be some extra elements before we do the operation, and when consider $$$i$$$-th slot, except choosing an element come from the operations, we can also choose the one already in the entry before the operations, which gives us the following transitions

and the final answer will be

After the long long thinking on the problem, all we need to do is to write a few line of code, which is amazing!

Conclusion

When solving this problem, I feel myself using a lot of techniques and problem solving skill I've ever learnt in my entire CP journey, and even I've known these stuffs for a fairly long time, I still got fascinated by the solution itself, especially the process of clarifying the core of the problem model by inventing proper subtasks, and the powerfulness of turning a counting problem into formula, which can lead further to the usage of some common techniques (product trick, contribution to the sum, DP, etc...)

Though I feel the whole solving path is a bit too long for me to solve it during contest, so if you have any shorter/smarter way to come up with the solution, please let me know by commenting below, I would be appreciated.

And finally, thanks for your reading and I hope this blog gives you some insights of problem solving :)