oj.uz

답안 #19646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19646 2016-02-25T03:21:38 Z kaTkaHr 카드 (kriii4_Z) C++14
13 / 100
 1000 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] * 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 = k*D[k]; i <= L; i++){
				for(int j = k*D[k]; j <= i; j++){
					A[k][i] = A[k][i] + A[k-1][i-j] * T[D[k]][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

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 142448 KB Output is correct
2 Correct 280 ms 142448 KB Output is correct
3 Correct 288 ms 142448 KB Output is correct
4 Correct 288 ms 142448 KB Output is correct
5 Correct 197 ms 142448 KB Output is correct
6 Correct 166 ms 142448 KB Output is correct
7 Correct 216 ms 142448 KB Output is correct
8 Correct 188 ms 142448 KB Output is correct
9 Correct 311 ms 142448 KB Output is correct
10 Correct 237 ms 142448 KB Output is correct
11 Correct 234 ms 142448 KB Output is correct
12 Correct 180 ms 142448 KB Output is correct
13 Correct 201 ms 142448 KB Output is correct
14 Correct 245 ms 142448 KB Output is correct
15 Correct 330 ms 142448 KB Output is correct
16 Correct 173 ms 142448 KB Output is correct
17 Correct 230 ms 142448 KB Output is correct
18 Correct 209 ms 142448 KB Output is correct
19 Correct 196 ms 142448 KB Output is correct
20 Correct 234 ms 142448 KB Output is correct
21 Correct 405 ms 142448 KB Output is correct
22 Correct 397 ms 142448 KB Output is correct
23 Correct 396 ms 142448 KB Output is correct
24 Correct 403 ms 142448 KB Output is correct
25 Correct 409 ms 142448 KB Output is correct

Subtask #2
0.0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 448 ms 142448 KB Output is correct
2 Correct 622 ms 142448 KB Output is correct
3 Execution timed out 1000 ms 142448 KB Program timed out
4 Halted 0 ms 0 KB -