Submission #19646

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19646	2016-02-25T03:21:38 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 = 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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-