Submission #19866

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19866	2016-02-25T06:22:54 Z	noslaak	카드 (kriii4_Z)	C++	0 / 100	1000 ms	72136 KB

Z

#include <iostream>
const int LARGE_NUMBER = 1000000007;
const int size = 3001;

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

	int modpow( long long A, long long X )
	{
		if( A < size && X < size && pows[size][size] > 0 )
			return pows[size][size];
			
		int acc = 1;
		while(X)
		{
			A %= LN;
			if(X%2)
				acc = (A*acc)%LN;
			A = A*A;
			X /= 2;
		}

		if( A < size && X < size )
			pows[size][size] = acc;
		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

0.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	681 ms	72136 KB	Output is correct
2	Correct	872 ms	72132 KB	Output is correct
3	Correct	10 ms	72080 KB	Output is correct
4	Correct	804 ms	72132 KB	Output is correct
5	Correct	898 ms	72124 KB	Output is correct
6	Correct	351 ms	72112 KB	Output is correct
7	Correct	982 ms	72132 KB	Output is correct
8	Correct	795 ms	72120 KB	Output is correct
9	Correct	538 ms	72132 KB	Output is correct
10	Correct	587 ms	72116 KB	Output is correct
11	Correct	968 ms	72132 KB	Output is correct
12	Correct	490 ms	72128 KB	Output is correct
13	Correct	868 ms	72116 KB	Output is correct
14	Execution timed out	1000 ms	72136 KB	Program timed out
15	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 87.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-