CodeChef LEMOVIE

题意:给你n个数字(下标不同数值相同的数字应当被认为是不同的数字),有n!种排列方式.每种排列方式的价值定义为:第一次出现时比前面的所有数字都大的数值个数.

比如1,2,2,3这个排列中,1,2,3这三个数值第一次出现的时候都比前面的所有数字都大,所以这个排列的价值是3.

1,3,1,2这个排列中,1和3第一次出现的时候比前面的所有数字都大,所以这个排列的价值是2.

30分n<=10,另外30分所有数值互不相同.

n<=10只需要n!枚举,所有数值互不相同的时候,我们可以考虑向序列中从大到小一个一个添加数字,那么新添加的数字必须位于当前序列的最前面才会使序列的价值+1,否则序列的价值不变,定义f[i][j]为放置最大的i个数字且当前价值为j的方案数,那么f[i][j]=f[i-1][j-1]+f[i-1][j]*(i-1)

100分的做法需要我们解决一下数值重复出现的情况.那么还是从大到小考虑每一个数值,只需要考虑新加入的数值是否会对答案贡献1.如果所有新加入的数值前面至少有一个原先存在的较大的数值,那么就不会产生贡献.假如原来有x个较大的数值,现在插入y个大小相同的较小数值,那么总的方案数为C(x+y,y),如果要求这y个数值不能产生贡献,即插入后的序列的第一个数还得是原先x个数中的第一个,那么总的方案数为C(x-1+y,y),产生贡献的方案数用总方案数减一下就可以了.

比HEOI2013SAO简单多了.

#include<cstdio>

#include<cstring>

typedef long long ll;

const ll mod=;

const int maxn=;

ll fac[maxn];

ll C[maxn][maxn];

void init(){

    fac[]=;

    for(int i=;i<maxn;++i)fac[i]=fac[i-]*i%mod;

    C[][]=;

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

        C[i][]=;

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

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

        }

    }

}

int cnt[maxn];

int f[maxn][maxn];

int main(){

    init();

    int tests;scanf("%d",&tests);

    while(tests--){

        memset(cnt,,sizeof(cnt));memset(f,,sizeof(f));

        int n,k;scanf("%d%d",&n,&k);

        int x;

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

            scanf("%d",&x);cnt[x]++;

        }

        int tot=,sum=;

        for(int i=;i>=;--i){//1<=Ai<=200

            if(cnt[i]!=){

                if(tot==){

                    ++tot;f[][]=fac[cnt[i]];

                }else{

                    ++tot;

                    ll sol0=C[sum+cnt[i]-][cnt[i]]*fac[cnt[i]]%mod,sol1=(C[sum+cnt[i]][cnt[i]]*fac[cnt[i]]%mod-sol0+mod)%mod;;

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

                        f[tot][j]=(f[tot][j]+f[tot-][j]*sol0%mod)%mod;

                        if(j>)f[tot][j]=(f[tot][j]+f[tot-][j-]*sol1%mod)%mod;

                    }

                }

                sum+=cnt[i];

            }

        }

        ll ans=;

        for(int i=;i<=k;++i)ans=(ans+f[tot][i])%mod;

        printf("%lld\n",ans);

    }

    return ;

}