51nod 1231 记分牌

时间：2023-03-10 05:07:05
51nod 1231 记分牌

链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1231

一个得分合法等价于前k小的得分之和大于等于$\frac{k*(k-1)}{2}$

听说是竞赛图的经典结论，可是我不会证。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define w(x) (x)*(x-1)/2

using namespace std;

int read_p,read_ca,read_f;

inline int read(){

    read_p=;read_ca=getchar();read_f=;

    while(read_ca<''||read_ca>'') {if (read_ca=='-') read_f=-;read_ca=getchar();}

    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();

    return read_p*read_f;

}

const int MOD=1e9+;

int T,n,m,mmh[][][],a,t[],q[],C[][];

inline void M(int &x){while(x>=MOD)x-=MOD;}

int main(){

    register int i,j,k,l;

    T=read();

    C[][]=;

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

    for (C[i][]=,j=;j<=i;j++) M(C[i][j]=C[i-][j]+C[i-][j-]);

    while (T--){

        n=read();

        memset(mmh,,sizeof(mmh));memset(t,,sizeof(t));

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

            a=read();

            if (a!=-) t[a]++;else t[n]++;

        }

        if (t[]>) {puts("");continue;}

        if (t[]==) if (mmh[][][]=,t[n]) mmh[][][]=C[t[n]][];

        if (t[]==) mmh[][][]=;q[]=t[];

        for (i=;i<n;i++) q[i]=q[i-]+t[i];

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

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

        for (k=;k<=n*n;k++)

        if (mmh[i][j-][k]){

            for (l=;l<=t[j];l++) if (k+j*l<w(i+l)) break;

            if (l<=t[j]) continue;

            for (l=t[j];l<=q[j]+t[n]-i;l++)

            if (k+j*l>=w(i+l)) M(mmh[i+l][j][k+j*l]+=1LL*mmh[i][j-][k]*C[t[n]-(i-q[j-])][l-t[j]]%MOD);

        }

        printf("%d\n",mmh[n][n-][w(n)]);

    }

}

相关文章