成绩比较（容斥+组合数学+离散化（雾））

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神的分数，显然有：

其中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)次。故有：

所以而t最大为n。所以每次用O(n^2)的复杂度，可以计算出G(u,a,b)。

最后乘法原理把三步乘起来，从复杂度O(n^2m)。

代码：

#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