题解 P3270【[JLOI2016]成绩比较】
cyffff
·
·
题解
\text{Link}
本文参考神仙 \color{black}\texttt{R}\color{red}\texttt{edpojoe} 的题解。
题意
有 n 名学生，m 名课程，一位同学在第 i 门课程中可被评为 [1,u_i] 范围内的分数。其中有一位同学，在第 i 门课程中排名 r_i，其余 n-1 名同学中有 k 名每门的分数都不高于这位同学。
求方案数，对 10^9+7 取模。
1\le n,m\le100,1\le u_i\le10^9
思路
首先我们将问题用乘法原理划分：
- 从 n-1 个同学中选出 k 个同学被 B 神碾压的方案数；
- 剩余 n-k-1 个同学在课程中与 B 神成绩的大小关系的方案数；
- 每科中每名同学具体成绩方案数。
第一部分
答案显然为 \displaystyle\binom{n-1}{k}。
第二部分
我们仍可以使用乘法原理将问题分解为单科的子问题，第 i 科中，比 B 神高的只有 r_i-1 名，则方案数为 \displaystyle\binom{n-k-1}{r_i-1}。
但是我们求出的只是有不超过 k 人被碾压，因为我们需要保证 n-k-1 个人都被选中了至少一次，我们设
f_i=\prod_{j=1}^m\binom{n-i-1}{r_j-1}
即不超过 k 人被碾压时的方案数，容斥后得到答案为
\sum_{i=1}^{n-k-1}(-1)^{i+1}f_{n-k-i}\binom{n-k-1}{i-1}
第三部分
拆分为单科后设 G(u,a,b) 表示分数上限为 u，有 a 人比 B 神高，b 人不比 B 神高的方案数，显然：
G_{u,a,b}=\sum_{i=0}^{u-1}i^a(u-i)^b
直接暴力求则会得到一个 O(n^2+nm+mv\log n) 的暴力（v=\max\{u_i\}），无法通过。
接下来可以通过二项式定理展开+拉格朗日插值求自然数 k 次幂和的方法解决，不过我们这里使用神仙 \color{black}\texttt{R}\color{red}\texttt{edpojoe} 的做法：枚举 n 人有 i 种得分的方案数，设为 d_i，算出每类的方案数之和即可。
可以得出，n 人有不超过 i 种得分的方案数为
\binom{u}{i}G_{i,a,b}
为了得出 d_i，我们考虑容斥，易得
d_i=\binom{u}{i}\left(G_{i,a,b}-\sum_{j=1}^{i-1}d_j\binom{i}{j}\right)
设 \displaystyle G'_{u,a,b}=\sum_{i=1}^nd_i=\sum_{i=1}^n\binom{u}{i}\left(G_{i,a,b}-\sum_{j=1}^{i-1}d_j\binom{i}{j}\right)，这部分的答案即为
\prod_{i=1}^nG'_{u_i,r_i-1,n-r_i}
则最终答案为三部分乘在一起。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
}
const int N=100+10,mod=1e9+7;
int n,m,k,u[N],r[N];
int C[N][N],pw[N][N],inv[N];
inline int qpow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
inline void Prefix(int n){
inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=0;i<=n;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
for(int i=0;i<=n;i++){
pw[i][0]=1;
for(int j=1;j<=n;j++)
pw[i][j]=1ll*pw[i][j-1]*i%mod;
}
}
inline int Type1(){
return C[n-1][k];
}
inline int F(int n){
int ans=1;
for(int i=1;i<=m;i++)
ans=1ll*ans*C[n][r[i]-1]%mod;
return ans;
}
inline int Type2(){
int t=n-k-1;
int ans=0;
for(int i=0;i<t;i++){
int tmp=1ll*F(t-i)*C[t][i]%mod;
ans=(ans+(i&1?mod-tmp:tmp))%mod;
}
return ans;
}
int D[N];
inline int G(int n,int a,int b){
int ans=0;
for(int i=0;i<n;i++)
ans=(ans+1ll*pw[i][a]*pw[n-i][b])%mod;
return ans;
}
inline int Gpi(int u,int a,int b){
int ans=0,tmp=1;
for(int i=1;i<=n;i++){
D[i]=G(i,a,b);
for(int j=1;j<i;j++)
D[i]=(D[i]+mod-1ll*D[j]*C[i][j]%mod)%mod;
tmp=1ll*tmp*(u-i+1)%mod*inv[i]%mod;
ans=(ans+1ll*tmp*D[i])%mod;
}
return ans;
}
inline int Type3(){
int ans=1;
for(int i=1;i<=m;i++)
ans=1ll*ans*Gpi(u[i],r[i]-1,n-r[i])%mod;
return ans;
}
int main(){
Prefix(N-10);
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++)
u[i]=read();
for(int i=1;i<=m;i++)
r[i]=read();
write(1ll*Type1()*Type2()%mod*Type3()%mod);
flush();
}
```
再见 qwq~