成绩比较

题意:除了小明外有 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)$的了。

分类: 文章

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注