题意
给定 \(n\) 个取值为实数的变量 \(x_1,x_2,\dots,x_n\)，其中 \(x_i\) 在 \([l_i,r_i)\) 之间均匀随机。求 \(\lfloor x_1+x_2+\dots+x_n\rfloor^k\) 的期望取值。对 \(998244353\) 取模。
\(1\le n\le10^3,1\le k\le20,0\le l_i<r_i<998244353\)。
题解
实数十分麻烦。这题如果不进行转化，暴力都写不出来。
将每个 \(x_i\) 拆成 \(a_i+r_i\)，其中 \(a_i\in\Z,r_i\in[0,1)\)。则答案为
\[E(\sum a_i+\lfloor\sum r_i\rfloor)^k\\ =E(\sum_{j=0}^k\binom{k}{j}(\sum a_i)^j\lfloor\sum r_i\rfloor^k)\\ =\sum_{j=0}^k\binom{k}{j}E(\sum a_i)^jE\lfloor\sum r_i\rfloor^{k-j} \]于是可以隔离考虑。先看前面部分。期望已经可以拿掉了，变成求所有 \((\sum a_i)^j\) 之和。
设 \(f_{i,k}\) 表示当前处理到 \(a_i\)，幂次为 \(k\) 的答案。设当前选 \(v\)，二项式展开易得
\[\begin{aligned} f_{i,k}&=\sum_{v=l_i}^{r_i-1}\sum_{j=0}^k\binom{k}{j}f_{i-1,j}v^{k-j}\\ &=\sum_{j=0}^k\binom{k}{j}f_{i-1,j}\sum_{v=l_i}^{r_i-1}v^{k-j} \end{aligned} \]后面那个是拉格朗日插值的经典问题。于是预处理后可以 \(O(nk^2)\) 解决。
再看后面部分。所有 \(r\) 均为 \([0,1)\) 的均匀随机变量，这是很好的性质。设 \(s_i=\sum\limits_{j=1}^ir_j\)，\(t_i=s_i-\lfloor s_i\rfloor\)。因为随机，所以 \(t_i\) 均不相等。将其看成一个排列，则我们发现所有 \(n!\) 种排列方式的概率相等，而且 \(\lfloor\sum r_i\rfloor=\sum\limits_{i=1}^{n-1}[t_i>t_{i+1}]\)。于是脱离了小数。同样通过求所有 \(\lfloor\sum r_i\rfloor^k\) 之和消去期望。
排列相关 \(\text{dp}\) 的重要思考方向之一是插数。从小到大插数，设 \(g_{i,j}\) 表示当前处理到 \(i\)，有 \(j\) 个位置满足上式的方案数。易得 \(g_{i,j}=g_{i-1,j-1}+g_{i-1,j}+j\cdot g_{i-1,j}+(i-j-1)g_{i-1,j-1}\)，分别表示插在开头，结尾，满足上式的两数之间，不满足之间。复杂度 \(O(n^2)\)。于是此题得解。
此题处理小数的方式十分精妙，值得学习。
标签：lfloor,le,记录,sum,rfloor,5.12,校赛,binom From： https://www.cnblogs.com/fish07/p/17396164.html