出题人：w33z

Description

$x$ 和 $y$ 为给定区间里的整数，求 $(x+y)^2$ 可能取值，期望取值。

$|x|,|y|\le10^{18}$

Solution

考虑极限：$x+y$ 最小为 $x$ 最小加 $y$ 最小，$x+y$ 最大为 $x$ 最大加 $y$ 最大。取该区间绝对值即可回答第一个问题。

对于第二个问题，考虑期望线性性。

$$E((x+y)^2)=E(x^2)+2E(xy)+E(y^2)$$

$x$ 和 $y$ 独立，于是可以继续拆：

$$E((x+y)^2)=E(x^2)+2E(x)E(y)+E(y^2)$$

考虑如何给定一个区间 $[l,r]$ 求 $E(x)$ 以及 $E(x^2)$。

如果你取和然后除，你会暴毙，因为 $r-l+1$ 可能是 $998244353$ 倍数。有几个方法：

1. 维护答案的 $998244353$ 次幂
2. 直接除走

我选了第二个方法。我们有：

$$E(x)=\frac{1}{r-l+1}\sum_{x=l}^{r}x=\frac{l+r}{2}$$

对于 $E(x^2)$，可以这样求：

$$\sum_{x=l}^rx^2=\sum_{x=0}^rx^2-\sum_{x=0}^{l-1}x^2=\frac{r(r+1)(2r+1)-l(l-1)(2l-1)}{6} $$

考虑暴力从分子凑出来一个 $r-l+1$ 系数。

$$\frac{r(r+1)(2r+1)-l(l-1)(2l-1)}{6}=\frac{(r-l+1)(2l^2+2lr-l+2r^2+r)}{6} $$

直接套即可，时间复杂度 $\mathcal O(T)$。