#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
const int N = 100;
int dp[1 + 3 * N][1 + 3 * N][1 + 3 * N][3][2]; /// A B C : 0/1 done
int freqA[1 + 3 * N], freqB[1 + 3 * N], freqC[1 + 3 * N];
int f[1 + 3 * N];
const int MOD = 1e9 + 7;
void add (int &a, int b) {
a += b;
if (a >= MOD)
a -= MOD;
}
int getDp (int ab, int bc, int ca, int turn, bool moved) {
if (ab + bc + ca == max ({ab, bc, ca})) {
return f[max ({ab, bc, ca})];
}
if (dp[ab][bc][ca][turn][moved]) return dp[ab][bc][ca][turn][moved];
int ans = 0;
if (turn == 0) { /// A -> B or A -> C
if (ab > 0)
add (ans, 1ll * ab * getDp (ab - 1, bc, ca, turn + 1, true) % MOD);
if (ca > 0)
add (ans, 1ll * ca * getDp (ab, bc + 1, ca - 1, turn + 1, moved) % MOD);
if (ab == 0 && ca == 0)
add (ans, getDp (ab, bc, ca, turn + 1, moved));
}
if (turn == 1) { /// B -> A or B -> C
if (bc > 0)
add (ans, 1ll * bc * getDp (ab, bc - 1, ca, turn + 1, true) % MOD);
if (ab > 0)
add (ans, 1ll * ab * getDp (ab - 1, bc, ca + 1, turn + 1, moved) % MOD);
if (ab == 0 && bc == 0)
add (ans, getDp (ab, bc, ca, turn + 1, moved));
}
if (turn == 2) { /// C -> B or C -> A
if (ca > 0)
add (ans, 1ll * ca * getDp (ab, bc, ca - 1, 0, 0) % MOD);
if (moved) {
if (bc > 0)
add (ans, 1ll * bc * getDp (ab, bc - 1, ca + 1, 0, 0) % MOD);
if (ca == 0 && bc == 0)
add (ans, getDp (ab, bc, ca, 0, 0));
}
}
return dp[ab][bc][ca][turn][moved] = ans;
}
void solveTest (int n) {
memset (dp, 0, sizeof (dp));
f[0] = 1;
for (int i = 1; i <= 3 * n; i++)
f[i] = 1ll * f[i - 1] * i % MOD;
for (int i = 1; i <= 3 * n; i++)
freqA[i] = freqB[i] = freqC[i] = 0;
for (int i = 0; i < 2 * n; i++) {
int x;
cin >> x;
freqA[x]++;
}
for (int i = 0; i < 2 * n; i++) {
int x;
cin >> x;
freqB[x]++;
}
for (int i = 0; i < 2 * n; i++) {
int x;
cin >> x;
freqC[x]++;
}
int AB = 0, BC = 0, CA = 0;
for (int i = 1; i <= 3 * n; i++) {
if (freqA[i] && freqB[i])
AB++;
if (freqB[i] && freqC[i])
BC++;
if (freqC[i] && freqA[i])
CA++;
}
/// dp[AB][BC][CA][0][0] = 1;
cout << getDp (AB, BC, CA, 0, false) << "\n";
// int total = AB + BC + CA;
/* for (int sum = total; sum > 0; sum--)
for (int ab = 0; ab <= min (AB, sum); ab++)
for (int bc = 0; bc <= min (BC, sum - ab); bc++) {
int ca = sum - ab - bc;
if (ca <= CA) {
for (int turn = 0; turn < 3; turn++) {
for (int moved = 0; moved < 2; moved++)
pushDp (ab, bc, ca, turn, moved);
}
}
}*/
}
int main () {
int n, t;
cin >> n >> t;
while (t--)
solveTest (n);
return 0;
}
/**
1 1
1 2
3 3
2 1
**/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
303 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
290 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
301 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
300 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
328 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
297 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
308 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
335 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
310 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
310 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
