I think the official editorial of problem G is a little bit hard to understand for me, therefore I write a learning note, with an example, in English:
Google Drive (Typo corrected): https://drive.google.com/file/d/1imUKYXcxQNw8wC28YFeTzEAkBV2wswMo/view?usp=sharing
Tencent Docs (Typo corrected): https://docs.qq.com/pdf/DU2VOa09uYUJHYU9E
The above pdf files do not contain code. My code:
Spoiler
and my submission: 211097938.
Be careful when handling indices! Here is a wrong submission with Runtime Error: 211089726.
Thank you for your notes!
There seem to be small typos though which confused me for a second. For example: it says that "our solution is $$$E\left[\prod_{i = 1}^n(a_i + x_{i, j})\right]$$$" but I imagine you mean $$$E\left[\prod_{i = 1}^n(a_i + \sum_{i = 1} ^ m {x_{i, j}})\right]$$$, because the indicator RV $$$x_{i, j}$$$ you state contributes $$$v$$$ with probability $$$i / n$$$ and contributes $$$0$$$ otherwise and of course this contribution of $$$v$$$ can occur in any of the $$$m$$$ operations not a single one. But so much as I understand, if we basically expand all of the terms out, each term will be of type 1: $$$a_i * x_{u, v}$$$ or type 2: $$$x_{u_1, v_1} * x_{u_2, v_2}$$$. For type 1 EV can be calculated due to independence. And for type 2, we can calculate this EV a little differently. And the use of DP in this problem is so we can calculate these terms more quickly than one by one. Hope my overall understanding of solution is correct.
Thank you for your clarification! You are right, sorry for my typos! That was a typo.
Auto comment: topic has been updated by dfsof (previous revision, new revision, compare).
I did a problem (ABC231G) before with similar tricks about random operation, so I recommend you to solve it.
Thank you!