#include <stdio.h>
#include <string.h>
#define N 99
#define MD 1000000007
int dp[N * 3 + 1][N * 3 + 1][N * 3 + 1];
int branch(int ab, int bc, int ca, int a, int upd) {
int x;
x = 0;
if (a == 0) {
if (ab == 0 && ca == 0)
x = branch(ab, bc, ca, 1, upd);
else {
if (ab > 0)
x = (x + (long long) branch(ab - 1, bc, ca, 1, 1) * ab) % MD;
if (ca > 0)
x = (x + (long long) branch(ab, bc + 1, ca - 1, 1, upd) * ca) % MD;
}
} else if (a == 1) {
if (bc == 0 && ab == 0)
x = branch(ab, bc, ca, 2, upd);
else {
if (bc > 0)
x = (x + (long long) branch(ab, bc - 1, ca, 2, 1) * bc) % MD;
if (ab > 0)
x = (x + (long long) branch(ab - 1, bc, ca + 1, 2, upd) * ab) % MD;
}
} else if (a == 2) {
if (ca == 0 && bc == 0)
x = branch(ab, bc, ca, 3, upd);
else {
if (ca > 0)
x = (x + (long long) branch(ab, bc, ca - 1, 3, 1) * ca) % MD;
if (bc > 0)
x = (x + (long long) branch(ab + 1, bc - 1, ca, 3, upd) * bc) % MD;
}
} else
x = upd ? dp[ab][bc][ca] : 0;
return x;
}
int main() {
static int aa[N * 3], bb[N * 3];
int t, n, i, s, ab, bc, ca, a, c;
scanf("%d%d", &n, &t);
dp[0][0][0] = 1;
for (s = 1; s <= n * 3; s++)
for (ab = 0; ab <= s; ab++)
for (bc = 0; ab + bc <= s; bc++) {
ca = s - ab - bc;
dp[ab][bc][ca] = branch(ab, bc, ca, 0, 0);
}
while (t--) {
memset(aa, -1, n * 3 * sizeof *aa), memset(bb, -1, n * 3 * sizeof *bb);
for (a = 0; a < 3; a++)
for (i = 0; i < n * 2; i++) {
scanf("%d", &c), c--;
if (aa[c] == -1)
aa[c] = a;
else
bb[c] = a;
}
ab = bc = ca = 0;
for (c = 0; c < n * 3; c++)
if (aa[c] == 0 && bb[c] == 1)
ab++;
else if (aa[c] == 1 && bb[c] == 2)
bc++;
else if (aa[c] == 0 && bb[c] == 2)
ca++;
printf("%d\n", dp[ab][bc][ca]);
}
return 0;
}
Compilation message
fishing.c: In function 'main':
fishing.c:49:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d%d", &n, &t);
| ^~~~~~~~~~~~~~~~~~~~~
fishing.c:61:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d", &c), c--;
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
4 ms |
10588 KB |
Output is correct |
| 4 |
Correct |
7 ms |
21084 KB |
Output is correct |
| 5 |
Correct |
71 ms |
52544 KB |
Output is correct |
| 6 |
Correct |
90 ms |
62528 KB |
Output is correct |
| 7 |
Correct |
132 ms |
75092 KB |
Output is correct |
| 8 |
Correct |
192 ms |
85396 KB |
Output is correct |
| 9 |
Correct |
276 ms |
95760 KB |
Output is correct |
| 10 |
Correct |
361 ms |
98204 KB |
Output is correct |
