Submission #19811

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19811	2016-02-25T05:50:27 Z	noslaak	카드 (kriii4_Z)	C++	0 / 100	1000 ms	36904 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 > 0 )
		return probs[remain_D][remain_L];
	if( remain_D > remain_L )
		return frac();
	if( remain_D == 0 )
		return frac(1,1);

	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);
	return p1+p2;
}

int main()
{
	probs[0][0].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 = 0;

		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	Execution timed out	1000 ms	36904 KB	Program timed out
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 87.0

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