답안 #19890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19890 2016-02-25T06:46:42 Z noslaak 카드 (kriii4_Z) C++
13 / 100
73 ms 72144 KB
#include <iostream>
const int LARGE_NUMBER = 1000000007;
const int size = 3001;

int fracs[size][size] = {0,};
template<int LN>
struct fraction
{
	int mod;
	fraction() : mod(0) {}
	fraction(int _denom, int _num)
	{
		if( _denom < size && _num < size && fracs[_denom][_num] )
		{
			mod = fracs[_denom][_num];
		}
		else
		{
			mod = getmod(_denom,_num);
			if( _denom < size && _num < size )
				fracs[_denom][_num] = mod;
		}
	}

	int modpow( long long A, long long X )
	{
		int acc = 1;
		while(X)
		{
			A %= LN;
			if(X%2)
				acc = (A*acc)%LN;
			A = A*A;
			X /= 2;
		}
		return acc;
	}

	int getmod( int denom, int num )
	{
		int rev = modpow(denom, LN-2);
		int mod = ((long long)num*rev)%LN;
		return mod;
	}

	fraction operator+( const fraction& op )
	{
		return fraction((this->mod+op.mod)%LN);
	}
	fraction operator-( const fraction& op )
	{
		return fraction((this->mod-op.mod+LN)%LN);
	}
	fraction operator*( const fraction& op )
	{
		return fraction(((long long)(this->mod)*op.mod)%LN);
	}
	fraction operator/( const fraction& op )
	{
		return fraction(op.mod, this->mod);
	}

private:
	fraction(int _mod) : mod(_mod) {}
};
typedef fraction<LARGE_NUMBER> frac;


int N, L;
frac probs[size][size];

frac calc_prob( int remain_D, int remain_L )
{
	if( probs[remain_D][remain_L].mod != -1 )
		return probs[remain_D][remain_L];
	if( remain_D > remain_L )
		return frac();
	
	frac p1 = calc_prob(remain_D, remain_L-1) * frac(N, N-remain_D);
	frac p2 = calc_prob(remain_D-1, remain_L-1) * frac(N, remain_D);
	probs[remain_D][remain_L] = p1+p2;
	return probs[remain_D][remain_L];
}

int main()
{
	probs[0][0].mod = 1;
	for( int i = 1; i < size; ++i )
	{
		probs[i][0].mod = 0;
		probs[0][i].mod = 1;
	}

	while( std::cin >> N >> L )
	{
		for( int i = 1; i <= N; ++i ) for( int j = 1; j <= L; ++j ) probs[i][j].mod = -1;

		int remain_D = 0;
		for( int i = 0; i < N; ++i )
		{
			int D;
			std::cin >> D;
			if( D == 1 )
				++remain_D;
		}

		frac prob = calc_prob( remain_D, L );
		std::cout << prob.mod << std::endl;
	}

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 72136 KB Output is correct
2 Correct 62 ms 72132 KB Output is correct
3 Correct 3 ms 72080 KB Output is correct
4 Correct 51 ms 72136 KB Output is correct
5 Correct 65 ms 72124 KB Output is correct
6 Correct 24 ms 72120 KB Output is correct
7 Correct 65 ms 72128 KB Output is correct
8 Correct 55 ms 72124 KB Output is correct
9 Correct 36 ms 72132 KB Output is correct
10 Correct 49 ms 72116 KB Output is correct
11 Correct 66 ms 72132 KB Output is correct
12 Correct 39 ms 72120 KB Output is correct
13 Correct 63 ms 72116 KB Output is correct
14 Correct 68 ms 72132 KB Output is correct
15 Correct 3 ms 72080 KB Output is correct
16 Correct 43 ms 72112 KB Output is correct
17 Correct 73 ms 72132 KB Output is correct
18 Correct 59 ms 72108 KB Output is correct
19 Correct 13 ms 72140 KB Output is correct
20 Correct 57 ms 72120 KB Output is correct
21 Correct 17 ms 72144 KB Output is correct
22 Correct 18 ms 72144 KB Output is correct
23 Correct 17 ms 72140 KB Output is correct
24 Correct 10 ms 72144 KB Output is correct
25 Correct 18 ms 72140 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 67 ms 72128 KB Output isn't correct
2 Halted 0 ms 0 KB -