# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
19850 |
2016-02-25T06:15:30 Z |
noslaak |
카드 (kriii4_Z) |
C++ |
|
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 |
- |