ABC450G Random Subtraction

比较简单的概率论题

设S=∑Ai,Q=∑Ai2S=\sum A_i,Q=\sum A_i^2S=∑Ai​,Q=∑Ai2​

最终结果可以表示为：
x=∑εiAi,εi∈{±1} x=\sum \varepsilon_i A_i,\quad \varepsilon_i\in\{\pm1\}x=∑εi​Ai​,εi​∈{±1}

展开平方并取期望：
E[x2]=Q+cN(S2−Q) E[x^2]=Q+c_N(S^2-Q)E[x2]=Q+cN​(S2−Q)

其中
cN=E[εiεj] (i≠j) c_N=E[\varepsilon_i\varepsilon_j]\ (i\ne j)cN​=E[εi​εj​](i=j)

通过分析第一次操作，可得递推：
cN=−2N(N−1)+(N−2)(N−3)N(N−1)cN−1 c_N=-\frac{2}{N(N-1)}+\frac{(N-2)(N-3)}{N(N-1)}c_{N-1}cN​=−N(N−1)2​+N(N−1)(N−2)(N−3)​cN−1​

解得：
cN={−1N=2−23(N−1)N≥3 c_N= \begin{cases} -1 & N=2 \\ -\dfrac{2}{3(N-1)} & N\ge 3 \end{cases}cN​=⎩⎨⎧​−1−3(N−1)2​​N=2N≥3​

代回得到：
E[x2]={QN=12Q−S2N=2Q−23(N−1)(S2−Q)N≥3 E[x^2]= \begin{cases} Q & N=1 \\[6pt] 2Q-S^2 & N=2 \\[6pt] Q-\dfrac{2}{3(N-1)}(S^2-Q) & N\ge 3 \end{cases}E[x2]=⎩⎨⎧​Q2Q−S2Q−3(N−1)2​(S2−Q)​N=1N=2N≥3​

进一步化简N≥3N\ge3N≥3：
E[x2]=(3N−1)Q−2S23(N−1) E[x^2]=\frac{(3N-1)Q-2S^2}{3(N-1)}E[x2]=3(N−1)(3N−1)Q−2S2​

复杂度分析：
时间复杂度：O(N)O(N)O(N)
空间复杂度：O(1)O(1)O(1)

不留代码