| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 670366 |
2022-12-08T19:06:22 Z |
rainboy |
Ruins 3 (JOI20_ruins3) |
C |
|
566 ms |
1744 KB |
#include <stdio.h>
#define N 600
#define MD 1000000007
int vv[N + 1], ff[N + 1], gg[N + 1], dp[N + 1][N + 1], dq[N + 1];
int choose(int n, int k) {
return k < 0 || k > n ? 0 : (long long) ff[n] * gg[k] % MD * gg[n - k] % MD;
}
void init() {
int i, j;
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 = 0; i <= N; i++)
for (j = i; j <= N; j++) {
int x = dp[i][j];
if (x == 0)
continue;
if (i < j)
dp[i + 2][j] = (dp[i + 2][j] + (long long) x * (i + 1) * (i + 2) / 2) % MD;
if (i < N && j < N)
dp[i + 1][j + 1] = (dp[i + 1][j + 1] + (long long) x * (i + 1) * (j + 1)) % MD;
if (j + 2 <= N)
dp[i][j + 2] = (dp[i][j + 2] + (long long) x * (j + 1) * (j + 2) / 2) % MD;
}
for (j = 0; j <= N; j++) {
dq[j] = dp[j][j];
for (i = 1; i < j; i++)
dq[j] = (dq[j] - (long long) dq[i] * choose(j, i) % MD * choose(j - 1, i - 1) % MD * dp[j - i][j - i]) % MD;
if (dq[j] < 0)
dq[j] += MD;
}
}
int main() {
static int kk[N], dr[N + 1];
static char cc[N * 2];
int n, h, i, j, j_, k, x;
init();
scanf("%d", &n);
for (h = 0; h < n; h++) {
scanf("%d", &i), i--;
cc[i] = 1;
}
k = 0;
for (h = 0, i = 0; h < n * 2; h++)
if (cc[h] == 0)
k++;
else
kk[i++] = k;
dr[0] = 1;
for (i = n - 1; i >= 0; i--)
for (j = n - i; j > 0; j--) {
x = 0;
for (j_ = 0; j_ < j; j_++)
x = (x + (long long) dr[j_] * choose(kk[i] - (n - j), j - j_) % MD * choose(n - i - j_ - 1, j - j_ - 1) % MD * dq[j - j_]) % MD;
if (j == n)
printf("%d\n", x);
else
dr[j] = (dr[j] + x) % MD;
}
return 0;
}
Compilation message
ruins3.c: In function 'main':
ruins3.c:50:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
ruins3.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d", &i), i--;
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1716 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1708 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1716 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1744 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1712 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1712 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1712 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1716 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1708 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1716 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1744 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1712 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1712 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1712 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1712 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1708 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1620 KB |
Output is correct |
| 13 |
Correct |
5 ms |
1620 KB |
Output is correct |
| 14 |
Correct |
5 ms |
1620 KB |
Output is correct |
| 15 |
Correct |
5 ms |
1700 KB |
Output is correct |
| 16 |
Correct |
5 ms |
1720 KB |
Output is correct |
| 17 |
Correct |
5 ms |
1620 KB |
Output is correct |
| 18 |
Correct |
5 ms |
1620 KB |
Output is correct |
| 19 |
Correct |
6 ms |
1620 KB |
Output is correct |
| 20 |
Correct |
5 ms |
1708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1716 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1708 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1716 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1744 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1712 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1712 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1712 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1712 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1708 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1620 KB |
Output is correct |
| 13 |
Correct |
5 ms |
1620 KB |
Output is correct |
| 14 |
Correct |
5 ms |
1620 KB |
Output is correct |
| 15 |
Correct |
5 ms |
1700 KB |
Output is correct |
| 16 |
Correct |
5 ms |
1720 KB |
Output is correct |
| 17 |
Correct |
5 ms |
1620 KB |
Output is correct |
| 18 |
Correct |
5 ms |
1620 KB |
Output is correct |
| 19 |
Correct |
6 ms |
1620 KB |
Output is correct |
| 20 |
Correct |
5 ms |
1708 KB |
Output is correct |
| 21 |
Correct |
346 ms |
1696 KB |
Output is correct |
| 22 |
Correct |
346 ms |
1696 KB |
Output is correct |
| 23 |
Correct |
350 ms |
1712 KB |
Output is correct |
| 24 |
Correct |
345 ms |
1696 KB |
Output is correct |
| 25 |
Correct |
343 ms |
1692 KB |
Output is correct |
| 26 |
Correct |
340 ms |
1692 KB |
Output is correct |
| 27 |
Correct |
340 ms |
1696 KB |
Output is correct |
| 28 |
Correct |
351 ms |
1708 KB |
Output is correct |
| 29 |
Correct |
342 ms |
1700 KB |
Output is correct |
| 30 |
Correct |
566 ms |
1740 KB |
Output is correct |
| 31 |
Correct |
457 ms |
1696 KB |
Output is correct |
| 32 |
Correct |
502 ms |
1696 KB |
Output is correct |
| 33 |
Correct |
564 ms |
1740 KB |
Output is correct |
| 34 |
Correct |
449 ms |
1740 KB |
Output is correct |
| 35 |
Correct |
502 ms |
1696 KB |
Output is correct |
| 36 |
Correct |
540 ms |
1692 KB |
Output is correct |
