bzoj 4559 成绩比较

Posted on | Views:

组合计数 + 容斥原理 + 拉格朗日插值法.

  • 首先我们确定哪些人被碾压,再确定没有被碾压的人各科分数分别是高于 $B$ 神还是小于等于 $B$ 神.然后就可以将每科分开算所有人各自具体分数的方案数,最后乘在一起.
  • 选出被碾压的人有 $n-1\choose k$ 种方案.
  • 对于课程 $i$ ,有 $r_i-1$ 个人的分比 $B$ 神高,这 $r_i-1$ 个人显然只能在未被碾压的 $n-k-1$ 个人中产生.如果任意分配,可能会出现新的人被碾压.所以用容斥原理计算这部分的贡献,没有人被碾压方案数 $=$ 总方案数 $-$ 保证 $1$ 个人被碾压方案数 $+$ 保证 $2$ 个人被碾压方案数 $\dots$ 记这个答案为 $s$ .
  • 再来计算第 $i$ 科排名恰好为 $r_i$ 的方案数 $p_i$ .枚举这一科 $B$ 神考了 $x$ 分.(有 $r_i=1$ 的情况,所以定义 $0^0=1$ ).

$$
\begin{aligned}
p_i=\sum_{x=1}^{u_i} x^{n-r_i}\cdot (u_i-x)^{r_i-1}
\end{aligned}
$$

  • 若暴力算 $p_i$ 可以拿到 $70$ 分.注意到 $p_i$ 是个关于 $u_i$ 的 $n$ 次多项式,而我们只需要求它在某一个位置的值.
  • 拉格朗日插值即可,答案为 ${n-1\choose k}\cdot s \cdot \prod p_i$ .
  • 时间复杂度 $O(n^3\cdot \log n)$ .
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=128;
const int P=1e9+7;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
int inv(int x)
{
	return fpow(x,P-2);
}
int n,m,k,C[MAXN][MAXN];
int u[MAXN],r[MAXN];
void init()
{
	C[0][0]=1;
	for(int i=1;i<=n;++i)
		C[i][0]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j)
			C[i][j]=add(C[i-1][j],C[i-1][j-1]);
}
int Assign_Rank()
{
	int res=1;
	for(int i=1;i<=m;++i)
		res=mul(res,C[n-k-1][r[i]-1]);
	bool flag=true;
	for(int i=1;i<=n-k-1 && flag;++i)
	{
		int tmp=C[n-k-1][i];
		for(int j=1;j<=m;++j)
			if(n-k-1-i>=r[j]-1)
				tmp=mul(tmp,C[n-k-1-i][r[j]-1]);
			else
			{
				tmp=0;
				flag=false;
				break;
			}
		if(i&1)
			res=add(res,P-tmp);
		else
			res=add(res,tmp);
	}
	return res;
}
int Calc_p(int i,int U)
{
	int res=0;
	for(int x=1;x<=U;++x)
		res=add(res,mul(fpow(x,n-r[i]),fpow(U-x,r[i]-1)));
	return res;
}
int x[MAXN],y[MAXN];
int Lagrange(int N,int pos)
{
	int res=0;
	for(int i=1;i<=N;++i)
	{
		int tmp=y[i];
		for(int j=1;j<=N;++j)
			if(i!=j)	
			{
				tmp=mul(tmp,add(pos,P-x[j]));
				tmp=mul(tmp,inv(add(x[i],P-x[j])));
			}	
		res=add(res,tmp);
	}
	return res;
}
int Assign_Score(int i)
{
	for(int U=2;U<=n+2;++U)
		x[U-1]=U,y[U-1]=Calc_p(i,U);
	return Lagrange(n+1,u[i]);
}
int main()
{
	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();
	init();
	int ans=C[n-1][k];
	ans=mul(ans,Assign_Rank());
	for(int i=1;i<=m;++i)
		ans=mul(ans,Assign_Score(i));
	cout<<ans<<endl;
	return 0;
}