原案:nok0

\(N=1\) のとき、答えは \(A_1^2\) です。
\(2 \leq N\) の場合を考えます。
最終的な \(x\) は、\(x=\sum_{i=1}^{N}{c_iA_i}\) という形で書くことができます。 ここで、\(c_i\) は \(1\) か \(-1\) です。
\(x^2=\sum_{i=1}^{N}{{A_i}^2}+2\sum_{1 \leq i \lt j \leq N}{c_ic_jA_iA_j}\) であり、\(\sum_{i=1}^{N}{{A_i}^2}\) は \(c_i\) に依存しません。
\(\sum_{1 \leq i \lt j \leq N}c_ic_j\) の期待値は \(N\) のみに依存するため、これを \(C_N\) と置きます。
\((c_1,c_2,\dots,c_N)\) 同士が多重集合として一致しているならばその出現確率は対称性より等しく、また \((c_1, c_2,\dots,c_N)\) は \((A_1, A_2,\dots,A_N)\) に依存しないため、
\(E[\sum_{1 \leq i \lt j \leq N}{c_ic_jA_iA_j}]=C_N\frac{\sum_{1 \leq i \lt j \leq N}{A_iA_j} }{\frac{N(N-1)}{2}}\)
が成り立ちます。
\(\sum_{1 \leq i \lt j \leq N}{A_iA_j}=\frac{(\sum_{i=1}^{N}{A_i})^2-\sum_{i=1}^{N}{A_i^2}}{2}\)
なので、あとは \(C_N\) が求まればよいです。
\(2 \leq N\) の場合を考えます。最初の操作で \(A_1\) と \(A_2\) を取り除いて \(A_1-A_2\) を追加するとして一般性を失いません。
このとき、これ以降どのように操作を行なっても \(c_1\) と \(c_2\) の符号は異なるため、
\(c_1c_2=-1\)
\(c_1c_i+c_2c_i=0 \; (3 \leq i \leq N)\)
が成り立ちます。
\(3 \leq i \lt j \leq N\) のとき、\(c_ic_j\) の期待値は 全体の要素数が \(N-1\) の場合の \(c_ic_j\) の期待値と同じなので、\(\frac{C_{N-1}}{\frac{(N-1)(N-2)}{2}}\) です。
よって、 \(C_N=-1+\frac{C_{N-1}}{\frac{(N-1)(N-2)}{2}}\frac{(N-2)(N-3)}{2}=-1+\frac{N-3}{N-1}C_{N-1}\)
です。また、\(C_1=0\) なので、 これにより \(C_2,C_3,\dots,C_N\) を順に求めていくことができます。
全体の計算量は \(O(N)\) です。