#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1e9 + 7;
const int N = 3 * 99 + 7;
int n;
int d[N][N][N];
int w[N][2];
int dp(int n01, int n12, int n02) {
if (~d[n01][n12][n02]) return d[n01][n12][n02];
if (n01 == 0 && n12 == 0 && n02 == 0) return d[n01][n12][n02] = 1;
d[n01][n12][n02] = 0;
for (int a0 = 0; a0 < 3; ++a0) {
if (a0 == 0 && (n01 > 0 || n02 > 0)) continue;
if (a0 == 1 && n01 == 0) continue;
if (a0 == 2 && n02 == 0) continue;
int m01 = n01, m12 = n12, m02 = n02;
int p = 1;
if (a0 == 1) {
p = (ll)p * m01 % M;
m01--;
}
if (a0 == 2) {
p = (ll)p * m02 % M;
m02--;
m12++;
}
for (int a1 = 0; a1 < 3; ++a1) {
if (a1 == 1 && (m01 > 0 || m12 > 0)) continue;
if (a1 == 0 && m01 == 0) continue;
if (a1 == 2 && m12 == 0) continue;
int k01 = m01, k12 = m12, k02 = m02;
int q = p;
if (a1 == 0) {
q = (ll)q * k01 % M;
k01--;
k02++;
}
if (a1 == 2) {
q = (ll)q * m12 % M;
k12--;
}
for (int a2 = 0; a2 < 3; ++a2) {
if (a2 == 2 && (k12 > 0 || k02 > 0)) continue;
if (a2 == 0 && k02 == 0) continue;
if (a2 == 1 && k12 == 0) continue;
int h01 = k01, h12 = k12, h02 = k02;
int r = q;
if (a2 == 0) {
r = (ll)r * h02 % M;
h02--;
}
if (a2 == 1) {
r = (ll)r * h12 % M;
h12--;
h02++;
}
if (h01 + h12 + h02 < n01 + n12 + n02) {
d[n01][n12][n02] += (ll)dp(h01, h12, h02) * r % M;
if (d[n01][n12][n02] >= M) d[n01][n12][n02] -= M;
}
}
}
}
return d[n01][n12][n02];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> n >> t;
while (t--) {
memset(w, 255, sizeof(w));
for (int p = 0; p < 3; ++p) {
for (int i = 0; i < 2 * n; ++i) {
int a;
cin >> a;
a--;
if (~w[a][0]) w[a][1] = p; else w[a][0] = p;
}
}
int n01 = 0, n12 = 0, n02 = 0;
for (int i = 0; i < 3 * n; ++i) {
if (w[i][0] == 0 && w[i][1] == 1) n01++;
if (w[i][0] == 1 && w[i][1] == 2) n12++;
if (w[i][0] == 0 && w[i][1] == 2) n02++;
}
memset(d, 255, sizeof(d));
cout << dp(n01, n12, n02) << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
110328 KB |
Output isn't correct |
| 2 |
Incorrect |
115 ms |
110328 KB |
Output isn't correct |
| 3 |
Incorrect |
115 ms |
110336 KB |
Output isn't correct |
| 4 |
Incorrect |
128 ms |
110584 KB |
Output isn't correct |
| 5 |
Incorrect |
249 ms |
110400 KB |
Output isn't correct |
| 6 |
Incorrect |
301 ms |
110456 KB |
Output isn't correct |
| 7 |
Incorrect |
377 ms |
110328 KB |
Output isn't correct |
| 8 |
Incorrect |
453 ms |
110456 KB |
Output isn't correct |
| 9 |
Incorrect |
558 ms |
110456 KB |
Output isn't correct |
| 10 |
Incorrect |
728 ms |
110496 KB |
Output isn't correct |
