自动搬运

查看原文

来自洛谷，原作者为

	Redpojoe Viat eupnes,viat Eupnes.

搬运于2025-08-24 21:47:11，当前版本为作者最后更新于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)$次。故有：

$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)$。

代码：

#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