首先我们让恰有 \(k\) 位同学被碾压是比较困难的，我们套路地把它转换成钦定某 \(k\) 位同学被碾压。
考虑到分数的分配方案数只与多少个人比 B 大/多少个人小于等于 B 相关，而这部分是个定值，所以我们接下来只需要对每门课把所有人分成两个集合就可以了。
我们记钦定某 \(k\) 位同学被碾压的方案为 \(g_k\)，恰有 \(k\) 位为 \(f_k\)，第 \(i\) 门课的分数分配方案为 \(h_i\)。
\[g_k=\prod_{i=1}^mh_i\binom{n-k}{n-R_i-k}\\\begin{aligned}f_k&=\sum_{p=k}^{n-1}(-1)^{p-k}\binom{p}{k}\binom{n-1}{p}g_p\\&=\sum_{p=k}^{n-1}(-1)^{p-k}\binom{p}{k}\binom{n-1}{p}\prod_{i=1}^mh_i\binom{n-k-1}{n-R_i-k}\\&=(\prod_{i=1}^mh_i)\sum_{p=k}^{n-1}(-1)^{p-k}\binom{p}{k}\binom{n-1}{p}\prod_{i=1}^m\binom{n-k-1}{n-R_i-k}\end{aligned} \]这些都是平凡的。
问题变成怎么求 \(h_i\)。
我们知道 \(h_i=\sum_{v=1}^{U_i}(U_i-v)^{R_i-1}v^{n-R_i}\)，但你考虑到 \(U_i\le1e9\)。
猜一手这个东西是关于 \(U_i\) 的一个 \(n\) 次左右多项式。
事实上有
\[\begin{aligned}h_i&=\sum_{v=1}^{U_i}(U_i-v)^{R_i-1}v^{n-R_i}\\&=\sum_{v=1}^{U_i}\sum_{j=0}^{R_i-1}(-1)^{R_i-1-j}U_i^jv^{n-1-j}\binom{R_i-1}{j}\\&=\sum_{j=0}^{R_i-1}(-1)^{R_i-1-j}U_i^j\binom{R_i-1}{j}\sum_{v=1}^{U_i}v^{n-1-j}\end{aligned} \]这是关于 \(U_i\) 的 \(R_i-1\) 次多项式，虽然并没有什么用。我们考虑把后面那个东西求出来。这个就很典中点了，拉格朗日插值一下就解决了。在 \(n,m\) 同阶时复杂度为 \(O(n^3)\)。
正经部分就结束了，下面是 云浅知处 在寻找平方做法时推的神秘式子，虽然最后没找到，但我想再推一遍，权当头脑体操。
\[\begin{aligned}h_i&=\sum_{v=1}^{U_i}(U_i-v)^{R_i-1}v^{n-R_i}\\&=\sum_{v=1}^{U_i}\sum_j S(R_i-1,j)(U_i-v)^{\underline{j}}\sum_j S(n-R_i,j)v^{\underline{j}}\\&=\sum_{v=1}^{U_i}\sum_{j\le R_i-1,\\k\le n-R_i}S(R_i-1,j)S(n-R_i,k)(U_i-v)^{\underline{j}}v^{\underline{k}}\\&=\sum_{v=1}^{U_i}\sum_{j\le R_i-1,\\k\le n-R_i}S(R_i-1,j)S(n-R_i,k)\binom{U_i-v}{j}\binom{v}{k}j!k!\\&=\sum_{j\le R_i-1,\\k\le n-R_i}S(R_i-1,j)S(n-R_i,k)j!k!\sum_{v=1}^{U_i}\binom{U_i-v}{j}\binom{v}{k}\\&=\sum_{j\le R_i-1,\\k\le n-R_i}S(R_i-1,j)S(n-R_i,k)j!k!\binom{U_i+1}{j+k+1}\end{aligned} \]你发现这个东西还是平方的。
另一种推法是这样的：
\[\begin{aligned}\sum_{v=1}^{U_i}v^p&=\sum_{v=1}^{U_i}\sum_{j}S(p,j)v^{\underline{j}}\\&=\sum_{j=0}^pS(p,j)j!\sum_{v=1}^{U_i}\binom{v}{j}\\&=\sum_{j=0}^pS(p,j)j!\binom{U_i+1}{j+1}\end{aligned} \]你发现仍然爆标失败。
但感觉似乎可以爆标，不是很清楚，找个时间再推推。
标签：JLOI2016,le,prod,sum,underline,aligned,binom,成绩,比较 From： https://www.cnblogs.com/PYD1/p/17495580.html