Submission #19643

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19643	2016-02-25T03:19:28 Z	kaTkaHr	카드 (kriii4_Z)	C++14	13 / 100	1000 ms	142448 KB

Z

#include <stdio.h>
#include<vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MX = 3005, MM = 1000000007;

template<typename T>
T pw(T A, ll B){
  T R = 1;
  while(B){
    if( B&1 ) R = R * A;
    A = A * A; B /= 2;
  }
  return R;
}

ll rv(ll A){ 
  ll R = 1, B = MM-2;
  while(B){
    if( B&1 ) R = R * A % MM;
    A = A * A % MM; B /= 2;
  }
  return R;
}
/*
struct frac{
  ll A, B;
		frac(ll A):A(A), B(1){}
  frac(ll a, ll b){
    A = (a%MM+MM) % MM;
    B = (b%MM+MM) % MM;
  }
  frac(){A = 0, B = 1;}
  frac operator+ (const frac &l)const{
    return frac((A * l.B + B * l.A) % MM, B * l.B % MM);
  }
  frac operator*(const frac &l)const{
    return frac(A*l.A % MM, B*l.B % MM);
  }
  frac operator/(const frac &l)const{
    return frac(A*l.B % MM, B*l.A % MM);
  }
  frac operator- (const frac &l)const{
    return frac((A*l.B - B*l.A%MM + MM) % MM, B*l.B % MM);
  }
  ll v(){ return A * rv(B) % MM; }
};// */
//*
struct frac{
  ll A;
		frac(ll A):A((A%MM+MM)%MM){}
  frac(ll a, ll b){
			a = (a%MM+MM)%MM;
			b = (b%MM+MM)%MM;
			A = rv(b) * a % MM;
  }
  frac(){A = 0;}
  frac operator+ (const frac &l)const{
			return l.A + A >= MM? l.A + A - MM: l.A + A;
  }
  frac operator*(const frac &l)const{
			return l.A * A % MM;
  }
  frac operator/(const frac &l)const{
			return A * rv(l.A) % MM;
  }
  frac operator- (const frac &l)const{
			return A >= l.A? A-l.A: A-l.A + MM;
  }
  ll v(){ return A; }
};// */

int D[MX];
frac T[MX][MX];
frac C[MX][MX];
frac A[11][MX];

int main()
{
	int N, L;
	scanf("%d%d", &N, &L);
	for(int i = 1; i <= N; i++){
		int A;
		scanf("%d", &A);
		D[A]++;
	}
	C[0][0] = 1;
	for(int i = 1; i <= 3000; i++){
		C[i][0] = 1;
		for(int j = 1; j <= i; j++){
			C[i][j] = C[i-1][j] + C[i-1][j-1];
		}
	}
	A[0][0] = 1;
	for(int i = 1; i <= L; i++) A[0][i] = A[0][i-1] * D[0];
	for(int k = 1; k <= 10; k++){
		T[0][0] = 1;
		for(int i = 1; i <= D[k]; i++){
			for(int j = 1; j <= L; j++){
				T[i][j] = T[i][j-1] * i;
				if( j >= k) T[i][j] = T[i][j] + T[i-1][j-k] * C[j-1][k-1];
			}
		}
		frac mul = 1;
		for(int i = 1; i <= D[k]; i++) mul = mul * i;
		if( D[k] ){
			for(int i = 0; i <= L; i++){
				for(int j = 0; j <= i; j++){
					A[k][i] = A[k][i] + A[k-1][j] * T[D[k]][i-j] * C[i][j];
				}
			}
		}
		else{
			for(int i = 0; i <= L; i++) A[k][i] = A[k-1][i];
		}
		for(int i = 0; i <= L; i++) A[k][i] = A[k][i] * mul;
	}

	frac ans = A[10][L];
	for(int i = 1; i <= L; i++) ans = ans / N;
	printf("%lld\n", ans.v());
}

Subtask #1

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	266 ms	142448 KB	Output is correct
2	Correct	420 ms	142448 KB	Output is correct
3	Correct	392 ms	142448 KB	Output is correct
4	Correct	437 ms	142448 KB	Output is correct
5	Correct	290 ms	142448 KB	Output is correct
6	Correct	189 ms	142448 KB	Output is correct
7	Correct	311 ms	142448 KB	Output is correct
8	Correct	263 ms	142448 KB	Output is correct
9	Correct	471 ms	142448 KB	Output is correct
10	Correct	343 ms	142448 KB	Output is correct
11	Correct	343 ms	142448 KB	Output is correct
12	Correct	222 ms	142448 KB	Output is correct
13	Correct	296 ms	142448 KB	Output is correct
14	Correct	363 ms	142448 KB	Output is correct
15	Correct	458 ms	142448 KB	Output is correct
16	Correct	226 ms	142448 KB	Output is correct
17	Correct	335 ms	142448 KB	Output is correct
18	Correct	314 ms	142448 KB	Output is correct
19	Correct	206 ms	142448 KB	Output is correct
20	Correct	351 ms	142448 KB	Output is correct
21	Correct	554 ms	142448 KB	Output is correct
22	Correct	568 ms	142448 KB	Output is correct
23	Correct	559 ms	142448 KB	Output is correct
24	Correct	567 ms	142448 KB	Output is correct
25	Correct	563 ms	142448 KB	Output is correct

Subtask #2

0.0 / 87.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	597 ms	142448 KB	Output is correct
2	Correct	652 ms	142448 KB	Output is correct
3	Execution timed out	1000 ms	142448 KB	Program timed out
4	Halted	0 ms	0 KB	-