Submission #19890

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19890	2016-02-25T06:46:42 Z	noslaak	카드 (kriii4_Z)	C++	13 / 100	73 ms	72144 KB

Z

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

Subtask #1

13.0 / 13.0

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

Subtask #2

0.0 / 87.0

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