Submission #19630

# Submission time Handle Problem Language Result Execution time Memory
19630 2016-02-25T02:44:23 Z kaTkaHr 카드 (kriii4_Z) C++14
13 / 100
580 ms 142448 KB
#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];
			}
		}
		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());
}
# Verdict Execution time Memory Grader output
1 Correct 251 ms 142448 KB Output is correct
2 Correct 385 ms 142448 KB Output is correct
3 Correct 380 ms 142448 KB Output is correct
4 Correct 403 ms 142448 KB Output is correct
5 Correct 271 ms 142448 KB Output is correct
6 Correct 195 ms 142448 KB Output is correct
7 Correct 306 ms 142448 KB Output is correct
8 Correct 254 ms 142448 KB Output is correct
9 Correct 441 ms 142448 KB Output is correct
10 Correct 329 ms 142448 KB Output is correct
11 Correct 334 ms 142448 KB Output is correct
12 Correct 211 ms 142448 KB Output is correct
13 Correct 278 ms 142448 KB Output is correct
14 Correct 346 ms 142448 KB Output is correct
15 Correct 428 ms 142448 KB Output is correct
16 Correct 227 ms 142448 KB Output is correct
17 Correct 302 ms 142448 KB Output is correct
18 Correct 295 ms 142448 KB Output is correct
19 Correct 203 ms 142448 KB Output is correct
20 Correct 341 ms 142448 KB Output is correct
21 Correct 509 ms 142448 KB Output is correct
22 Correct 515 ms 142448 KB Output is correct
23 Correct 514 ms 142448 KB Output is correct
24 Correct 517 ms 142448 KB Output is correct
25 Correct 522 ms 142448 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 580 ms 142448 KB Output isn't correct
2 Halted 0 ms 0 KB -