【容斥、插值】P3270 [JLOI2016]成绩比较
题目简述
- 有 \(n+1\) 个人，进行 \(m\) 场考试，第 \(i\) 场考试的可能得分是 \([0,U_i]\) 之间的整数。
- 假设你是其中一人，你知道每场考试的排名 \(r_i\)（相同分数算后排名），并且恰有 \(k\) 个人每一场考试的分数都不大于你。
- 求方案数，对 \(10^9+7\) 取模。
- \(n,m\leq 100\)，\(U_i\leq10^9\)。
解题思路
很显然的计数分为三个部分：
- 确定被你碾压的 \(k\) 人。
- 确定每个人和你分数的大小关系。
- 确定每个人的分数。
对于第 \(1\) 部分，显然是 \(C_n^k\)。
对于第 \(2\) 部分，我们可以通过排名确定出每场比赛 \(i\) 有多少人分数 $\leq $ 你，多少人分数 \(>\) 你。那么由于已经确定出 \(k\) 个被碾压的人了，所以这 \(k\) 个人的分数 $\leq $ 你，我们的问题转换成在剩下的人当中去分配 \(R_i\) 使得每个人至少有一个 \(>\) 你的分数。很显然的可以使用容斥。
由于 \(k\) 个被碾压者已经确定，记剩下的人 \(N=n-k\)，假设有：
\[f_i=\prod_{j=1}^m C^{r_j-1}_{i} \]表示有至多 \(i\) 个人被你碾压，很显然的容斥为：
\[ans=\sum_{i=0}^N (-1)^{N-i}\times f_i\times C_{N}^i \]对于第三部分，每一场考试是独立的，我们可以写出式子：
\[\sum_{k=0}^{U_i} k^{n-r_i+1}\times (U_i-k)^{r_i-1} \]我们不难发现原式改写成 \(\sum_{k=0}^{x} k^{n-r_i+1}\times (U_i-k)^{r_i-1}\) 是关于 \(x\) 的 \(n+1\) 次多项式，所以我们对于 \(\leq n+2\) 的值暴力枚举，然后使用插值求出 \(x=U_i\) 的值即可。
暴力拉格朗日的复杂度 \(O(n^2\log V)\)，可以通过。我们也可以优化到 \(O(n\log n)\) 的拉格朗日。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
const int MAXN=105;
const int MOD=1e9+7;
int n,m,k;
int x[MAXN],r[MAXN];
ll fac[MAXN],inf[MAXN];
ll ksm(ll a,int b){ll res=1;while(b){if(b&1)res=res*a%MOD;a=a*a%MOD,b>>=1;}return res;}
ll inv(ll a){return ksm(a,MOD-2);}
void init(){
fac[0]=inf[0]=1;
for(int i=1;i<MAXN;i++)
fac[i]=fac[i-1]*i%MOD,
inf[i]=inv(fac[i]);
return;
}
ll C(int n,int m){if(n>m) return 0;return fac[m]*inf[n]%MOD*inf[m-n]%MOD;}
ll sgn(int x){return (x&1)?-1:1;}
ll Part_2(){
ll f[MAXN];
for(int i=0;i<=n;i++){
f[i]=1;
for(int j=1;j<=m;j++)
f[i]=f[i]*C(r[j]-1,i)%MOD;
}
ll res=0;
int d=n-k;
for(int i=0;i<=d;i++)
res=(res+sgn(d-i)*f[i]%MOD*C(i,d)%MOD+MOD)%MOD;
return res;
}
ll Func(ll x,int a,int b){
ll y[MAXN],res=0;
for(int i=1;i<=n+2;i++){
res+=ksm(i,a)*ksm(x-i+MOD,b)%MOD;
res%=MOD;
y[i]=res;
}
ll ans=0;
for(int i=1;i<=n+2;i++){
res=y[i];
for(int j=1;j<=n+2;j++)
if(i!=j)
res=res*(x-j+MOD)%MOD*inv(i-j+MOD)%MOD;
ans+=res;ans%=MOD;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
init();
cin>>n>>m>>k;n--;
for(int i=1;i<=m;i++)
cin>>x[i];
for(int i=1;i<=m;i++)
cin>>r[i];
ll ans=C(k,n)*Part_2()%MOD;
for(int i=1;i<=m;i++)
ans=ans*Func(x[i],n-r[i]+1,r[i]-1)%MOD;
cout<<ans;
return 0;
}