1 条题解

  • 1
    @ 2021-8-7 18:18:34

    出题人:w33z

    Description

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

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

    Solution

    考虑极限:x+yx+y 最小为 xx 最小加 yy 最小,x+yx+y 最大为 xx 最大加 yy 最大。取该区间绝对值即可回答第一个问题。

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

    E((x+y)2)=E(x2)+2E(xy)+E(y2)E((x+y)^2)=E(x^2)+2E(xy)+E(y^2)

    xxyy 独立,于是可以继续拆:

    E((x+y)2)=E(x2)+2E(x)E(y)+E(y2)E((x+y)^2)=E(x^2)+2E(x)E(y)+E(y^2)

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

    如果你取和然后除,你会暴毙,因为 rl+1r-l+1 可能是 998244353998244353 倍数。有几个方法:

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

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

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

    对于 E(x2)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} $$

    考虑暴力从分子凑出来一个 rl+1r-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} $$

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

    • 1

    信息

    ID
    178
    时间
    2000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    17
    已通过
    1
    上传者