Submission #19850

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19850	2016-02-25T06:15:30 Z	noslaak	카드 (kriii4_Z)	C++	0 / 100	1000 ms	36956 KB

Z

#include <iostream>
const int LARGE_NUMBER = 1000000007;

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 )
	{
		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[3001][3001];

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 < 3001; ++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	36952 KB	Output is correct
2	Correct	870 ms	36956 KB	Output is correct
3	Correct	5 ms	36900 KB	Output is correct
4	Correct	803 ms	36956 KB	Output is correct
5	Correct	894 ms	36944 KB	Output is correct
6	Correct	348 ms	36936 KB	Output is correct
7	Correct	982 ms	36952 KB	Output is correct
8	Correct	806 ms	36944 KB	Output is correct
9	Correct	542 ms	36956 KB	Output is correct
10	Correct	583 ms	36932 KB	Output is correct
11	Correct	962 ms	36944 KB	Output is correct
12	Correct	487 ms	36944 KB	Output is correct
13	Correct	873 ms	36936 KB	Output is correct
14	Execution timed out	1000 ms	36956 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	-