| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 481423 |
2021-10-20T18:36:29 Z |
rainboy |
Zapina (COCI20_zapina) |
C |
|
87 ms |
288 KB |
#include <stdio.h>
#define N 350
#define MD 1000000007
int main() {
static int vv[N + 1], ff[N + 1], gg[N + 1], dp[N + 1][2];
int n, i, j, k;
scanf("%d", &n);
ff[0] = gg[0] = 1;
for (i = 1; i <= n; i++) {
vv[i] = i == 1 ? 1 : (long long) vv[i - MD % i] * (MD / i + 1) % MD;
ff[i] = (long long) ff[i - 1] * i % MD;
gg[i] = (long long) gg[i - 1] * vv[i] % MD;
}
dp[0][0] = 1;
for (i = 1; i <= n; i++)
for (j = n; j >= 0; j--)
for (k = 1; j + k <= n; k++)
if (k == i)
dp[j + k][1] = (dp[j + k][1] + (long long) (dp[j][0] + dp[j][1]) * gg[k] % MD) % MD;
else {
dp[j + k][0] = (dp[j + k][0] + (long long) dp[j][0] * gg[k]) % MD;
dp[j + k][1] = (dp[j + k][1] + (long long) dp[j][1] * gg[k]) % MD;
}
printf("%lld\n", (long long) dp[n][1] * ff[n] % MD);
return 0;
}
Compilation message
zapina.c: In function 'main':
zapina.c:10:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
288 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
288 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
0 ms |
204 KB |
Output is correct |
| 17 |
Correct |
47 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
9 ms |
204 KB |
Output is correct |
| 20 |
Correct |
0 ms |
204 KB |
Output is correct |
| 21 |
Correct |
56 ms |
264 KB |
Output is correct |
| 22 |
Correct |
6 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
204 KB |
Output is correct |
| 24 |
Correct |
12 ms |
280 KB |
Output is correct |
| 25 |
Correct |
9 ms |
284 KB |
Output is correct |
| 26 |
Correct |
17 ms |
284 KB |
Output is correct |
| 27 |
Correct |
81 ms |
276 KB |
Output is correct |
| 28 |
Correct |
79 ms |
204 KB |
Output is correct |
| 29 |
Correct |
87 ms |
260 KB |
Output is correct |
| 30 |
Correct |
81 ms |
204 KB |
Output is correct |
| 31 |
Correct |
81 ms |
204 KB |
Output is correct |
| 32 |
Correct |
82 ms |
204 KB |
Output is correct |
| 33 |
Correct |
81 ms |
204 KB |
Output is correct |
| 34 |
Correct |
82 ms |
204 KB |
Output is correct |
| 35 |
Correct |
82 ms |
204 KB |
Output is correct |
| 36 |
Correct |
83 ms |
264 KB |
Output is correct |
| 37 |
Correct |
84 ms |
204 KB |
Output is correct |
