题意:给你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 ;
}