BZOJ 4559. [JLoi2016&LNoi2016]成绩比较

Description

G系共有n位同学,M门必修课。这N位同学的编号为0到N-1的整数,其中B神的编号为0号。这M门必修课编号为0到M-1的整数。一位同学在必修课上可以获得的分数是1到Ui中的一个整数。如果在每门课上A获得的成绩均小于等于B获得的成绩,则称A被B碾压。在B神的说法中,G系共有K位同学被他碾压(不包括他自己),而其他N-K-1位同学则没有被他碾压。D神查到了B神每门必修课的排名。这里的排名是指:如果B神某门课的排名为R,则表示有且仅有R-1位同学这门课的分数大于B神的分数,有且仅有N-R位同学这门课的分数小于等于B神(不包括他自己)。我们需要求出全系所有同学每门必修课得分的情况数,使其既能满足B神的说法,也能符合D神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。你不需要像D神那么厉害,你只需要计算出情况数模10^9+7的余数就可以了。

Input

第一行包含三个正整数N,M,K,分别表示G系的同学数量(包括B神),必修课的数量和被B神碾压的同学数量。第二行包含M个正整数,依次表示每门课的最高分Ui。第三行包含M个正整数,依次表示B神在每门课上的排名Ri。保证1≤Ri≤N。数据保证至少有1种情况使得B神说的话成立。N<=100,M<=100,Ui<=10^9

Output

仅一行一个正整数,表示满足条件的情况数模10^9+7的余数。

Sample Input

3 2 1
2 2
1 2

Sample Output

10

分析

首先设计 DP 状态 $f(i,j)$ 表示前 $i$ 个学科,不被碾压的人数为 $j$ 的方案数。

考虑从 $f(i,j)$ 转移到 $f(i,k)$,其中设 $t_1=k-j$ 表示新增加的不被碾压的人数,$t_2=R_i-1-t_1$ 表示原本就存在的不被碾压的人数,那么要从 $j$ 个人中选出 $t_2$ 个人,从 $n-j-1$ 个人中选出 $t_1$ 个人,方案数为 ${{j}\choose{t_2}}\times{n-j-1\choose{t_1}}$。

在每种方案下,当分数为 $x$ 时,$R_i-1$ 个人的分数要超过 $x$,$n-R_i$ 个人的分数不超过 $x$,即方案数为

$$\sum_{x=1}^{U_i} (U_i-x)^{R_i-1}\times x^{n-R_i}$$

所以,转移方程为

$$f(i,k)\leftarrow f(i,j)\times {{j}\choose{t_2}}\times{n-j-1\choose{t_1}}\times(\sum_{x=1}^{U_i} (U_i-x)^{R_i-1}\times x^{n-R_i})$$

由于 $U_i$ 太大,不能直接求,可以发现 $(U_i-x)^{R_i-1}\times x^{n-R_i}$ 的次数为 $n-1$,所以求和之后是一个最高次数为 $n$ 的多项式,可以用插值法求。由于这个和式的值之和 $i$ 有关,所以可以对于每个 $i$ 求出和式的值,只要做 $m$ 次插值即可。

所以就得到一个 $O(mn\log{U}+mn^2)$ 的做法。

发表评论