Operation Permutation

I checked the official Codeforces editorial and accepted-submission listings first. The intended route is exactly: normalize operations, use linearity of expectation, compute elementary symmetric sums with DP, then average over the relative position of one additive operation. Sources: official editorial, accepted submission listing.

Rewrite the operations into two kinds:

• +y gives an additive value $+y$;
• -y gives an additive value $-y$;
• xy gives a multiplicative factor $y$;
• /y gives a multiplicative factor $y^{-1}$ modulo $M$.

Let the multiplicative factors be

$a_1,a_2,\dots,a_m,$

and let the sum of all additive values be

$B=\sum b_i.$

The starting value $x$ always contributes

$x\prod_{i=1}^{m}a_i,$

because every multiplicative operation eventually hits it, regardless of order.

Now take one additive operation with value $b$. In a fixed permutation, once $b$ is added, only the multiplicative operations after it can change it. Its contribution is

$b\cdot\prod_{a_j\text{ after }b}a_j.$

By linearity of expectation, all additive operations can share the same expected multiplier. Their actual values only matter through $B$. Nice little probability coupon, no need to wrestle all $n!$ permutations like a maniac.

For one fixed additive operation, ignore every other additive operation. They do not affect the product. So we only care about the relative order of these $m+1$ objects:

$b,a_1,a_2,\dots,a_m.$

The rank of $b$ among them is uniform. Therefore the number $k$ of multiplicative operations after $b$ is uniform over $0,1,\dots,m$, with probability

$\frac{1}{m+1}.$

Conditioned on exactly $k$ multiplicative operations being after $b$, the subset is uniformly random among all $\binom{m}{k}$ subsets.

Define $e_k$ as the elementary symmetric sum of degree $k$:

$e_k=\sum_{|S|=k}\prod_{i\in S}a_i.$

Then the average product of a random size-$k$ subset is

$\frac{e_k}{\binom{m}{k}}.$

So the expected multiplier applied to any additive operation is

$S=\frac{1}{m+1}\sum_{k=0}^{m}\frac{e_k}{\binom{m}{k}}.$

The final answer is

$\boxed{x\prod_{i=1}^{m}a_i+B\cdot S}.$

To compute the $e_k$ values, use the generating polynomial

$\prod_{i=1}^{m}(1+a_i z).$

Its coefficient of $z^k$ is $e_k$. Standard descending DP:

$dp[0]=1,$

and for every factor $a$,

$dp[k]\leftarrow dp[k]+dp[k-1]a.$

After processing all factors, $dp[k]=e_k$.

For the binomial denominator,

$\frac{1}{\binom{m}{k}}=\frac{k!(m-k)!}{m!}.$

Precompute factorials and inverse factorials modulo $M$.

Edge cases:

• If $m=0$, then $S=1$, and the answer is just $x+B$.
• If there are no additive operations, then $B=0$, so only the multiplied starting value remains.
• /1 and x1 are fine as factors equal to $1$; keeping them in the DP is correct.

Complexity:

$O(m^2)$

per test case and $O(m)$ memory. Since $m\le n$ and the statement gives

$\sum n^2\le 3000^2,$

this fits easily.