BZOJ4559 JLOI2016成绩比较（容斥原理+组合数学+斯特林数）

　　容斥一发改为计算至少碾压k人的情况数量，这样对于每门课就可以分开考虑再相乘了。剩下的问题是给出某人的排名和分数的值域，求方案数。枚举出现了几种不同的分数，再枚举被给出的人的分数排第几，算一个类似斯特林数的东西即可。后一部分与碾压几人是无关的，预处理一下，复杂度即为三方。当然和四方跑得也差不多快。

　　数据有些过水，容斥系数都错了还能有90。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define P 1000000007

#define N 210

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,k,a[N],r[N],C[N][N],S[N][N],S2[N][N],v[N],ans;

int ksm(int a,int k)

{

    int s=;

    for (;k;k>>=,a=1ll*a*a%P) if (k&) s=1ll*s*a%P;

    return s;

}

int inv(int a){return ksm(a,P-);}

void pre(int id)

{

    int s=,t=;

    for (int i=;i<=n;i++)

    {

        s=1ll*s*inv(i)%P*(a[id]-i+)%P;t=;

        for (int j=;j<=i;j++)

        t=(t+1ll*S2[n-r[id]+][j]*S[r[id]-][i-j])%P;

        v[id]=(v[id]+1ll*s*t)%P;

    }

}

int g(int id,int k){return 1ll*v[id]*C[n--k][n-r[id]-k]%P;}

int f(int k)

{

    int ans=C[n-][k];

    for (int i=;i<=m;i++)

    ans=1ll*ans*g(i,k)%P;

    return ans;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4559.in","r",stdin);

    freopen("bzoj4559.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),k=read();

    for (int i=;i<=m;i++) a[i]=read();

    int R=n;

    for (int i=;i<=m;i++) R=min(R,n-(r[i]=read()));

    C[][]=;

    for (int i=;i<=;i++)

    {

        C[i][]=C[i][i]=;

        for (int j=;j<;j++)

        C[i][j]=(C[i-][j-]+C[i-][j])%P;

    }

    S[][]=;

    for (int i=;i<=;i++)

        for (int j=;j<=i;j++)

        S[i][j]=(S[i-][j-]+1ll*S[i-][j]*j)%P;

    for (int i=;i<=;i++)

    {

        int fac=;

        for (int j=;j<=i;j++)

        {

            S2[i][j]=1ll*S[i][j]*fac%P;

            fac=1ll*fac*j%P;

            S[i][j]=1ll*S[i][j]*fac%P;

        }

    }

    for (int i=;i<=m;i++) pre(i);

    for (int i=k;i<=R;i++)

    if (i-k&) ans=(ans-1ll*C[i][k]*f(i)%P+P)%P;

    else ans=(ans+1ll*C[i][k]*f(i)%P)%P;

    cout<<ans;

    return ;

}