YZOJ P3098 [JLOI2016]成绩比较
时间限制：100MS 内存限制：131072KB
难度：\(6.0\)
-
题目描述
G系共有 \(n\) 位同学，\(m\) 门必修课。这 \(n\) 位同学的编号为 \(0\) 到 \(n-1\) 的整数，其中B神的编号为 \(0\) 号。
这 \(m\) 门必修课编号为 \(0\) 到 \(m-1\) 的整数。一位同学在必修课上可以获得的分数是 \(1\) 到 \(U_i\) 中的一个整数。如果在每门课上 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\) 的余数就可以了。
-
输入格式
第一行包含三个正整数 \(n, m, k\)，分别表示G系的同学数量（包括B神），必修课的数量和被B神碾压的同学数量。
第二行包含 \(m\) 个正整数，依次表示每门课的最高分 \(U_i\) 。
第三行包含 \(m\) 个正整数，依次表示B神在每门课上的排名 \(R_i\) 。保证 \(1 \leq R_i \leq n\)。
数据保证至少有 \(1\) 种情况使得B神说的话成立。\(n \leq 100, m \leq 100, U_i \leq 10^9\) 。
-
输出格式
输出仅包括一行一个整数，表示成绩情况数对 \(10^9+7\) 取模的结果。
-
样例输入
|
1 2 3 |
3 2 1 2 2 2 1 |
-
样例输出
|
1 |
10 |
-
数据规模与约定
对于 \(30\%\) 的数据，\(n, m \leq 20\)，\(U_i \leq 100\)；
对于 \(100\%\) 的数据，\(n,m \leq 100\)，\(U_i \leq 10^9\)，\(1 \leq R_i \leq n\)，\(0 \leq k < n\) 。
Source: BZOJ 4559
挺神仙的一道题，当场就爆零了
考虑 DP ，设 \(f_{i, j}\) 表示前 \(i\) 个科目中恰好碾压了 \(j\) 个人的方案数。
那么有
\(f_{i, j} = \sum\limits_{k=j}^n f_{i-1, j} \times C_k^j \times C_{n-k-1}^{n-R_i-j} \times P_i\)
首先枚举 \(k\) 表示从上一门课 \(j\) 个人中继续选出 \(j\) 个人被碾压，所以有一个 \(C_k^j\) ；然后再选一些人的排名继续不超过自己，即 \(C_{n-k-1}^{n-R_i-j}\) ；最后 \(P_i\) 表示将 \(1\) ~ \(U_i\) 这些分数分给 \(n\) 个人的合法方案数。
可以发现 \(P_i = \sum\limits_{j=1}^{U_i} {j^{n-R_i} \times (U_i-j)^{R_i-1}}\)
即枚举自己的分数 \(j\) ，然后有 \(n-R_i\) 个人分数不少于自己，\(R_i-1\) 个人分数大于自己，次方后乘起来即可。
这样是 \(O\left(m\sum{U_i}+n^2m\right)\) ，可以拿到 \(40pts\) 。
考虑优化这个过程，因为 \(U_i\) 达到了 \(10^9\) 级别，所以用xxx维护是不可能的。
\(\begin{array}{l}\sum\limits_{j = 1}^{{U_i}} {{j^{n – {R_i}}}} {({U_i} – j)^{{R_i} – 1}} = \sum\limits_{j = 1}^{{U_i}} {{j^{n – {R_i}}}} \sum\limits_{d = 0}^{{R_i} – 1} {C_{{R_i} – 1}^d} {j^d}U_i^{{R_i} – 1 – d}\\= \sum\limits_{d = 0}^{{R_i} – 1} {C_{{R_i} – 1}^d} U_i^{{R_i} – 1 – d}\sum\limits_{j = 1}^{{U_i}} {{j^{n – {R_i} + d}}}\end{array}\)
可以发现前面的是常数，后面的是自然数幂和。可以知道自然数幂和（上方的式子）是一个次数为 \(n\) 的多项式。
所以 \(\sum\limits_{j = 1}^{{U_i}} {{j^{n – {R_i}}}} {({U_i} – j)^{{R_i} – 1}}\) 是一个最高次数不超过 \(n\) 的多项式，然后就可以直接拉格朗日插值插一下就好了。
时间复杂度 \(O\left(n^2m\right)\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define MOD 1000000007 inline int _pow(register int base,register int b) { register int ans=1; while(b) { if(b&1) ans=(long long)ans*base%MOD; base=(long long)base*base%MOD; b>>=1; } return ans; } int U[105],R[105],P[105]; int comb[105][105],poly[105],inv[105]; int f[105][105]; int main() { int N,M,K;scanf("%d%d%d",&N,&M,&K); for(register int i=1;i<=M;i++) scanf("%d",&U[i]); for(register int i=1;i<=M;i++) scanf("%d",&R[i]); comb[0][0]=1; for(register int i=1;i<=N;i++) { comb[0][i]=1; for(register int j=1;j<=i;j++) comb[j][i]=(comb[j][i-1]+comb[j-1][i-1])%MOD; } for(register int i=1;i<=N;i++) inv[i]=_pow(i,MOD-2); for(register int i=1;i<=M;i++) { register int k=N; for(register int j=1;j<=k+1;j++) poly[j]=(poly[j-1]+(long long)_pow(j,N-R[i])*_pow(U[i]-j,R[i]-1)%MOD)%MOD; if(U[i] <= k+1) { P[i]=poly[U[i]]; continue; } register int ans=0; for(register int j=1;j<=k+1;j++) { register int neg=0,tans=poly[j]; for(register int x=1;x<=k+1;x++) if(x != j) { tans=(long long)tans*(U[i]-x)%MOD; register int t=j-x; if(t<0) t=-t,neg^=1; tans=(long long)tans*inv[t]%MOD; } ans=(ans+(neg?-1:1)*tans)%MOD,(ans+=MOD)%=MOD; } P[i]=ans; } f[0][N-1]=1; for(register int i=1;i<=M;i++) for(register int j=0;j<=N-R[i];j++) for(register int k=j;k<=N-1;k++) (f[i][j]+=(long long)f[i-1][k]*comb[j][k]%MOD*comb[N-R[i]-j][N-k-1]%MOD*P[i]%MOD)%=MOD; printf("%d\n",f[M][K]); return 0; } |