oj.uz

Submission #19658

# Submission time Handle Problem Language Result Execution time Memory
19658 2016-02-25T04:16:21 Z kaTkaHr 카드 (kriii4_Z) C++14
100 / 100
 578 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){}
  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;
		for(int i = 0; i <= L; i++){
			for(int j = 0; j <= i; j++){
				A[k][i] = A[k][i] + A[k-1][i-j] * T[D[k]][j] * C[i][j];
			}
		}
		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 444 ms 142448 KB Output is correct
2 Correct 492 ms 142448 KB Output is correct
3 Correct 417 ms 142448 KB Output is correct
4 Correct 501 ms 142448 KB Output is correct
5 Correct 417 ms 142448 KB Output is correct
6 Correct 345 ms 142448 KB Output is correct
7 Correct 440 ms 142448 KB Output is correct
8 Correct 392 ms 142448 KB Output is correct
9 Correct 509 ms 142448 KB Output is correct
10 Correct 389 ms 142448 KB Output is correct
11 Correct 454 ms 142448 KB Output is correct
12 Correct 386 ms 142448 KB Output is correct
13 Correct 386 ms 142448 KB Output is correct
14 Correct 482 ms 142448 KB Output is correct
15 Correct 471 ms 142448 KB Output is correct
16 Correct 350 ms 142448 KB Output is correct
17 Correct 474 ms 142448 KB Output is correct
18 Correct 385 ms 142448 KB Output is correct
19 Correct 437 ms 142448 KB Output is correct
20 Correct 418 ms 142448 KB Output is correct
21 Correct 567 ms 142448 KB Output is correct
22 Correct 565 ms 142448 KB Output is correct
23 Correct 574 ms 142448 KB Output is correct
24 Correct 578 ms 142448 KB Output is correct
25 Correct 572 ms 142448 KB Output is correct

Subtask #2
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 142448 KB Output is correct
2 Correct 432 ms 142448 KB Output is correct
3 Correct 406 ms 142448 KB Output is correct
4 Correct 451 ms 142448 KB Output is correct
5 Correct 473 ms 142448 KB Output is correct
6 Correct 447 ms 142448 KB Output is correct
7 Correct 418 ms 142448 KB Output is correct
8 Correct 480 ms 142448 KB Output is correct
9 Correct 427 ms 142448 KB Output is correct
10 Correct 415 ms 142448 KB Output is correct
11 Correct 458 ms 142448 KB Output is correct
12 Correct 467 ms 142448 KB Output is correct
13 Correct 472 ms 142448 KB Output is correct
14 Correct 468 ms 142448 KB Output is correct
15 Correct 438 ms 142448 KB Output is correct
16 Correct 478 ms 142448 KB Output is correct
17 Correct 486 ms 142448 KB Output is correct
18 Correct 471 ms 142448 KB Output is correct
19 Correct 448 ms 142448 KB Output is correct
20 Correct 482 ms 142448 KB Output is correct