解析

依然不會亞qwq
但這次至少有點上道了
(指推出了一個會導致重復計數的錯誤式子)

首先，我們要選出碾壓那些人，方案數就是$C_{n?1}^k$

然后，我們要統計每門學科的排名情況
考慮比B神分數高的人一定是從沒被碾壓的人里選。所以對應的方案就是$C_{n?k?1}^{r_i?1}$，設為$f_k$
但是這樣隨便選可能會導致有的應該沒被碾壓的人一直沒被選到，被碾壓，所以這個東西其實是至少碾壓$k$人的方案數
那么使用常規的容斥套路，這部分的答案就是$f_k?f_{k+1}+f_{k+2}?...$

最后，我們要統計每門學科的分數情況
設$g_{u,a,b}$表示總分數為u，B神前面有a個人，后面有b個人的方案數
枚舉B神的分數 i，那么就有：
$$g_{u,a,b}=\sum _{i?1}^u(u?i{)}^a?i^b$$
但是這個東西暴力算是On的
（PS：我就是卡在這里了）qwq

考慮由于a和b非常少，我們可以使用離散化的思路
設n個人的分數一共有t個取值
枚舉t，就有：
$$g_{u,a,b}=\sum _{t=1}^n{g}_{t,a,b}\times C_u^t$$
里面的 g 可以暴力求解
問題得以解決

代碼

#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; #define ll long long #define il inline il ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m,k; ll c[105][105],u[105],r[105],mx=1000; ll sum[105],jc[105],ni[105]; inline ll ksm(ll x,ll k){ll res=1;while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res; } ll f[105][105];ll D[105]; inline ll g(ll u,ll a,ll b){ll res(0);for(int i=1;i<=u;i++){res+=f[u-i][a]*f[i][b];res%=mod;}return res; } ll G(ll u,ll a,ll b){ll C=1,ans=0;//printf("\nG:u=%lld a=%lld b=%lld\n",u,a,b);for(int t=1;t<=n;t++){ll now=g(t,a,b);for(int i=1;i<t;i++) now=(now-D[i]*c[t][i]%mod+mod)%mod;D[t]=now;C=C*(u-t+1)%mod*jc[t-1]%mod*ni[t]%mod;ans+=now*C;ans%=mod;//printf(" t=%d C=%lld now=%lld ans=%lld\n",t,C,D[t],ans);}return ans; }int main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=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(),mx=min(mx,n-r[i]);jc[0]=1;for(int i=1;i<=100;i++) jc[i]=jc[i-1]*i%mod;ni[n]=ksm(jc[n],mod-2);for(int i=n-1;i>=0;i--) ni[i]=ni[i+1]*(i+1)%mod;for(int i=0;i<=100;i++){f[i][0]=1;for(int j=1;j<=100;j++) f[i][j]=f[i][j-1]*i%mod;}c[0][0]=1;for(int i=1;i<=n;i++){c[i][0]=1;for(int j=1;j<=i;j++){c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}}for(int i=1;i<=m;i++){sum[i]=G(u[i],r[i]-1,n-r[i]);//printf("i=%d sum=%lld\n",i,sum[i]);}ll ans=0;for(int o=k;o<=n;o++){ll now=c[n-k-1][n-o-1];//printf(" i=0 now=%lld\n",now);for(int i=1;i<=m;i++){//now=now*c[n-o-1][r[i]-1]%mod;now=now*c[n-o-1][r[i]-1]%mod*sum[i]%mod;//printf(" i=%d now=%lld\n",i,now);}if((o-k)&1){ans-=now;if(ans<0) ans+=mod;}else{ans+=now;if(ans>=mod) ans-=mod;}//printf("o=%d now=%lld ans=%lld\n\n",o,now,ans);//printf("o=%d now=%lld\n",o,now);}//for(int i=1;i<=m;i++){//ans=ans*sum[i]%mod;//printf("i=%d ans=%lld\n",i,ans);//}printf("%lld\n",ans*c[n-1][k]%mod);return 0; } /**/

總結

以上是生活随笔為你收集整理的洛谷P3270：成绩比较（容斥、组合数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。