P9963前缀和 数学推导解法
\(\operatorname{E}{\sum\limits_{i=1}^n[l\le y_i\le r]}\\=\sum\limits_{i=1}^n\operatorname{E}[l\le y_i\le r]\\=\sum\limits_{i=1}^n\operatorname{E}[l\le \sum\limits_{j=1}^ix_j\le r]\\=\sum\limits_{i=1}^n\operatorname{P}[l\le \sum\limits_{j=1}^ix_j\le r]\)
考虑每个 \(x\) 的概率生成函数
则\(F(x)=px+(1-p)px^2+(1-p)^2px^3+\cdots=\dfrac{px}{1-(1-p)x}\)
所以\((F(x))^k\\=p^kx^k\dfrac{1}{(1-(1-p)x)^k}\\=p^kx^k\sum\limits_{i=0}^\infin{i+k-1\choose k-1}(1-p)^ix^i\\=\sum\limits_{i=k}^\infin{i-1\choose k-1}(1-p)^{i-k}p^kx^i\)
所以\(\operatorname{P}[l\le \sum\limits_{j=1}^ix_j\le r]=\sum_{j=l}^r(F(x))^i[x^j]=\sum_{j=l}^r{j-1\choose i-1}(1-p)^{j-i}p^i\)
\(\therefore原式=\sum\limits_{i=1}^n\sum\limits_{j=l}^r{j-1\choose i-1}(1-p)^{j-i}p^i\\=\sum\limits_{j=l}^rp\sum\limits_{i=1}^n{j-1\choose i-1}(1-p)^{j-i}p^{i-1}\\=\sum\limits_{j=l}^rp=p(r-l+1)\)
标签：P9963,ix,le,前缀,limits,sum,choose,operatorname,解法 From： https://www.cnblogs.com/lupengheyyds/p/18303124