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

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];
			}
		}
		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	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

Subtask #2

0.0 / 87.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	580 ms	142448 KB	Output isn't correct
2	Halted	0 ms	0 KB	-