成绩比较

题意：除了小明外有 n 个人，m 门课程，每门课程的得分是 $[1,U_i]$内的整数。定义 A 碾压 B 为 A 门门课程得分不比 B 低。现在给定小明碾压了多少人，以及他每门课的排名 (分数比他高的人数)，求有多少种不同的得分分布情况 (两种情况中存在任何一个人任何一门的得分不同，则两种情况不同)。其中 $n,m\leq 100,U_i\leq 10^9$

分析：根据题意，我们可以列出这样的式子：

令 $f(x)$表示固定小明碾压了 $x$名同学，其它同学的情况未定的情况总数。

$f(x)$的求法较为复杂。对于每一门课程的情况我们分开考虑，最终将每一门课的情况总数相乘即是 $f(x)$。

对于第 $i$门课，设有 $k_i$人排名不比他靠前，且他的得分为 $V_i$。其中 $V_i$是未定的变量，$k_i$是已知量。则这一门课所有人的得分情况为：
$$
C_n^x\sum_{V_i=1}^{U_i}C_{n-x}^{k_i-x}V_i^{k_i}(U_i-V_i)^{n-k_i}
$$
上面的式子的意思是，先选出 $x$人作为强制被碾压的人。然后枚举这门课小明的得分 $V_i$，再从剩下的人中选出这门课不比小明高的人，因此总共有 $k_i$人这门课得分不比小明高，即 $V_i^{k_i}$。接着，剩下的所有人都有 $(U_i-V_i)$种得分方法。

将这个式子的最后面一项二项式展开，并化简：
$$
C_n^x\sum_{j=0}^{n-k_i}C_{n-k_i}^j(-1)^{n-k_i-j}C_{n-x}^{k_i-x}U_i^{j}
\sum_{V_i=1}^{U_i}V_i^{n-j}
$$
因此，最后的 $f(x)$可以表示为：
$$
f(x)=C_n^x\prod_{i=1}^{m}\Big(\sum_{j=0}^{n-k_i}C_{n-k_i}^j(-1)^{n-k_i-j}C_{n-x}^{k_i-x}U_i^{j}
\sum_{V_i=1}^{U_i}V_i^{n-j}\Big)
$$
计算 $f(1\cdots n)$的复杂度是 $O(n^2mU)$的，非常不好。

但是，如果我们可以 $O(n^2m)$内预处理 $\sum_{i=1}^{x}i^{t}$，我们就可以 $O(1)$获得最后一项的值，从而使总复杂度降低到 $O(n^2m)$。幸运的是，这是可以做到的。在最后会说明如何预处理。

由于任何一个碾压了 $y$人的情况都会被 $f(x)$重复计算 $C_y^x$次，因此设 $g(x)$表示小明恰好碾压了 $x$人的方案数，则：
$$
f(x)=\sum_{y=x}^nC_y^xg(y)
$$
根据二项式反演：
$$
g(x)=\sum_{y=x}^{n}(-1)^{y-x}C_y^xf(y)
$$
到目前为止，我们的复杂度集中在 $f(x)$的求解和预处理上，总复杂度为 $O(n^2m) $

下面是预处理的方法。我们需要预处理自然数幂级数和，$1$到 $n$的而 $k$次幂和是一个关于 $n$的 $k+1$次多项式。我们可以先预处理出对于 $k\in[1,n]$的每个多项式的每个系数。

令：
$$
\sum_{x=1}^nx^t=\sum_{i=1}^{t+1}f_in^i
$$
则有：
$$
\sum_{x=1}^{n+1}x^t=\sum_{i=1}^{t+1}f_i(n+1)^i
$$
联立上下两个方程，我们不难发现：
$$
\sum_{i=a}^{t+1}C_i^af_i=f_a+C_t^a
$$
由此可以解出 $f_a$：
$$
f_a=\frac{C_t^{a-1}-\sum_{i=a+1}^{t+1}C_i^{x-1}f_t^i}{a}
$$
这样，预处理的复杂度就是 $O(n^2m)$的了。