JLOI/SHOI2016成绩比较

刚开始一头雾水

不过考虑分解一下

1. 选k个同学不被碾压\(ans*=C^k_{n-1}\)

2. 不被碾压的同学中至少有一门课成绩大于B神

   考虑容斥，\(i\)个同学完全碾压，剩余不知

   \(ans*=\sum_{i=0}^{k}(-1)^iC^i_k\prod_{j=1}^mC^{k-i}_{r_j-1}\)

3. 现在得到的是相对关系，还未对每个排名进行成绩赋值

   \(ans*=\prod_{i=1}^m\sum_{j=1}^{u_i}j^{n-r_i}(u_i-j)^{r_i-1}\)

   后面这个是关于\(u_i\)的\(n\)次多项式，用拉格朗日插值

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f==1?x:-x;
}
#define ll long long
const int N=104,mod=1e9+7;
inline int ksm(int x,int r){
    int ret=1;
    for(int i=0;(1ll<<i)<=r;i++){
        if((r>>i)&1)ret=(ll)ret*x%mod;
        x=(ll)x*x%mod;
    }
    return ret;
}
int n,m,k,u[N],r[N],ans,c[N][N],inv[N],f[N];
int main(){
    n=read();m=read();k=n-1-read();
    for(int i=1;i<=m;i++)u[i]=read();
    for(int i=1;i<=m;i++)r[i]=read();
    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]+c[i-1][j-1])%mod;
    }
    inv[0]=inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
    for(int i=0,x;i<=k;i++){
        x=c[k][i];
        if(i&1)x=mod-x;
        for(int j=1;j<=m;j++)x=(ll)x*c[k-i][r[j]-1]%mod;
        ans=(ans+x)%mod;
    }
    for(int i=1,x,s;i<=m;i++){
        for(int j=1;j<=n;j++){
            f[j]=0;
            for(int v=1;v<=j;v++)
                f[j]=((ll)ksm(v,n-r[i])*ksm(j-v,r[i]-1)+f[j])%mod;
        }
        if(u[i]<=n){ans=(ll)ans*f[u[i]]%mod;continue;}
        x=0;
        for(int j=1;j<=n;j++){
            s=f[j];
            for(int k=0;k<=n;k++)
                if(k!=j)s=(ll)s*(u[i]-k)%mod*(j>k?inv[j-k]:mod-inv[k-j])%mod;
            x=(x+s)%mod;
        }
        ans=(ll)ans*x%mod;
    }
    cout<<(ll)ans*c[n-1][k]%mod;
    return (0-0);
}

JLOI/SHOI2016成绩比较

原文：https://www.cnblogs.com/aurora2004/p/12539860.html