Little Elephant and Movies

Description:

Little Elephant from Zoo of Lviv likes to watch movies. There are N different movies (numbered from 0 to N 1) he wants to watch in some order. Of course, he will watch each movie exactly once. The priority of ith movie is Pi. A watching of a movie is called exciting if and only if one of the following two conditions holds: This is the first watching. The priority of this movie is strictly greater than the maximal priority of the movies watched so far. Let us call the number of exciting watchings the excitingness of the order. Help him to find the number of different watching orders whose excitingness does not exceed K. Since the answer can be large, print it modulo 1000000007 (109+7). Input The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow. The first line of each test case contains two space-separated integers N and K. The next line contains N space-separated integers P1, P2, ..., PN. Output For each test case, print the number of different watching orders having at most K excitingness modulo 1000000007 (109+7). Constraints 1<=T<=10 1<=K<=N<=200 1<=Pi<=200 In the first case, there are two boring watching orders whose excitingness not greater than K=1: [3, 1, 2], [3, 2, 1]. Both watching orders have one exciting watching: the first watching. In the second case, every watching order has at most 3 excitingness. Test Case 1 Input (stdin) 2 3 1 3 1 2 4 3 1 2 2 3 Expected Output 2 24 Test Case 2 Input (stdin) 0 Expected Output 0

Program :

#include<stdio.h>


#define MAX 210

#define MOD 1000000007

typedef unsigned int UD;

typedef unsigned long long ULL;


UD comb[MAX][MAX]={0};

UD fact[MAX]={0};


/*UD partfact2(UD m, UD n)

{

UD ans;

for(i=0;i<(n-1);i++)

{

m++;

ans=((ULL)ans*m)%MOD;

}

ans = ((ULL)comb[m+n-1][m]*fact[n])%MOD;

//ans = ((ULL)ans*n)%MOD;

return ans;

}


UD partfact1(UD m, UD n)

{

UD ans;

for(i=0;i<(n-1);i++)

{

m++;

ans=((ULL)ans*m)%MOD;

}

//ans = ((ULL)ans*temp)%MOD;

ans = ((ULL)comb[m+n-1][m-1]*fact[n])%MOD;

return ans;

}*/

UD solve()

{

UD N,K,i,num,count=0,m=0,n,j,fact1,fact2,ans=0;

UD P[MAX]={0},Karray[MAX][2]={0};

scanf("%u %u",&N,&K);

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

{

scanf("%u",&num);

P[num]++;

}

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

{

if(P[i]>0)

{

count=i;

}

}

n=P[count];

Karray[1][1]=((ULL)comb[m+n-1][m]*fact[n])%MOD;

Karray[1][0]=Karray[1][1];

for(i=count-1;i>0;i--)

{


m=m+n;

n=P[i];

if(n==0)

{

continue;

}

else

{

fact1=((ULL)comb[m+n-1][m-1]*fact[n])%MOD;

fact2=((ULL)comb[m+n-1][m]*fact[n])%MOD;

for(j=1;j<=(count-i+1) && j<=K;j++)

{

Karray[j][0]=Karray[j][1];

Karray[j][1]=((ULL)((ULL)Karray[j][0]*fact1)%MOD + ((ULL)Karray[j-1][0]*fact2)%MOD)%MOD;

}


}

}

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

{

ans=((ULL)ans+Karray[i][1])%MOD;

}

return ans;

}


int main()

{


UD T,ans,i,j;

// UD comb[MAX][MAX]={0};

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

{

comb[i][0]=1;

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

{

comb[i][j]=((ULL)comb[i-1][j] + comb[i-1][j-1])%MOD;

}

}

fact[0]=1;

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

{

fact[i]=((ULL)fact[i-1]*i)%MOD;

}

scanf("%u",&T);

while(T--)

{

ans=solve();

/*for(i=0;i<MAX;i++)

{

P[i]=0;

Karray[i][0]=0;

Karray[i][1]=0;

}*/

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

}

return 0;

}