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
#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;
}
# 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 -
# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -