題目：https://www.lydsy.com/JudgeOnline/problem.php?id=4559

看了看拉格朗日插值：http://www.cnblogs.com/ECJTUACM-873284962/p/6833391.html

https://blog.csdn.net/lvzelong2014/article/details/79159346

https://blog.csdn.net/qq_35649707/article/details/78018944

還只會(huì)最簡(jiǎn)單的那種，正好在這道題里可以用到；

計(jì)算方案數(shù)，可以考慮DP，利用那個(gè)所有成績(jī)都小于 B 的性質(zhì)，枚舉超過(guò) B 的一門(mén)課；

設(shè)計(jì) f[i][j] 表示當(dāng)前到了第 i 門(mén)課，還剩 j 個(gè)人被碾壓(一開(kāi)始是所有人都被碾壓，然后漸漸突破...)；

則 f[i][j] = ∑(j<=t<=n-1) f[i-1][t] * C(n-1-t,rk[i]-1-(t-j)) * C(t,j) * g[i]

其中第一個(gè)組合數(shù)表示在 n-1-t 個(gè)上一次已經(jīng)不被碾壓的人中選出? rk[i]-1-(t-j) 個(gè)作為這次成績(jī)高于 B 的人，第二個(gè)組合數(shù)表示從 t 個(gè)上次被碾壓的人中選出 j 個(gè)這次仍然被碾壓(也等同與選出 t-j 個(gè)人這次成績(jī)高于 B )；

g[i] 則表示在 i 這門(mén)課上的成績(jī)分布情況，則選出的人的成績(jī)可以對(duì)號(hào)入座；

而 g[i] = ∑(1<=j<=lim[i]) j^(n-rk[i]) * (lim[i]-j)^(rk[i]-1)，表示若 B 的成績(jī)是 j，則有 n-rk[i] 個(gè)人的成績(jī)?cè)?1~j 中選擇，有 rk[i]-1 個(gè)人的成績(jī)?cè)?lim[i]-j~lim[i] 中選擇；

可以發(fā)現(xiàn)這是個(gè)大約 n+1 次的多項(xiàng)式，所以設(shè)出幾個(gè)點(diǎn)，求出當(dāng) x=lim 時(shí)的取值即可，這個(gè)過(guò)程的復(fù)雜度是 n^2 的。

代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int const xn=105,mod=1e9+7; int n,m,K,lm[xn],rk[xn],g[xn],c[xn][xn],f[xn][xn],xx[xn],yy[xn]; int rd() {int ret=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();return f?ret:-ret; } int pw(ll a,int b) {ll ret=1; for(;b;b>>=1,a=(a*a)%mod)if(b&1)ret=(ret*a)%mod;return ret; } int upt(int x){while(x>=mod)x-=mod; while(x<0)x+=mod; return x;} void init() {for(int i=0;i<=n;i++)c[i][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)c[i][j]=upt(c[i-1][j]+c[i-1][j-1]); } int solve(int lim,int n,int m) {int num=n+m+2,sum=0;for(int i=1;i<=num;i++)xx[i]=i,yy[i]=upt(yy[i-1]+(ll)pw(i,n)*pw(lim-i,m)%mod);for(int i=1;i<=num;i++){ll s1=1,s2=1;for(int j=1;j<=num;j++)if(i!=j)//!!!s1=s1*(lim-xx[j])%mod,s2=s2*(xx[i]-xx[j])%mod;sum=upt(sum+s1*pw(s2,mod-2)%mod*yy[i]%mod);}return sum; } int main() {n=rd()-1; m=rd(); K=rd(); init();//n-1for(int i=1;i<=m;i++)lm[i]=rd();for(int i=1;i<=m;i++)rk[i]=rd(),g[i]=solve(lm[i],n-rk[i]+1,rk[i]-1);//+1f[0][n]=1;//nfor(int i=1;i<=m;i++)for(int j=K;j<=n;j++)//kfor(int t=j;t<=n;t++){if(t-j>rk[i]-1||j>n-rk[i]+1)continue;//+1!f[i][j]=upt(f[i][j]+(ll)f[i-1][t]*c[t][j]%mod*c[n-t][rk[i]-1-t+j]%mod*g[i]%mod);}printf("%d\n",f[m][K]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Zinn/p/10006681.html

總結(jié)

以上是生活随笔為你收集整理的bzoj 4559 [JLoi2016]成绩比较 —— DP+拉格朗日插值的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。