成绩比较（容斥+组合数学+离散化（雾））
Redpojoe
2018-12-03 15:16:01
（数学公式的锅暂时已修复）
玄学组合数学题。对于我等蒟蒻，高级的方法是不存在的，~~dp是不存在的~~，所以我们只有用强硬的组合数学功底解决。
前置知识：没有神仙的各种数学知识，只有基本的组合数学。
#### 大体思路框架
我们可以清晰地把整个题目的框架分成三份：
1. 计算在n-1个人中选出k个，被B神碾压的方案数。
2. 对于剩下的n-1-k个人，计算有多少种方案来合法分配每一个人、每一门科目的得分状况。这里，得分状况定义为是比B神高，还是比B神低或相等。
3. 已知每一门科目的得分状况，计算对于给定的满分，有多少种分配分数的方案。
首先，第一个部分的答案很显然是$C(n-1,k)$。接下来我们要讨论第2、3部分。
#### 第二部分计数
在第二部分中，很显然我们可以对于每一门科目进行讨论。对于每一门科目，分数比B神高的人有$R[i]-1$个（不能重复，不计顺序），并且只可能在那$n-k-1$个人中诞生。所以对于这门课，方案为$C(R[i]-1,n-k-1)$个。用乘法原理可以得到。
但是有一个问题：由于**恰好**有k个人被碾压，每个人都必须被选中至少一次。对于这种问题，一个很常用的方法就是**容斥原理**。
定义函数$F(p)$表示至多有p个人被碾压，这一步总共的方案数。上述的乘法原理+组合数的计算过程就是$F(n-k-1)$的计算过程，只用把参数改成p即可解决。然后枚举p进行容斥，即可得到第二部分的计算结果。复杂度$O(nm)$。
#### 第三部分计数
在第三部分中，显然，可以把每一门科目分开来处理。这样，需要我们实现一个函数$G(u,a,b)$，表示有u种可选分数，其中a个人比B神高，b个人低于或等于B神的方案数。这里假定根据第一、第二步，这些人的得分状况已经被选定好，所以不用考虑顺序问题。
枚举B神的分数，显然有：
$$G(u,a,b)=\sum_{i=0}^{u-1}i^a\cdot(u-i)^b$$
其中i表示有多少种分数比B神的分数高。
然而，由于u的范围很大，这样显然T飞。所以我们需要作出一些措施。想想，你平常遇到这种数据范围很大的题都是怎么做的？很容易想到离散化。当然这里不用直接离散化，而要借助离散化的思想。
我们可以**枚举这n个人有t种不同的得分**，然后，t的范围就很小了，这个时候直接调用暴力函数也没事。同时，我们知道有$C(u,t)$种方案从u个分数中选出t个。所以对于t，贡献为$D(t)=G(t,a,b)\cdot C(u,t)$。最后用加法原理加起来即可。
但是那个式子其实是错的，因为又有一个问题：在暴力函数中，有一种情况就是：给你t种可能的分数，但是并不全都取到t种，会导致重复。所以，我们可以再用一次容斥，把重复的情况剔除。对于**恰**有r种分数的情况，被重复计算了$C(t,r)$次。故有：
$D(t)=(G(t,a,b)-\sum_{i=1}^{t-1}D(i)\cdot C(t,i))\cdot C(u,t)$
所以而t最大为n。所以每次用$O(n^2)$的复杂度，可以计算出$G(u,a,b)$。
最后乘法原理把三步乘起来，从复杂度$O(n^2m)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int P=1e9+7;
int n,m,k;
int U[105],R[105];
long long Pow(long long a,long long p) {
long long ret=1;
for(; p; p>>=1,a=a*a%P)if(p&1)ret=ret*a%P;
return ret;
}
//各种预处理
long long C[105][105],Pw[105][105];//在暴力G函数中用的乘方也可以预处理
long long Fact[105],Inv[105];
void Init() {
for(int i=1; i<=100; i++)
for(int j=0; j<=i; j++)
if(j==0||j==i)C[i][j]=1;
else C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
Fact[0]=1;
for(int i=1; i<=100; i++)Fact[i]=Fact[i-1]*i%P,Inv[i]=Pow(i,P-2);
for(int i=0; i<=100; i++) {
Pw[i][0]=1;
for(int j=1; j<=100; j++)Pw[i][j]=Pw[i][j-1]*i%P;
}
}
long long F(int p) {//F函数
long long Ans=1;
for(int i=1; i<=m; i++)Ans=Ans*C[p][R[i]-1]%P;//暴力即可
return Ans;
}
long long Calc() {
int tot=n-k-1;
long long Ans=0;
for(int i=0; i<tot; i++) {
long long th=F(tot-i)*C[tot][i];//不要忘记乘组合数！
if(i&1)Ans-=th;//i表示tot个人中有多少个人没有出现，故偶加奇减
else Ans+=th;
Ans%=P;
}
Ans=(Ans+P)%P;
return Ans;
}
long long g(int u,int a,int b) {//暴力G函数
long long ret=0;
for(int i=0; i<u; i++)ret=(ret+Pw[i][a]*Pw[u-i][b])%P;
return ret;
}
long long D[105];
long long G(int u,int a,int b) {//离散化优化G函数
long long Ans=0;
long long Combination=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]-D[j]*C[i][j])%P;//减去重复的
Combination=Combination*(u-i+1)%P*Inv[i]%P;//组合数可以递推
Ans=(Ans+D[i]*Combination)%P;//加法原理
}
return (Ans+P)%P;
}
void Solve() {
Init();
long long Ans=C[n-1][k]*Calc()%P;
for(int i=1; i<=m; i++)Ans=Ans*G(U[i],R[i]-1,n-R[i])%P;//乘法原理
printf("%lld\n",Ans);
}
int main() {
scanf("%d%d%d",&n,&m,&k);
for(int i=1; i<=m; i++)scanf("%d",&U[i]);
for(int i=1; i<=m; i++)scanf("%d",&R[i]);
Solve();
return 0;
}
```
By ^3