【BZOJ4559】成绩比较(动态规划,拉格朗日插值)

题面

BZOJ

洛谷

题解

显然可以每门课顺次考虑,

设\(f[i][j]\)表示前\(i\)门课程\(zsy\)恰好碾压了\(j\)个\(yyb\)的方案数。

那么,思考转移,显然是原来碾压了\(k\)个人,但是在考虑到这一门课程的时候有些人没被碾压了,

所以转移就是\(f[i][j]=f[i-1][k]*C_k^j*C_{n-k-1}^{n-rank[i]-j}*P[i]\)

大致的含义就是,原先\(zsy\)碾压了\(k\)个人,但是现在\(zsy\)只碾压了\(j\)个蒟蒻\(yyb\),

因为有\(k-j\)个神犇\(ppl\)在这门课程上的得分吊打了\(zsy\)。

先找出来哪些是\(j\)个蒟蒻\(yyb\)中的一员,并且被\(zsy\)被碾压了,方案数是\(C_k^j\),

由于之前有\(k\)个人钦定被\(zsy\)吊打,所以还剩下\(n-k-1\)个人,

然而有\(j\)个蒟蒻\(yyb\)仍然钦定被\(zsy\)吊打,所以剩下的人里面要找些人把被\(zsy\)吊打的人数给填满,要不然\(zsy\)会不开森。

还差多少个被吊打的人呢?一共是\(n-rank[i]\)个被吊打名额,有\(j\)个蒟蒻\(yyb\)被钦定了,所以还剩下\(n-rand[i]-j\)个名额。

所以就得到了上面的转移。。。。吗?

后面那个\(P\)是啥玩意?

你现在不是已经钦定好了这些人的相对排名了吗,然而我们并不知道分数是多少。

所以\(P[i]\)表示的是给所有人钦定\([1,U[i]]\)之间的分数的方案数。

\(U\)这么大,明显不让人活了,所以假装拉格朗日插值一下是对的。

\(P\)是个啥玩意呢?

\(P=\sum_{i=1}^Ui^{n-rank}*(U-i)^{rank-1}\)

什么意思?钦定一下\(zsy\)的分数是\(i\),那么所有被\(zsy\)吊打的人的选择就只有\([1,i]\),

而总共有\(n-rank\)个人被吊打,而剩下的人分数比\(zsy\)高,所以被钦定为\([i+1,U]\),一共\((U-i)\)种方法,总共\(rank-1\)个人,大力插值一波假装是对的就好了。

然而我嫌插值太慢,去网上蒯(抄)了一种神仙做法

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 150
#define MOD 1000000007
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int fpow(int a,int b)
{
int s=1;
while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}
return s;
}
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
int n,m,K,u[MAX],rk[MAX],f[MAX][MAX],P[MAX],g[MAX];;
int jc[MAX],jv[MAX],inv[MAX];
int C(int n,int m){if(n<0||m<0||m>n)return 0;return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;}
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)rk[i]=read();
jc[0]=jv[0]=inv[0]=inv[1]=1;
for(int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%MOD;
for(int i=2;i<=n;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;
for(int i=1;i<=m;++i)
{
g[0]=u[i];
for(int j=1;j<=n;++j)
{
g[j]=(fpow(u[i]+1,j+1)-1+MOD)%MOD;
for(int k=0;k<j;++k)add(g[j],MOD-(1ll*C(j+1,k)*g[k]%MOD));
g[j]=1ll*g[j]*fpow(j+1,MOD-2)%MOD;
}
int inv=fpow(u[i],MOD-2),v=fpow(u[i],rk[i]-1),d=1;
for(int j=0;j<rk[i];++j,d=MOD-d,v=1ll*v*inv%MOD)
add(P[i],1ll*C(rk[i]-1,j)*d%MOD*v%MOD*g[n-rk[i]+j]%MOD);
}
f[0][n-1]=1;
for(int i=1;i<=m;++i)
for(int j=K;j<=n;++j)
for(int k=j;k<=n;++k)
add(f[i][j],1ll*f[i-1][k]*C(k,j)%MOD*C(n-k-1,n-rk[i]-j)%MOD*P[i]%MOD);
printf("%d\n",f[m][K]);
return 0;
}
05-12 09:51