| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 18990 |
2016-02-17T02:43:10 Z |
kriii |
카드 (kriii4_Z) |
C++14 |
|
622 ms |
142060 KB |
#include <stdio.h>
const long long mod = 1000000007;
long long pow(long long a, long long p)
{
long long r = 1;
a %= mod;
p = (p % (mod - 1) + mod - 1) % (mod - 1);
while (p){
if (p & 1) r = r * a % mod;
a = a * a % mod;
p /= 2;
}
return r;
}
long long comb[3003][3003],sti[3003][3003],fact[3003],prv[3003],nxt[3003];
int cnt[11];
int main()
{
int N,L;
scanf ("%d %d",&N,&L);
comb[0][0] = fact[0] = 1;
for (int i=1;i<=L;i++){
comb[i][i] = comb[i][0] = 1;
for (int j=1;j<i;j++) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % mod;
fact[i] = fact[i-1] * i % mod;
}
for (int i=0;i<N;i++){
int d; scanf ("%d",&d); cnt[d]++;
}
prv[0] = 1;
for (int i=1;i<=L;i++) prv[i] = prv[i-1] * cnt[0] % mod;
for (int d=1;d<=10;d++) if (cnt[d]){
sti[0][0] = 1;
for (int i=1;i<=L;i++){
for (int j=1;j<=cnt[d];j++){
sti[i][j] = j * sti[i-1][j] % mod;
if (i >= d) sti[i][j] = (sti[i][j] + comb[i-1][d-1] * sti[i-d][j-1]) % mod;
}
}
for (int i=0;i<=L;i++) nxt[i] = 0;
for (int i=0;i<=L;i++) for (int j=cnt[d]*d;i+j<=L;j++) nxt[i+j] = (nxt[i+j] + prv[i] * sti[j][cnt[d]] % mod * comb[i+j][j]) % mod;
for (int i=0;i<=L;i++) prv[i] = nxt[i] * fact[cnt[d]] % mod;
}
printf ("%lld\n",prv[L]*pow(N,-L)%mod);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
142060 KB |
Output is correct |
| 2 |
Correct |
59 ms |
142060 KB |
Output is correct |
| 3 |
Correct |
59 ms |
142060 KB |
Output is correct |
| 4 |
Correct |
50 ms |
142060 KB |
Output is correct |
| 5 |
Correct |
50 ms |
142060 KB |
Output is correct |
| 6 |
Correct |
50 ms |
142060 KB |
Output is correct |
| 7 |
Correct |
41 ms |
142060 KB |
Output is correct |
| 8 |
Correct |
61 ms |
142060 KB |
Output is correct |
| 9 |
Correct |
52 ms |
142060 KB |
Output is correct |
| 10 |
Correct |
51 ms |
142060 KB |
Output is correct |
| 11 |
Correct |
61 ms |
142060 KB |
Output is correct |
| 12 |
Correct |
61 ms |
142060 KB |
Output is correct |
| 13 |
Correct |
50 ms |
142060 KB |
Output is correct |
| 14 |
Correct |
46 ms |
142060 KB |
Output is correct |
| 15 |
Correct |
56 ms |
142060 KB |
Output is correct |
| 16 |
Correct |
50 ms |
142060 KB |
Output is correct |
| 17 |
Correct |
63 ms |
142060 KB |
Output is correct |
| 18 |
Correct |
44 ms |
142060 KB |
Output is correct |
| 19 |
Correct |
84 ms |
142060 KB |
Output is correct |
| 20 |
Correct |
57 ms |
142060 KB |
Output is correct |
| 21 |
Correct |
60 ms |
142060 KB |
Output is correct |
| 22 |
Correct |
66 ms |
142060 KB |
Output is correct |
| 23 |
Correct |
65 ms |
142060 KB |
Output is correct |
| 24 |
Correct |
70 ms |
142060 KB |
Output is correct |
| 25 |
Correct |
57 ms |
142060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
142060 KB |
Output is correct |
| 2 |
Correct |
270 ms |
142060 KB |
Output is correct |
| 3 |
Correct |
587 ms |
142060 KB |
Output is correct |
| 4 |
Correct |
551 ms |
142060 KB |
Output is correct |
| 5 |
Correct |
467 ms |
142060 KB |
Output is correct |
| 6 |
Correct |
553 ms |
142060 KB |
Output is correct |
| 7 |
Correct |
515 ms |
142060 KB |
Output is correct |
| 8 |
Correct |
622 ms |
142060 KB |
Output is correct |
| 9 |
Correct |
12 ms |
142060 KB |
Output is correct |
| 10 |
Correct |
320 ms |
142060 KB |
Output is correct |
| 11 |
Correct |
195 ms |
142060 KB |
Output is correct |
| 12 |
Correct |
263 ms |
142060 KB |
Output is correct |
| 13 |
Correct |
193 ms |
142060 KB |
Output is correct |
| 14 |
Correct |
263 ms |
142060 KB |
Output is correct |
| 15 |
Correct |
302 ms |
142060 KB |
Output is correct |
| 16 |
Correct |
312 ms |
142060 KB |
Output is correct |
| 17 |
Correct |
240 ms |
142060 KB |
Output is correct |
| 18 |
Correct |
595 ms |
142060 KB |
Output is correct |
| 19 |
Correct |
571 ms |
142060 KB |
Output is correct |
| 20 |
Correct |
601 ms |
142060 KB |
Output is correct |
